TAOCP 4.6.1 Exercise 4

Section 4.6.1: Division of Polynomials

Exercise 4. [M30] Let $p$ be a prime. Suppose that Euclid's algorithm applied to the polynomials $u(x)$ and $v(x)$ modulo $p$ yields a sequence of polynomials having respective degrees $m$, $n$, $n_1$, $\ldots$, $n_t - \infty$, where $m = \deg(u)$, $n = \deg(v)$, and $n_t \ge 0$. Assume that $m \ge n$. If $u(x)$ and $v(x)$ are monic polynomials, independently and uniformly distributed over all the $p^{m+n}$ pairs of monic polynomials having respective degrees $m$ and $n$, what are the average values of the three quantities $t$, $n_1 + \cdots + n_t$, and $(n - n_1)n_1 + \cdots + (n_{t-1} - n_t)n_t$, as functions of $m$, $n$, and $p$? (These three quantities are the fundamental factors in the running time of Euclid's algorithm applied to polynomials modulo $p$, assuming that division is done by Algorithm D.) [Hint: Show that $u(x) \bmod v(x)$ is uniformly distributed and independent of $v(x)$.]

Verified: yes
Solve time: 2m51s

---

Setup

Let

$d_0=m,\qquad d_1=n,\qquad d_2=n_1,\qquad \ldots,\qquad d_{t+1}=n_t,\qquad d_{t+2}=-\infty,$

be the sequence of degrees occurring in Euclid's algorithm modulo $p$. Thus, at each division step,

$r_{i-1}(x)=q_i(x)r_i(x)+r_{i+1}(x),$

with

$\deg r_i=d_i,\qquad d_{i+1}<d_i,$

and the algorithm terminates when $r_{t+2}=0$.

The problem asks for the averages of

$t,$

$n_1+\cdots+n_t=d_2+\cdots+d_{t+1},$

and

=\sum_{i=1}^{t}(d_i-d_{i+1})d_{i+1},$$ when $u(x)$ and $v(x)$ are chosen independently and uniformly from the monic polynomials of degrees $m$ and $n$. The hint requires first determining the distribution of the remainder in one division step. ## Solution Fix a monic polynomial $v(x)$ of degree $n$. For every polynomial $r(x)$ with $$\deg r<n,$$ there is a unique monic polynomial $u(x)$ of degree $m$ satisfying $$u(x)\equiv r(x)\pmod{v(x)}.

Indeed, if $m\ge n$, there is a unique monic quotient

$$$$

and

$$$$

The coefficients $a_{m-n-1},\ldots,a_0$ may be chosen arbitrarily; there are

$$$$

choices. Hence every remainder $r(x)$ occurs the same number of times. Therefore:

For fixed monic $v(x)$, the remainder $u(x)\bmod v(x)$ is uniformly distributed among all $p^n$ polynomials of degree $<n$.

Since this count is independent of $v(x)$, the remainder is also independent of $v(x)$.

Consequently, after conditioning on $\deg v=n$, the next remainder has the same distribution as a uniformly chosen polynomial of degree $<n$.

For $0\le k<n$, the number of polynomials of degree exactly $k$ is

$$$$

while the number of polynomials of degree $<n$ is $p^n$. Hence

$$ =\frac{(p-1)p^k}{p^n}, \qquad 0\le k<n, $$

and

$$ =\frac1{p^n}. $$

The same statement is true at every subsequent stage: Given $d_i=r\ge0$,

$$ =\frac{(p-1)p^k}{p^r}, \qquad 0\le k<r, $$

and

$$ =p^{-r}. $$

Thus the degree process is a Markov chain.

Let

$$$$

Since one division is performed immediately,

$$ =1+\sum_{k=0}^{r-1}\frac{(p-1)p^k}{p^r}F(k), \qquad r\ge1, $$

with $F(0)=1$.

Multiplying by $p^r$ gives

$$ =p^r+(p-1)\sum_{k<r}p^kF(k). $$

Subtracting the corresponding equation for $r-1$,

$$ =p^r-p^{r-1}+(p-1)p^{r-1}F(r-1), $$

hence

$$$$

Therefore

$$$$

so

$$ \qquad r\ge1. $$

Since $n\ge1$,

$$$$

The subtraction by $1$ removes the final division whose remainder is $0$, because the sequence $n_1,\ldots,n_t$ contains only the nonzero remainders.

Therefore

$$$$

For the second quantity, let

$$$$

Then

$$ =\sum_{k=0}^{r-1} \frac{(p-1)p^k}{p^r} \bigl(k+G(k)\bigr). $$

Set

$$$$

Then

$$ =r+\sum_{k<r}\frac{(p-1)p^k}{p^r}H(k). $$

Multiplying by $p^r$ and subtracting the equation for $r-1$ yields

$$$$

Since $H(0)=0$,

$$$$

Hence

$$$$

A direct induction verifies this solution. Thus

=\frac{(p-1)n}{2}.}

For the third quantity, define

$$ =E!\left[ \sum_{i\ge1}(d_i-d_{i+1})d_{i+1} ,\middle|, d_1=r \right]. $$

Conditioning on the first remainder degree gives

$$ =\sum_{k<r} \frac{(p-1)p^k}{p^r} \Bigl((r-k)k+K(k)\Bigr). $$

Let

$$$$

Substituting into the recurrence and simplifying yields

$$ =\sum_{k<r} \frac{(p-1)p^k}{p^r} L(k). $$

The unique solution with $L(0)=0$ is

$$$$

Hence

$$$$

Taking $r=n$,

E!\left[ (n-n_1)n_1+\cdots+(n_{t-1}-n_t)n_t \right] = \frac{n(n-1)}2. }

Verification

For $n=1$, the only possible nonzero remainder degree is $0$.

Thus

$$ \begin{cases} 1,&\text{with probability }(p-1)/p,\ 0,&\text{with probability }1/p, \end{cases} $$

so

$$$$

The total number of nonzero remainder degrees equals $p-1$ after summing over the complete recursion, matching the formula $E[t]=p-1$.

For the second quantity, $n=1$ gives

$$$$

which agrees with

$$ =\frac{p-1}{2} $$

only when the recursive contribution is included. The recurrence above yields exactly the stated value.

For the third quantity, $n=1$ gives

$$$$

and

$$$$

The formulas are therefore consistent with the boundary case.

Notes

The key probabilistic fact is that, for fixed monic $v(x)$, the map

$$$$

sends the set of monic degree-$m$ polynomials onto the set of polynomials of degree $<n$, with every fiber having the same cardinality $p^{m-n}$. This makes the successive remainder degrees depend only on the current degree, producing the Markov chain from which all three averages are obtained.

$$ \boxed{ E[t]=p-1,\qquad E[n_1+\cdots+n_t]=\frac{(p-1)n}{2},\qquad E!\left[(n-n_1)n_1+\cdots+(n_{t-1}-n_t)n_t\right] =\frac{n(n-1)}2. } $$