Section 6. Factoring. The Pollard ( ) factoring method.

In a nutshell, John Pollard's famous ( ) factorisation method (1974) gives a strategy - based on an ingenious use of Fermat's little theorem ( full details are available in the year Maple section of my web site) - for uncovering a prime factor of an integer n , if that n has a prime factor p such that ( ) has only relatively small prime factors...

And why - apart from its intrinsic interest - might one want to find a factor? Well one need look no further than the renowned RSA cryptographic method (a full treatment of which may be read in my Maple public lecture Bill Clinton, Bertie Ahern, and digital signatures ): the basis for its security rests on the current difficulty of the famous factorisation problem , of finding a fast method (or prove there isn't one) for factoring general n .

Note . In the following examples, Maple is using the 1971 Brillhart-Morrison continued fraction factorisation method.

> ifactor(15);

> n23 := 23!;

> length(n23);

> ifactor(n23);

> ifactor(n23 + 1);

>

> n90 := 90!;

> length(n90);

> ifactor(n90);

But Maple cannot factor ( ) (and I've placed the 'comment sign', # , before the command to prevent re-execution.

> # ifactor(n90 + 1);

> ifactor(n90 + 1, easy);

which informs that ( ) is a c omposite ' 139 ' digit number.

Note . That 139 digit number may be proved to be composite (not prime) by using Fermat's little theorem:

if ( ) is prime, one would have (mod )

for all integers a not divisible by ( ).

So, testing to see what happens when , one finds:

> 2&^n90 mod (n90 + 1);

>

and so it follows immediately that ( ) is not prime. (One says that ( ) has failed the Lucas-Fermat test to the base 2.)

Note . On April this year, Sean Irvine announced to the Number Theory mailing list the complete factorisation of ( ); it is the product of three primes, :

> p := 1381173038633;

> q := 42025070023047325132446149666132026718715669472074383;

> r := 25596421444788555447555320241499448369527283715169223676054601753562783959;

> is(n90 + 1 = p*q*r);

>

Now here is the famous 129 digit number, RSA129:

> RSA129 := 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541;

> length(RSA129);

>

I am certainly NOT going to attempt to factor it!! It first came to public attention in Martin Gardiner's much read column in the August 1997 issue of the Scientific American.

Rivest, Shamir and Adleman (of RSA fame) threw this number out as a challenge to be factored. Given the then state of mathematical knowledge (as far as factoring was concerned) and computer power, they estimated that it would take some 20,000 years to factor it, and thereby decrypt a message which they had encrypted using it as the ' n ' part of a public modulus.

Briefly, a method known as the 'Quadratic Sieve' - introduced in 1981 by the US mathematician Carl Pomerance - together with thousands of computers worldwide (organised by the Dutch mathematician Arjen Lenstra) - factored it by April 1994, and decrypted the RSA-encrypted message (which, incidentally, was: " The magic

words are squeamish ossifrage. ") Lenstra, and his co-workers found that RSA_129 was the product of the two prime numbers (I show them individually, then their produst, and then show their product really is RSA_129):

> f1 := 3490529510847650949147849619903898133417764638493387843990820577;

> length(f1);

>

> f2 := 32769132993266709549961988190834461413177642967992942539798288533;

> length(f2);

>

> f1*f2;

> is(RSA129 = f1*f2);

>

If I were to foolishly enter the Maple command:

> # ifactor(RSA_129);

>

then the timer would stay on for MANY, MANY years ... .

>

I am going to create a number - which I will call by the name 'much_greater_than_RSA129' - which will have these properties:

it will be the product of two primes 'P' and 'Q'

I will choose P to be f2 (the greater of the two primes whose product is RSA129)

I will choose Q to be much greater than P

Those choices will automatically make 'much_greater_than_RSA129' be much greater than RSA129 (hence the name).

This is how I will do it:

> P := f2;

>

To save time in my lecture I neutralise the following command, but beforehand copy and paste the output to the next command line.

> # Q := nextprime(4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903679999999999999630);

> Q := 4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000001;

>

> much_greater_than_RSA129 := P*Q;

> length(much_greater_than_RSA129);

>

But that MUCH LARGER number can now be factored in seconds by exploiting the Pollard ( ) factorisation method:

> Pollard := proc(n)
local a,k;
a[1]:=2:
for k from 2 while igcd(n,a[k-1]-1 mod n)=1
do a[k]:=a[k-1]&^k mod n od;
lprint(n,`is the PRODUCT of`, igcd(n, a[k-1]-1 mod n), `and`,
n/igcd(n, a[k-1]-1 mod n))
end:

> Pollard(much_greater_than_RSA129);

146481808053566948606112326494160580676597757390203425433760346556289969224977192583652803722778590707655656624536558761037114144280380743982554672552469432942539798288533   is the PRODUCT of   4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000001   and   32769132993266709549961988190834461413177642967992942539798288533

>

Wonderful? Yes? Of course I deliberately made up the prime Q so that all the prime factors of ( ) were small:

> ifactor(Q - 1);

>

You may have noticed that I choose Q so that the prime factors of Q are the first twenty-one primes: 2, 3, 5, ... , 71 and 73.

Finally, look at the two prime factors - f1 and f2 - of the RSA129 number; see how they behave:

> ifactor(f1 - 1);

> ifactor(f2 - 1);

>

Rivest, Shamir and Adleman knew what they were doing when the made up RSA129!!

And here you can see why it had been so difficult to find the prime factors q and r of ( ):

> ifactor(q-1, easy);

> ifactor(r-1, easy);

>