New Algorithms for Integer Factoring and Integer Factorials ====Warren D. Smith Dec 2011===PRELIMINARY FIRST DRAFT============== In this note I explain new algorithms for factoring integer N. I also explain new algorithms for computing N!, the factorial of N. These algorithms both appaear to be world records, although the senses in which that is true are not necessarily very impressive. *****I. Factorial. To compute N!, the naive method is 1*2*3*...*(N-1)*N. We want faster methods. Mentally divide the sequence 1,2,3,...,N into R=floor(squareroot(N)) chunks each R long, plus a leftover smaller chunk if N is not a perfect square. Consider the degree-M polynomial (x)(x-1)(x-2)...(x+1-M) which we can abbreviate as x^_M ["falling factorial"]. We have N! = N^_R * (N-R)^_R * (N-2R)^_R *... * (N-[R-1]R)^_R * (N-RR)!. The final chunk (N-RR)! can be evaluated recursively or just naively using <R operations. All the other chunk values are different values of the same polynomial x^_R, it is just that this polynomial is evaluated at R different values of its argument x, where the different arguments form an arithmetic sequence. Finally multiply all the R+1 terms together going up a binary tree. There are known fast algorithms for simultaneously-evaluating a polynomial of degree M at M different argument values (forming an arithmetic sequence) in a number of arithmetic operations O(pm(M)*logM) where pm(M) denotes the number of arithmetic operations required to multiply to degree-M polynomials symbolically. See, e.g. A.Bostan & E.Schost: Polynomial evaluation and interpolation on special sets of points, Journal of Complexity 21,4 (2005) 420-446. http://algo.inria.fr/bostan/publications/BoSc05.pdf [I also have a different algorithm than theirs which matches their time bound, though probably with a worse constant factor.] By using FFT convolution theorem to multiply polynomials symbolically, pm(M)=O(M*logM). Note, this FFT approach takes us outside the integers into the real and complex numbers, but at the end of the process you get integers back (and the reals did not need to have much higher precision than the integers had to keep the erorrs below +-0.1). If this bothers you you can use Toom multiplication with pm(M)=O(M^(1+epsilon)) instead. This keeps everything rational with bounded denominators. Also, the polynomial x^_M can be computed in symbolic form if desired by polynomial multiplication on a binary tree, in O(pm(M)*logM) arithmetic steps. CONCLUSIONS: 1. N! can be computed in O(squareroot(N)*(logN)^2) arithmetic operations. 2. The total time usage is more interesting to most people than the arithmetic operation count. If we compute over the ring of integers, then the time should be of the same order as performing logN multiplications on numbers of the same length as N!. If we compute over some small ring (such as "the integers mod 1009") then the arithmetic-op count really does govern the time since all operations are on bounded-length numbers. 3. The memory usage is large: need to store order squareroot(N) numbers. *****II. Even faster "primorial"-like things such as LCM(1,2,3,...,N). It is possible to speed up the above algorithm somewhat further by cleverness about primes. I have not thought carefully about how far that can be pushed. But just to make it clear that speedup is possible... suppose instead of computing N! we were satisfied to compute some multiple of primorial(N). Then we do not need to multiply 1*2*3*...*(N-1)*N. It suffices to multiply (product of primes<L) * (product of numbers from L to N which are relatively prime to all primes<L) where L is chosen so that primorial(L)=squareroot(N) roughly, i.e. L has order logN/loglogN roughly. In this case each of my "falling factorial" polynomials can be replaced by a polynomial whose terms have been "sieved" to remove ones that would have been multiples of the primes<L. The degree of this polynomial would no longer be longer R, but rather about R/loglogN. Actually you need to adjust the parameters a bit... and if you want factorials not primorials you need to keep track of the stuff you sacrificed and put it back in... but anyhow SLIGHT IMPROVEMENT: N! can be computed in O(squareroot(N/loglogN)*(logN)^2) arithmetic operations and comparable-factor savings should be possible re time savings and memory usage too. Quite possibly one can do better than these since my prime-using methods were very straightforward with no attempt to be clever. Peter Luschny and Arnold Sch:onhage each invented clever prime-using methods that compute N! in the same time as doing a constant number of multiplications of the numbers of the same length as N! [i.e. O(NlogN) bits long] but their methods, though better than me by a log factor about TIME, are far far worse than me about ARITHMETIC-OP COUNT... so we have to wonder if it is possible to get the best of both worlds. *****III. Factoring the integer N. Assume we know N is composite (fast primality tests are known) and it is not divisible by (say) the primes<100. Define the function F(x)=gcd(x!, N). This is a monotonically increasing function of x with 1<x<=N, and F(1)=1 and F(N)=N. We can evaluate it fast by computing (x! mod N) using the fast algorithm above in the ring of integers mod N, then fast gcd algorithm. (The "improved" algorithm II will also work.) To factor N, one approach is to do a binary search on x with 100<x<squareroot(N) to find an x such that F(x)>F(x-1) and then gcd(x,N) will be a nontrivial factor of N. This will run in time = O( (squareroot(N)/loglogN)^(1/2) * (logN)^2) arithmetic operations on numbers each O(logN) bits long [same length as const*N^2] memory = O( (squareroot(N)/loglogN)^(1/2) ) numbers each O(logN) bits long. That is: Total time = O( N^(1/4) * (logN)^2 * (loglogN)^(1/2) ) * (logloglogN or lower) bit-ops. Total memory = O( N^(1/4) * logN * (loglogN)^(1/2) ) bits. As far as I know, this is a new world record time bound for integer factoring provided we only allow algorithms that are (i) deterministic and (ii) have rigorous worst-case time bound. Further, as I said it might be possible to improve this further by some kind of log factor with cleverer prime-using tricks. *****IV. Factoring the integer N using less memory but more time. Our proposal so far can be viewed as a way to speed up "trial division." As R.S.Lehman pointed out, it is possible to speed up factoring by doing a combination of "trial division to find factors < L" with "Fermat's difference of squares method to find factors > L". Lehman chose the breakpoint L to be of order N^(1/3) thus achieving a rigorous factoring algorithm running in O(N^(1/3)) arithmetic operations. R. Sherman Lehman: Factoring Large Integers, Mathematics of Computation 28, 126 (April 1974) 637-646 We now propose to do the same thing as Lehman but now using "sped-up trial division." I haven't checked this as carefully as I should, but I believe what happens is this. Choose the breakpoint L=N^P for 1/4<=P<=1/2. Besides P, there will also be another tunable parameter Q, with 0<Q<=P/2. The runtime will then be time = O( N^(P-Q) * (loglogN)^(-1/2) * (logN)^2 + N^([1-P]/2) ) arithmetic operations and memory = O( (N^Q / loglogN)^(1/2) ) numbers. If P=1/2 and Q=1/4 then we get our fast (but memory-hog) algorithm without using Fermat. If 1/4<=P<1/2 we slow down, but can enjoy using less memory. For example, choose P=0.4 and Q=0.1 to get a factoring algorithm running in time O(N^0.3) ignoring log terms, and with memory usage O(N^).1) ignoring log terms. This compromise strikes me as actually pretty attractive -- more attractive than either plain Lehman, plain Fermat, or plain trial division. However, it will still be heavily outperformed by Pollard-rho method, ECM, Quadratic Sieve, and NF-Sieve factorers, if you are willing to accept the fact they are nondeterministic and/or have nonrigorous time bounds. *****V. History -- is this just a rediscovery?. It now seems likely that V.Strassen 1976 in a paper I have not seen, invented something similar to my algorithms here -- but I suspect his log terms must have been slightly worse than mine? Volker Strassen: Einige Resultate u:ber Berechnungskomplexitat, Jahresber. Deutsch. Math.-Verein 78,1 (1976/7) 1-8. --end.