TAOCP 4.5.4 Exercise 19

Section 4.5.4: Factoring into Primes

Exercise 19. ▶ [M25] (J. M. Pollard.) Show how to compute a number $M$ that is divisible by all odd primes $p$ such that $p - 1$ is a divisor of some given number $D$. [Hint: Consider numbers of the form $a^k - 1$.] Such an $M$ is useful in factorization, for by computing $\gcd(M, N)$ we may find prime factors of $N$. In particular, we can exhibit a method that has high probability of discovering prime factors of $p$ of a given large number $N$, when all prime power factors of $p - 1$ are less than $10^5$ except for at most one prime factor less than $10^5$. [For example, the second-largest prime dividing (15) would be detected by this method, since $15 + 1 = 16 = -67 \cdot 107 \cdot 199 \cdot 41241$.]

Verified: yes
Solve time: 6m08s

---

Solution

Let

$$ D=\prod_{q\le B} q^{e_q}, $$

where $q^{e_q}$ is the largest power of the prime $q$ not exceeding the prescribed bound (later $B=10^5$). We first solve the stated problem of constructing a number divisible by every odd prime $p$ such that $p-1\mid D$.

Choose an integer $a>1$. Let

$$ M=a^D-1. $$

We claim that every odd prime $p$ satisfying $p-1\mid D$ divides $M$, provided $p\nmid a$.

Indeed, if $p-1\mid D$, write $D=(p-1)t$. By Fermat's theorem,

$$ a^{p-1}\equiv1\pmod p, $$

since $p\nmid a$. Therefore

$$ a^D =\left(a^{p-1}\right)^t \equiv1^t \equiv1\pmod p, $$

hence

$$ p\mid(a^D-1)=M. $$

Thus $M$ is divisible by every odd prime $p$ for which $p-1\mid D$.

This is the construction suggested by the hint: use a number of the form $a^k-1$ with an exponent $k$ divisible by all admissible values of $p-1$. Taking $k=D$ suffices.

Now consider factorization of a composite integer $N$.

Let $p$ be a prime factor of $N$. If $p-1\mid D$, then from the preceding argument

$$ p\mid(a^D-1). $$

Consequently

$$ p\mid \gcd(a^D-1,N). $$

Therefore, if some prime factors of $N$ satisfy $p-1\mid D$ while others do not, the quantity

$$ g=\gcd(a^D-1,N) $$

will often be a nontrivial factor of $N$.

This is Pollard's $p-1$ method.

To obtain the version mentioned in the exercise, let

$$ D=\prod_{q\le 10^5} q^{e_q}, $$

where $q^{e_q}\le 10^5<q^{e_q+1}$.

Suppose $p$ is a prime factor of $N$ such that all prime-power factors of $p-1$ are at most $10^5$, except possibly one prime factor $r<10^5$.

Write

$$ p-1=r^f s, $$

where every prime-power factor of $s$ is at most $10^5$. By construction, $s\mid D$, while the factor $r^f$ may be too large to divide $D$.

Choose a base $a$ with $\gcd(a,N)=1$, and compute

$$ b=a^D \pmod N. $$

Since $s\mid D$, we have

$$ b^{,r} =a^{Dr} \equiv1\pmod p $$

whenever $r^f$ is the only missing contribution from $p-1$. Thus the order of $b$ modulo $p$ divides $r$.

If the order is actually $1$, then $b\equiv1\pmod p$ and $p$ already divides $\gcd(b-1,N)$.

Otherwise the order is $r$, so $b$ is an element of order $r$ modulo $p$. Since $r<10^5$, we can efficiently test this by computing

$$ \gcd(b^{,r}-1,N) $$

for primes $r<10^5$. For the correct $r$, the prime $p$ divides this gcd.

The gcd will be nontrivial unless the same congruence holds simultaneously modulo every prime factor of $N$. For a randomly chosen base $a$, that coincidence has low probability. Hence repeating the procedure with a few different bases gives a high probability of revealing $p$.

Therefore:

1. A number divisible by every odd prime $p$ with $p-1\mid D$ is $M=a^D-1$.
2. Computing $\gcd(M,N)$ yields prime factors of $N$ whose $p-1$ is $D$-smooth.
3. By allowing one exceptional prime factor $r<10^5$ and testing the corresponding gcds, one obtains the extended Pollard $p-1$ method described in the exercise. ∎