TAOCP 3.2.1.3 Exercise 6

We are asked to determine which values of $m = w \pm 1$ in Table 3.

taocpmathematicsalgorithmsvolume-2medium

Section 3.2.1.3: Potency

Exercise 6. ▶ [20] Which of the values of $m = w \pm 1$ in Table 3.2.1.1–1 can be used in a linear congruential sequence of maximum period whose potency is 4 or more? (Use the result of exercise 5.)

Verified: yes
Solve time: 3m55s

Solution

We are asked to determine which values of $m = w \pm 1$ in Table 3.2.1.1–1 can be used in a linear congruential sequence of maximum period whose potency is at least $4$. We must use the result of Exercise 5 (Section 3.2.1.3).

Step 1: Recall the result of Exercise 5

Exercise 5 states the following. Let $m = \prod_{i=1}^r p_i^{e_i}$ be the prime-power factorization of the modulus, and let $a$ be a multiplier such that the linear congruential sequence

$$ x_{n+1} \equiv a x_n \pmod{m} $$

achieves maximum period. Then the potency $s$ of this sequence satisfies

$$ s = \min_i p_i^{,e_i - f_i} \quad \text{where (f_i) is the highest power of (p_i) dividing (a-1)}. $$

Equivalently, for the sequence to have potency at least 4, there must exist a choice of $a$ of maximum period such that for each prime $p_i$ dividing $m$, the corresponding exponent $f_i$ satisfies

$$ p_i^{,e_i - f_i} \ge 4. $$

This is the correct criterion to use.

Step 2: List the relevant moduli $m = w \pm 1$ from Table 3.2.1.1–1

Table 3.2.1.1–1 lists common computer word-size moduli of the form $2^n \pm 1$. Relevant entries are:

$$ \begin{aligned} m &= 2^8 - 1 = 255, & 2^8 + 1 = 257,\ m &= 2^{16} - 1 = 65535, & 2^{16} + 1 = 65537,\ m &= 2^{32} - 1 = 4294967295, & 2^{32} + 1 = 4294967297,\ m &= 2^{64} - 1, & 2^{64} + 1, \text{ etc.} \end{aligned} $$

We must examine the prime-power factorization of each modulus.

Step 3: Factorize each modulus

  1. $2^8 - 1 = 255 = 3 \cdot 5 \cdot 17$

Prime powers: $3^1, 5^1, 17^1$ 2. $2^8 + 1 = 257$

Prime: $257^1$ 3. $2^{16} - 1 = 65535 = 3 \cdot 5 \cdot 17 \cdot 257$

Prime powers: $3^1, 5^1, 17^1, 257^1$ 4. $2^{16} + 1 = 65537$

Prime: $65537^1$ 5. $2^{32} - 1 = 4294967295 = 3 \cdot 5 \cdot 17 \cdot 257 \cdot 65537$

Prime powers: $3^1, 5^1, 17^1, 257^1, 65537^1$ 6. $2^{32} + 1 = 4294967297 = 641 \cdot 6700417$

Prime powers: $641^1, 6700417^1$

Other higher-word moduli can be treated similarly. Each prime factor has exponent $1$.

Step 4: Apply the potency criterion

We require $p_i^{,e_i - f_i} \ge 4$ for some choice of maximum-period multiplier $a$. Here $e_i = 1$ for all prime factors of the above moduli.

  • Since $e_i = 1$, we have $1 - f_i \ge \log_{p_i} 4$.
  • But $f_i$ is a nonnegative integer ($f_i \le e_i = 1$).
  • Therefore $e_i - f_i \le 1$, so $p_i^{,e_i - f_i} \le p_i$.

Hence, the only way to have $p_i^{,e_i - f_i} \ge 4$ is if $p_i \ge 4$.

  • For $2^8 - 1 = 3 \cdot 5 \cdot 17$, the factor $3$ cannot satisfy $3 \ge 4$.
  • Similarly, for $2^{16} - 1 = 3 \cdot 5 \cdot 17 \cdot 257$, the factor $3$ fails.
  • The same reasoning excludes all other moduli except those that are prime and ≥ 4, since then $e_1 = 1$ and $p_1^{,1 - 0} = p_1 \ge 4$.

Step 5: Identify qualifying moduli

From the list:

  • $2^8 + 1 = 257$ (prime ≥ 4) ✅
  • $2^{16} + 1 = 65537$ (prime ≥ 4) ✅

All other moduli either:

  1. Contain a prime factor smaller than 4, or
  2. Are composite with all prime factors less than 4 (only $2^n - 1$ with $n \ge 2$ contain 3),

and thus cannot achieve potency ≥ 4 with a maximum-period multiplier.

Step 6: Conclusion

The values of $m = w \pm 1$ from Table 3.2.1.1–1 that admit a linear congruential sequence of maximum period and potency at least 4 are:

$$ \boxed{2^8 + 1 = 257, \quad 2^{16} + 1 = 65537.} $$

All other entries in the table either are composite with small prime factors or fail the potency criterion.

∎

Answer (explicit):

$$ \displaystyle m = 257, \quad 65537 $$

These are the only moduli of the form $w \pm 1$ from Table 3.2.1.1–1 suitable for maximum-period linear congruential sequences with potency ≥ 4.