Factoring arbitrary n in (log n)^2
Trevor Blackwell
A few people [from c.l.f] have asked, so I may as well post it.
History: I mentioned that if you had a machine which could operate
(+,-,*,integer divide) on Integers (all countably infinite mathematician's
integers, not just -2^31..2^31) as a basic operation [i.e., constant
time] then you could factor a number n in (log n)^2 time, or better in
certain useful cases.
Take an integer n, which you want to factor. If you take some number
k<n, then x=GCD(k!,n)/k! will contain _some_ of the factors of n (the
ones larger than k). [see below for computing GCD and k! quickly]
So, I start by picking, say, k around sqrt(n), and compute x. Either:
- x will equal n, in which case k was too large, so let k=k/2 and try
again
- x will be a factor of n, in which case I use the same procedure
recursively to factor x.
Basically, you need to get k>some root, and k<another root, in order
to get factors. This is basically a binary search: you know if you're
too low or too high, so you reduce the interval for k by 1/2 each
time. So, this takes at most log n time.
There can be at most log(n) roots, which you get (at worst) one at a
time.
So, the key question: how do you compute k! without doing k
multiplications?
Let M be some suitably large number, say n^n. Compute (1+M)^n. [you can
take an nth power in log n time, by squaring log n times, and
multiplying some of them together corresponding to the binary
representation of n]
(1+M)^n = C(n,1)1 + C(n,2)M + .. + C(n,n)M^n [ binomial series]
and C(n,k) = n!/(n-k!)k!
So, you can get C(n,n/2) (or C(n,n/2-1) if n is odd) by dividing (1+M)^n
by M^(n/2), and taking it mod M. (so, this is why M must be greater
than C(n,n/2). n^n is a good choice).
quick example: let M=10000, n=8. Then, (1+M)^n =
100080028005600700056002800080001. C(8,4) = 70. Just divide by M^4,
^^
and take it mod M, to get the C(8,4) term.
So, you have C(n,n/2) in O(1) ops. Then, you compute C(n/2,n/4)
similarily, and multiply by its square, so you get
C(n,n/2) * C(n/2,n/4)^2 = n!/(n/4)!^4
You get rid of the (n/4)! by computing C(n/4,n/8) and so on, so in log
(n) steps you are left with n!.
GCD(n,m), of course, can be computed in O(min(log n,log m)), so the
GCD computation I mentioned takes log(n). So, basically each trial K
takes log(n) for computing k!, and log(n) for doing the GCD, and you
need to try at most log(n) values for k. So, we're talking
O((log n)^2).
Acknowledgement: the suggestion that there existed such an algorithm
came from Knuth, Seminumerical Algorithms, 2nd ed, [it's given as an
exercise there to work it out]; Knuth attributes it to A. Shamir.
So, this is impressive. Factoring the 400-bit numbers used in RSA public
key encryption would take c*16000 ops [c about 10, by a rough count] -
a blink of an eye for a 1 MIPS Integer Machine. Actually, it's much
better, because in breaking RSA you know that the number you want to
factor is the product of exactly 2 primes, you you pick
k=floor(sqrt(n)), so exactly one of the factors will be larger than
this. You get the roots of n in one round, so the algorithm runs in
log(n) this way, i.e. c*400 ops. Less than 5000 operations to break
one of the most secure codes known.
The problem,of course, is that (1+M)^n is around n^2n, which is
kinda large, about 2n log n digits. Most computer's ALUs are
substantially less than 2^400 = 10^120 bits.
You can't do this if you try to work in Zp or GF(p^m), because the
terms of (M+1)^n get scrambled, not to mention k!. I strongly doubt
that any modification of this algorithm to work over finite fields
would be the best way to do factoring in practice. But, it's a nifty
theoretical result.
I'm halfway though figuring out an algorithm to decide whether a graph
is Hamiltonian (the classic NP-complete problem) in O(E) time on the
Integer Machine, but I'm having trouble with one part of it. Has
anyone worked this one out, or know if it can be done or not?
--
----------------
Trevor Blackwell t...@das.harvard.edu (617) 495-8912
Aiken G9 / Harvard University / 33 Oxford St / Cambridge, MA / 02138
Trevor Blackwell
abro...@watdragon.uwaterloo.ca (Andrej Brodnik (Andy)) writes:
Isn't ``Integer machine'' something what van Emde Boas in Handbook on
Theor.CS calls ``MRAM''? He also puts MRAM in a ``second machine
class'' where is also PRAM. So, my final question is what is known
about factoring on PRAM?
I think it's a more powerful machine than PRAM: it can multiply and
divide in O(1) time: the best you can do on a PRAM [even with
infinitely many processors] is at least O(log n). Since the numbers
are on the order of (1+n^n)^n or approx 2^2n, a PRAM would take O(n)
time to run this. To get near this bound, you need O(n^2) processors.
Factoring on various parallel machines is a big research area: I won't
pretend to know the state of the art. This, however, is _not_ the
algorithm to use. It's just a theoretical curiosity.
Maybe Mr. Leyland will someday enlighten us on the RSA-129 algorithms.
ni...@harlqn.co.uk (Nick Haines) writes:
...
k<n, then x=GCD(k!,n)/k! will contain _some_ of the factors of n (the
...
Huh? GCD(k!,n) will be less than k!
Of course. I meant to say x=GCD(k!,n). (I had previously been using
LCM. I need a proofreader)