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