Development of Fermat's Method (was: RE: Mersenne: Hyperbola)
On 14 Jul 99, at 7:59, Paul Leyland wrote, in reply to my earlier message: Actually Fermat's Method is extraordinarily efficient at finding a factorization n = a * b when (a - b) is small. It's also easy to code, needs very little storage and (once initialized) requires only relatively low-precision arithmetic, therefore making the attempt fast (per iteration). All of this is completely true, as long as the concept "small" is well understood. Fermat's method is excellent if (a-b) is about sqrt(a) or sqrt(sqrt(N)). If it is much larger than this, Fermat's method is hopelessly slow. In a "typical case", Fermat's method is slower than trial division! I think you mean we want (a-b) to be _much_ smaller than sqrt(a) if Fermat's method is going to succeed reasonably quickly. However, ... Suppose we take a number which is proving troublesome to factorize, e.g. 2^727-1. Factors of this number are going to be of the form 1454k+1. The number is 219 decimal digits long; we are fairly sure, from work expended in ECM, that there are no factors much less than 45 digits long. Suppose we multiply 2^727-1 by 100!. The reason for doing this is that this just about guarantees that there is some combination of factors a, b such that (a-b) sqrt(a). Therefore we should be able to use Fermat's method (or anything else which might be better) and get a factorization in a reasonable time. We also know that none the factors of 2^727-1 are 100, so we can then reduce the factors found by dividing out of them all the primes 100. What we're left with must surely be the factorization of 2^727-1 (though the remaining factors might possibly still be composite). Now I'm not saying that the effort involved is trivial - I'm sure a run length of some hours, days or weeks would be neccessary. Also, I'd be very surprised indeed if I'm the first to suggest a trick like this, but, is it worth while starting to code this method? The point is that it's going to take a fair number of CPU years to complete ECM testing on 2^727-1 to the point where we're reasonably sure that there are no factors 10^50; for all we know, there might be only 2 factors each over 100 digits long, in which case ECM is almost certain to fail, unless _much_ faster hardware comes along. Regards Brian Beesley Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Development of Fermat's Method (was: RE: Mersenne: Hyperbola)
Hi folks Suppose we take a number which is proving troublesome to factorize, e.g. 2^727-1. Factors of this number are going to be of the form 1454k+1. Suppose we multiply 2^727-1 by 100!. The reason for doing this is that this just about guarantees that there is some combination of factors a, b such that (a-b) sqrt(a) Now I'm not saying that the effort involved is trivial - I'm sure a run length of some hours, days or weeks would be neccessary. Also, I'd be very surprised indeed if I'm the first to suggest a trick like this, but, is it worth while starting to code this method? I can give a reasonably informed answer to this, having tried it myself. To use Fermat's method directly on kN in order to factor N, unless you are very lucky, is no improvement. In the 2^727-1 case, as pointed out, since you know the form of the factors, it's sufficient to try a=727x+1, for all a above sqrt(N), to check a^2-N is a perfect square. To preserve this, make the factor you multiply by a product of factors of the form 1454k+1 - all the factors of the product are still of this form. Do we win, or do we lose? Let's suppose that our composite has precisely two prime factors, and thus direct application of Fermat will uncover only one non-trivial solution from which we can derive the factor values. If what we multiply by has k distinct factors, then there are now 2^k useful solutions - but the number of values of a that we need to try has increased by more than that factor. In all likelihood, it would take longer... But don't despair. Since all we have to check for is "a^2-N is a perfect square", it's easy just to inspect this value modulo many small primes and sieve out quadratic non-residues. With a few lookup tables, it's easy to trial-factor at 10^9, even 10^12, values of a per CPU-second. Even so, for a 219-digit number like 2^727-1, and even assuming there's no factor below 40 or so digits, you'd still need 10^60 or more CPU-seconds to spare. (OK if you've got a universe with nothing else to do). Unsurprisingly, the method needs a bit of control to be realizable - which is what the continued fraction method achieves. Each iteration finds a (relatively) small square modulo N (at worst sqrt(N) in absolute value), which, after striking out square factors, making sensible choices of which to store, and judicious combinations, you hope to eventually find non-trivial a^2=b^2 mod N. Still need a lot of luck, though, and the steps are now non-trivial... Chris Nash Lexington KY UNITED STATES == Still a co-discoverer of the largest known *non*-Mersenne prime Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Development of Fermat's Method (was: RE: Mersenne: Hyperbola)
Brian Beesley wrote: Suppose we multiply 2^727-1 by 100!. The reason for doing this is that this just about guarantees that there is some combination of factors a, b such that (a-b) sqrt(a). Therefore we should be able to use Fermat's method (or anything else which might be better) and get a factorization in a reasonable time. But the guarantee is not there. your a ~ sqrt(2^727 * 100!) ~ 10^188 sqrt(a) ~ 10^94 There are (only) 2^100 ~ 10^30 ways to choose the combinations of factors of 100! , which are the degrees of freedom. But they need to be chosen so that a-b 10^94 for a (and b) near 10^188. For f1, a factor of 2^727-1, near 10^100 it will be nearly impossible (not guaranteed) for (f1 * some combination of the factors of 100!) to be within one part in 10^94 of a certain number ~10^188. The combination of factors of 100! need to be within 10^-6 of a certain number of size ~ 10^88. 10^30 chances at hitting a number ~10^88 to within 10^-6 leaves you several dozen orders of magnitude short of a guarantee. Best regards, Todd Sauke Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
