TAOCP 3.2.1.2 Exercise 4

We are given a linear congruential sequence $X_{n+1} = (a X_n + c) \bmod 2^e$ with $X_0 = 0$, and where $a$ and $c$ satisfy the conditions of Theorem A.

taocpmathematicsalgorithmsvolume-2math-medium

Section 3.2.1.2: Choice of Multiplier

Exercise 4. [M20] Assume that $m = 2^e$ and $X_0 = 0$. If the numbers $a$ and $c$ satisfy the conditions of Theorem A, what is the value of $X_{2^{e-1}}$?

Verified: yes
Solve time: 1m32s

Solution

We are given a linear congruential sequence

$X_{n+1} = (a X_n + c) \bmod 2^e$

with $X_0 = 0$, and where $a$ and $c$ satisfy the conditions of Theorem A. Since $m = 2^e$, Theorem A requires that $c$ is odd and that $a \equiv 1 \pmod{4}$. We are to compute $X_{2^{e-1}}$.

By formula 3.2.1–(6), the general term of a linear congruential sequence with $X_0 = 0$ is

$X_n = \frac{a^n - 1}{a - 1} , c \bmod 2^e.$

Set $n = 2^{e-1}$:

$X_{2^{e-1}} = \frac{a^{2^{e-1}} - 1}{a - 1} , c \bmod 2^e.$

Write $a = 1 + 4q$ for some integer $q$, as required by Theorem A. Then

$a - 1 = 4q.$

Apply Lemma P repeatedly with $p = 2$, $r = 2$, and $x = a = 1 + 4q$. Lemma P shows that for any integer $g \ge 0$:

$(1 + 4q)^{2^g} \equiv 1 + 2^{g+2} q \pmod{2^{g+3}}.$

Set $g = e-2$. Then

$(1 + 4q)^{2^{e-2}} \equiv 1 + 2^{e} q \equiv 1 \pmod{2^e},$

since $2^e q$ is divisible by $2^e$. Therefore

$a^{2^{e-2}} \equiv 1 \pmod{2^e}.$

We need $a^{2^{e-1}} - 1$. Observe that

$a^{2^{e-1}} = (a^{2^{e-2}})^2 \equiv 1^2 \equiv 1 \pmod{2^e}.$

Thus

$a^{2^{e-1}} - 1 \equiv 0 \pmod{2^e}.$

We now consider

$\frac{a^{2^{e-1}} - 1}{a - 1} = \frac{0}{4q} = 0 \pmod{2^e}.$

But we must be careful modulo powers of 2. By repeated application of Lemma P, we have the more precise congruence:

$(1 + 4q)^{2^{e-1}} - 1 \equiv 2^{e-1} \cdot 4 q = 2^{e+1} q \pmod{2^{e+1}}.$

Dividing by $a - 1 = 4q$, we obtain

$\frac{a^{2^{e-1}} - 1}{a - 1} \equiv \frac{2^{e+1} q}{4 q} = 2 \pmod{2^e}.$

Multiplying by $c$ gives

$X_{2^{e-1}} \equiv 2 c \pmod{2^e}.$

Since $c$ is odd, $2c$ is congruent to $2$ modulo $4$ and is less than $2^e$. Therefore the final answer is

$\boxed{X_{2^{e-1}} = 2 c \bmod 2^e}.$

This completes the solution. ∎