19
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Felipe Voloch Feb 13 '18 at 0:27
  • 1
    $\begingroup$ @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$. $\endgroup$ – Robin Houston Feb 13 '18 at 0:30
  • 1
    $\begingroup$ @FelipeVoloch Or perhaps I should ask more specifically: how big would it have to be, and why? $\endgroup$ – Robin Houston Feb 13 '18 at 0:40
  • $\begingroup$ 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$, $\endgroup$ – Jan-Christoph Schlage-Puchta Feb 15 '18 at 15:56
  • 1
    $\begingroup$ 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. $\endgroup$ – Jan-Christoph Schlage-Puchta Feb 15 '18 at 15:59
31
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.