Names of some factoring methods: Continued Fraction Algorithm Quadratic Sieve Algorithm Class Group Method Elliptic Curve Algorithm Number Field Sieve Fermat's method of difference of squares Dixon's Random Squares ALgorithm Valle's Two-thirds Algorithm Seysen's Class Group Algorithm Sources A. K. Lenstra, H.W. Lenstra Jr Algorithms in Number theory J. Van Leeuwen (Editor) Handbook of theoretical computer science, Volume A: Algorithms and Complexity Elsevier, PP. 673-715, 1990 Fermat's method commentary by garscosi@pipeline.com (Gary Scott Simon) or Albert Y.C. Lai trebla@vex.net http://www.vex.net/~trebla/ To express the number as x^2 - y^2, the best way (other than inspection in lucky cases like 77 = 81 - 4) is still exhausive search. Before you object, on computers Fermat's method is faster than trial division on average, first because on average Fermat's method requires fewer trials before success, and second division is much slower than multiplication. And if you are still not convinced, well, it is Fermat's method, not mine. I would use Pollard's rho. (Not true. I would use trial division like you did, for a brief moment, to factor out the small factors. Then, Pollard's rho.) Pick a pseudo random number generator mod n. Usually we use f(x) = (x^2 + 1) mod n. One could also use f(x) = (x^2 + c) mod n, where c is not -2 or 0, so that f is more random. Linear congruential's ((ax + b) mod n) are bad. Consider the sequence x_(k+1) = f(x_k), with x_0 arbitrarily chosen (1 will do). The aim is to find an x_i and an x_j so that gcd(n, x_i - x_j) gives a factor of n. Although a brute-force search will work, Pollard and Floyd proposed a cleverer way. (Brent proposed an even cleverer way, but it is harder and I don't feel like describing it.) Introduce the sequence y_(k+1) = f(f(y_k)), with y_0 = x_0. So y_i = x_2i. We just need to look at gcd(n, x_i - y_i). Let's just try. First split off the small prime factors: 34348384 = 2^5 * 7 * 153341, by minimal trial-division. Let's say now I am tired of trial division, and use Pollard's rho. I will use x_0 = 1, and f(x) = (x^2 + 1) mod 153341. x_i: 1 2 5 26 677 151648 106112 80256 90173 110064 145097 y_i: 1 5 677 106112 90173 145097 45990 98315 136955 54132 90173 - : 0 -3 -672 -106086 -89496 6551 60122 -18059 -46782 55932 54924 gcd: 1 1 1 113 1 23 1 2599 59 23 The factors stick out. Sometimes we don't feel like computing gcds for every i. If n is large, you will run through many i's before you hit a factor. In this case, it is safe to accumulate several x_i - y_i before you do a gcd: keep a running product of Product[i=m+1 to m+20 or something] (x_i - y_i), mod n, and find gcd(n, product) instead. From owner-math-history-list@ENTERPRISE.MAA.ORG Fri Jan 30 11:25 EST 1998 Approved-By: John Conway Date: Fri, 30 Jan 1998 11:25:19 -0500 Reply-To: Discussion List on the History of Mathematics , John Conway From: John Conway Subject: Re: F_5 Comments: To: Israel Kleiner To: MATH-HISTORY-LIST@ENTERPRISE.MAA.ORG In-Reply-To: <98Jan27.181757-0500_est.330101-27545+786@mail.on.rogers.wave.ca> Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Length: 609 Status: RO On Tue, 27 Jan 1998, Israel Kleiner wrote: > Thanks for the details. What I was really asking (although I didn't phrase > it that way) was how Euler showed that the divisors of F(5) are of the form > 64k+1. Once we know this, the rest is, of course, a straightforward > computation. > Regards, > Israel K. The reason is that if p is an odd prime divisor of F5, then 2 has order 64 modulo p (since 2^32 = -1, 2^64 must be the first power that's 1, mod p). But by Fermat's little theorem, 2^(p-1) is 1 mod p, and so 64 must divide p-1. The argument is due to Fermat rather than Euler. John Conway From owner-math-history-list@ENTERPRISE.MAA.ORG Fri Jan 30 11:56 EST 1998 Approved-By: John Conway Date: Fri, 30 Jan 1998 11:52:00 -0500 Reply-To: Discussion List on the History of Mathematics , John Conway From: John Conway Subject: Re: Euler and F5 Comments: To: Jack Wales To: MATH-HISTORY-LIST@ENTERPRISE.MAA.ORG On Wed, 28 Jan 1998, Jack Wales wrote: > SANDIFER@WCSUB.CTSTATEU.EDU,Internet writes:> > > > >Theorem 8: The sum of two such powers a^2^m + b^2^m, where the exponent > >is a > >power of two, admits no other divisors except those contained in the form > >2^(m+1) * n + 1. > > This seems to call for a somewhat more careful statement, because (for > example) 3^2^1+6^2^1=45, which admits 3 as a divisor, but 3 is not of the > form 2^(1+1)*n+1. Must a and b be relatively prime? Must a and b be > relatively prime with one of them even?> The proof is short and makes it easy to get the statement right. Namely, suppose that b is prime to p, and that p divides the above thing. Then modulo p, a/b exists and has (2^m)th power congruent to -1 mod p, and so (2^{m+1})th power congruent to +1 mod p. Provided that p isn't 2, this shows that the order of a/b is exactly 2^{m+1}, so that p-1 must be a multiple of that number. [The problem with p = 2 is that -1 and +1 are the same modulo 2.] So the condition is that p be not 2, and prime to b (which will follow from the coprimeness of a and b). John Conway