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

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$.

• To have a good chance to factor all numbers this way, $k$ would have to be really, really big and the computations would get out of hand. But, this is not very different from Pollard's $p-1$ algorithm which factors some number of a special form. – Felipe Voloch Feb 13 '18 at 0:27
• @FelipeVoloch I think this is precisely my question: why would $k$ have to be really, really big? Naively the number of “hits” should grow exponentially in the number of prime factors of $k$. – Robin Houston Feb 13 '18 at 0:30
• @FelipeVoloch Or perhaps I should ask more specifically: how big would it have to be, and why? – Robin Houston Feb 13 '18 at 0:40
• Suppose that you want to find the prime factor $p$. Let $q$ be the largest prime factor of $p-1$. The multiplicative order of $x\pmod{p}$ is $(p-1)/d$ , where $d$ is a divisor of $n$, which is usually quite small, in particular the largest prime factor of $(p-1)/d$ will practically always be $q$ as well. If $k$ is the product of the first primes, then you have to take $k$ to be as large as the product of all primes up to $q$. Conjecturally the largest prime factor of $p-1$ is distributed according to the Dickman function, thus $k$ has to be as large as $e^{p^c}$, where $c$ depends on $p$, – Jan-Christoph Schlage-Puchta Feb 15 '18 at 15:56
• but is usually bigger than $0.2$. The problem with your argument is that as $d$ runs over the divisors of $k$, most of the time you check whether $n$ is divisible by a prime which is much larger than $n$ itself, and only occasionally you go back and obtain information about smaller primes. – Jan-Christoph Schlage-Puchta Feb 15 '18 at 15:59

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.

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.
• Thanks! This doesn’t quite answer the question, but it’s very interesting (and new to me). – Robin Houston Feb 21 '18 at 16:41