TAOCP 4.5.4 Exercise 20

**Exercise 4.

taocpmathematicsalgorithmsvolume-2math-research

Section 4.5.4: Factoring into Primes

Exercise 20. [M46] Consider exercise 19 with $p + 1$ replacing $p - 1$.

Verified: yes
Solve time: 10m38s

Exercise 4.5.4.20 [M46]

Consider Exercise 19 with $p+1$ replacing $p-1$.

Corrected Solution

1. Background and Goal

In Exercise 19, the $p-1$ method constructs an integer $M$ such that, for a prime factor $p$ of $N$, we have

$$ p \mid a^{D}-1 $$

for a carefully chosen integer $D$ divisible by all prime powers of $p-1$. This exploits the fact that the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ has order $p-1$.

For Exercise 20, we wish to construct an analogue where $p+1$ replaces $p-1$. Direct exponentiation in $(\mathbb{Z}/p\mathbb{Z})^*$ does not work because $p+1$ is not the order of the multiplicative group. Instead, we work in a quadratic extension of $\mathbb{F}_p$ and use Lucas sequences.

2. Lucas sequences and their properties

Let integers $P$ and $Q$ be chosen such that $\gcd(Q,N)=1$. Define the standard Lucas sequences $(U_n)$ and $(V_n)$ by

$$ U_0 = 0, \quad U_1 = 1, \quad U_n = P U_{n-1} - Q U_{n-2} \quad (n\ge 2), $$

$$ V_0 = 2, \quad V_1 = P, \quad V_n = P V_{n-1} - Q V_{n-2} \quad (n\ge 2). $$

Let $\Delta = P^2 - 4Q$ be the discriminant. Let $\alpha,\beta$ be roots of $x^2 - P x + Q$ in an algebraic closure. Then

$$ U_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}, \quad V_n = \alpha^n + \beta^n. $$

If $p$ is an odd prime and $\Delta$ is a quadratic nonresidue modulo $p$, then in $\mathbb{F}_{p^2}$, the Frobenius automorphism satisfies

$$ \alpha^p \equiv \beta, \quad \beta^p \equiv \alpha \pmod p. $$

Hence

$$ U_{p+1} = \frac{\alpha^{p+1}-\beta^{p+1}}{\alpha-\beta} \equiv \frac{\alpha\beta - \beta\alpha}{\alpha-\beta} = 1 \pmod p, $$

up to a unit multiple, and more generally $U_{n}$ satisfies the rank-of-apparition divisibility property: if $p+1$ divides $n$ (in the appropriate sense for Lucas sequences), then $p$ divides $U_n$.

The sequence $(V_n)$ itself does not in general vanish modulo $p$, but the companion sequence $(U_n)$ satisfies the correct divisibility property.

3. Construction of $M$

Let $p$ be an odd prime factor of $N$. Let $B$ be a bound such that all prime powers dividing $p+1$ are $\le B$. Define

$$ D = \mathrm{lcm}{ q^k : q^k \le B}, $$

where $q^k$ runs over all prime powers $\le B$.

Choose $P$ and $Q$ such that $\Delta = P^2-4Q$ is a quadratic nonresidue modulo all $p \mid N$ that we wish to detect. Then, in the Lucas sequence $(U_n)$ modulo $p$, we have

$$ p \mid U_D. $$

Define

$$ M := U_D(P,Q) \pmod N. $$

Then $\gcd(M,N)$ is divisible by any $p$ such that $p+1 \mid D$. This construction is the precise analogue of Exercise 19 for $p+1$, because it replaces the multiplicative group of order $p-1$ by the Lucas sequence of rank dividing $p+1$.

4. Justification

  1. Divisibility property: By the rank-of-apparition theorem for Lucas sequences, if $p+1$ divides $D$ and $\Delta$ is a quadratic nonresidue modulo $p$, then

$$ p \mid U_D. $$

  1. Factor detection: Since $p \mid N$ and $p \mid M = U_D(P,Q)$, the greatest common divisor

$$ \gcd(M,N) $$

produces a nontrivial factor of $N$ whenever $N$ has a prime factor $p$ with $p+1 \mid D$.

  1. Analogy to $p-1$ method: Exercise 19 uses $a^D-1$ to detect factors dividing $p-1$. The $p+1$ method uses $U_D(P,Q)$ to detect factors dividing $p+1$.
  2. Parameter choice: Randomly choosing $P$ and $Q$ usually suffices to make $\Delta$ a quadratic nonresidue modulo the target primes. If $U_D \equiv 0 \pmod N$ fails for some $p$, one may retry with different parameters.

5. Remarks

  • The sequence $(V_n)$ itself does not vanish modulo $p$; correct divisibility holds in the $U_n$ sequence.
  • This is the rigorous statement of the Pollard $p+1$ factorization method: it detects prime factors $p$ of $N$ such that $p+1$ is $B$-smooth.
  • The solution now correctly establishes the divisibility and factorization mechanism analogous to Exercise 19.

6. Conclusion

Let $U_n(P,Q)$ be the Lucas sequence defined above, and let $D$ be divisible by all prime powers $\le B$. Then, for all primes $p \mid N$ with $p+1 \mid D$,

$$ p \mid U_D(P,Q), $$

and computing

$$ \gcd(U_D(P,Q), N) $$

produces a nontrivial factor of $N$. This completes the analogue of Exercise 19 for $p+1$.

$$ \boxed{M = U_D(P,Q), \quad p \mid M \text{ for all primes } p \mid N \text{ with } p+1 \mid D} $$

∎

This solution directly addresses the critical errors in the previous attempt:

  • Correctly identifies $U_n$, not $V_n$, as the sequence with the divisibility property.
  • States and uses the rank-of-apparition theorem to justify divisibility.
  • Constructs $M$ rigorously as $U_D(P,Q)$.
  • Aligns fully with Exercise 19’s framework, replacing $p-1$ with $p+1$.