Why can’t you use cyclotomic polynomials to factor big numbers really quickly?

Question

Two simple remarks:

1. The polynomial $x^k-1$ can be factorised over the integers as a product of (irreducible) cyclotomic polynomials: $$x^k-1 = \prod_{d|k}\Phi_d(x).$$ If we choose $k$ to be a number that has a lot of divisors, then $x^k-1$ will have a lot of factors. For example, if $k$ is a product of $b$ distinct primes then $x^k-1$ has $2^b$ factors.

2. Suppose we are given some largeish natural number $n$, and we want to factorise it. One way to find a factor of $n$ would be to compute the product $a$ of lots of different numbers $a_i$, modulo $n,$ and then compute $\gcd(n, a)$. If we are lucky and some of the $a_i$ are factors of $n$ but $a$ is not a multiple of $n$, then the gcd will be a non-trivial factor of $n$.

Putting these together, one might imagine that a good way to find factors of $n$ would be to compute $\gcd(n, x^k-1\mathrm{\ mod\ } n)$ with $k$ a product of distinct primes and $x>1$. This is equivalent to testing $\Phi_d(x)$ for a common factor with $n$ for each of the exponentially-many divisors $d|k$. So it might naively be hoped that one could thereby factorise $n$ in time $O(\log n)$ or thereabouts.

Of course this does not actually work – one cannot thus factorise enormous numbers in the blink of an eye. I justify this claim on the non-mathematical grounds that a) if such a simple method worked then someone would have noticed by now; and the heuristic grounds that b) I tried it, and it didn’t.

What I would like to know is why it doesn’t work. Presumably the problem is that the $2^b$ values $\Phi_d(x)$ are distributed in a sufficiently non-uniform way to stymie the procedure. What’s going on here?

I can’t see much hint of this non-uniformity in examples that are small enough to compute all the $\Phi_d(x)$ explicitly in a reasonable amount of time. For example, if $n=61\times71=4331$ and $k=9699690$ is the product of the first eight primes, then the expression $\Phi_d(2)$ takes 244 different values as $d$ ranges over the $2^8=256$ divisors of $k$. (And as it happens, $\Phi_{35}(2)$ is a multiple of 71, and so computing $\gcd(4331, 2^{9699690}-1\mathrm{\ mod\ } 4331)$ reveals this factor.)

---

Added: Thanks to David E Speyer for a clear concise answer. Just to make it explicit, the “non-uniformity” at play here is that each prime factor of $\Phi_d(x)$ is congruent to 1 modulo $d$.

Answer 1

Lets suppose you're in the worst case scenario: $N=pq$ where $p=2p′+1$ and $q=2q′+1$ with $p$, $q$, $p′$ and $q′$ all prime and $p$ and $q$ roughly the same size. Then the order of $x$ modulo $p$ will be either $p′$ or $2p′$ for any $x \neq \pm 1 \mod p$, and similarly modulo $q$. So we expect $GCD(N,x^k−1)$ to be nontrivial only if $p′$ or $q′$ divide $k$. The odds of this happening are roughly $1/p′+1/q′ \approx 4/\sqrt{N}$, so you need to try $\sqrt{N}$ values of $(x,k)$ before you expect a hit.

Answer 2

Cyclotomic Factoring is a class of integer factoring algorithms. It is based on the Euler congruence $x^{\varphi(n)}-1 \equiv 0 \mod n$. There are a few well known special cases.

1. The $p-1$-Pollard algorithm.
2. The $p+$-William algorithm.

3. Aurifeuillian Factoring, this is the oldest.

   The time complexity is $O(n^{1/4})$ arithmetic operations. Many authors have tried to obtain $O(n^{1/5})$, but no major reduction in complexity have been achieved in the last few decades.

   There is a large literature on this topic, a few are listed.

4. A. Granville, Aurifeuillian factors, Math Comp. Vol. 75, 2006.

5. E. Bach, Factoring with Cyclotomic Polynomials, Math. Comp. 1989.