|
||||||||||||||||||||||||||||||||||||||
Home
News How? Status Results Records Primes Contributors Join us! Reserve Links Contact |
There are many different factoring algorithms.
Usually all of them are separated into two groups. Partial factorization
algorithms allow us to find some small factors (having up to 50 and more
digits) of a given composite number, and their running time is more dependent
on the size of the factor than on the size of the composite. Complete factorization
algorithms split one composite (having 100 and more digits) into two (or
more) parts of roughly the same size, and in this case running time depends
on the size of initial composite number. Such methods as trial division,
William's P+1, Pollard's Rho and P-1, Lenstra's elliptic curve method (ECM)
belong to the first group, while numerous sieves, such as MPQS, SIQS, GNFS,
SNFS, belong to the second group of factoring algorithms.
Note that partial factorization algorithm may produce a complete factorization of a number, but only if this composite contain no more than one big prime factor. On the other hand, complete factorization algorithm may find a composite factor, but applying this method again to this much smaller composite quickly completes the factorization. The main idea of integer factorization is to extract small factors by ECM until cofactor became prime or factorable enough quickly with sieve methods. Usually, when running ECM on many composites at the same time, some smaller ones should be taken out and factored with sieve methods as soon as the average period of extracting ECM factors become twice less than sieve running time for those small composites. Here is the table of recommended ECM parameters to remove
the most of small factors having less than a given number of digits:
Sometimes P-1 method give better results than ECM when factors are known to possess some special properties. Note that very small factors (up to ~8 digits) are usually to be removed yet before ECM (or P-1) by trial division, Rho, etc. There are many implementations of ECM, one of the best being GMP-ECM by Paul Zimmermann et. al. based on GMP library. General sieve methods (quadratic sieves) are those for which any composites are suitable. Usually self-initializing quadratic sieve (SIQS) is used for composites having up to 100 digits. Here you can use an excellent Msieve by Jason S. Papadopoulos. Number field sieves are usually used for larger numbers. GNFS become faster than QS nearly at 100 decimal digits; SNFS is yet faster than GNFS, but tricky to be applied. Note that numbers of the form xy + yx may be factored by SNFS, altough their composite cofactors may appear enough small to make another method faster, especially when a lot of small factors are removed by ECM. There are few implementations of NFS, the most popular being GGNFS by Chris Monico and Msieve by Jason S. Papadopoulos, though some people use software written by Jens Franke. Generally, we can work out enough quick and simple factoring strategy for an array of composites of typical size (50-300 digits). There is my variant; I think it can't be notably speeded up without getting too complicated. Step 1. Algebraic factoring, trial division,
rho, quick P-1
If there are thousands of composites, a single machine usually will not be able to go further. So it's better to stop here and distribute following-up ECM work starting at B1 = 3*106, unless you have a powerful cluster or the number of composites is enough small (say, a hundred). Step 8. ECM, B1 from 2M through 5M with
step 2k
The last stage is usually merged with NFS methods. Some papers about methods of integer factorization and their applications are listed in the Links section. |
|||||||||||||||||||||||||||||||||||||