Two simple remarks:

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.

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