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



Why can’t you use cyclotomic polynomials to factor big numbers really quickly?
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.


