Other Applications - Elliptic Curves: Number Theory and Cryptography - page 190

on E , then the main problem we'll face is finding some integer k such that
kP = mod one of the factors of n . In fact, we'll often not obtain such an

integer k . But if we work with enough curves E ,itislikelythatatleastone
of them will allow us to find suc h a k . This is the key property of the elliptic
curve factorization method.

∞

Before we say more about elliptic curves, let's look at the classical p − 1
factorization method . We start with a composite integer n that we want
to factor. Choose a random integer a and a large integer B . Compute

a B ! a 1 ≡ (mod n ) , and gcd( a 1 − 1 ,n ) .

Note that we do not compute a B ! and then reduce mod n , since that would
overflow the computer. Instead, we can compute a B !

mod n recursively by

≡ a ( b− 1)! b (mod n ), for b =2 , 3 , 4 ,...,B .Orwecanwrite B !inbinary
and do modular exponentiation by successive squaring.
We say that an integer m is B-smooth if all of the prime factors of m are
less than or equal to B . For simplicity, assume n = pq is the product of two
large primes. Suppose that p − 1is B -smooth. Since B ! contains all of the
primes up to B , it is likely that B ! is a multiple of p − 1 (the main exception
is when p − 1 is divisible by the square of a prime that is between B/ 2and
B ). Therefore,

a b !

a 1 ≡ a B !

≡ 1(mod p )

by Fermat's little theorem (we ignore the very unlikely case that p | a ).

1 is divisible by a prime >B . Among all the elements in
the cyclic group Z q , there are at most ( q − 1) / that have order not divisible
by and at least ( − 1)( q − 1) / that have order divisible by .

Now suppose q −

(These

numbers are exact if 2 q − 1.) Therefore, it is very likely that the order of

a is divisible by , and therefore

a 1 ≡ a B ! ≡ 1(mod q ) .

Therefore, a 1 − 1 is a multiple of p but is not a multiple of q ,so

gcd( a 1 − 1 ,pq )= p.

If all the prime factors of q 1 are less than B , we usually obtain gcd( a 1 −

1 ,n )= n . In this case, we can try a smaller B , or use various other procedures
(similar to the one in Section 6.8). The main problem is choosing B so that
p − 1(or q − 1) is B -smooth. If we choose B small, the probability of this
is low. If we choose B very large, then the computation of a 1 becomes too
lengthy. So we need to choose B of medium size, maybe around 10 8 .But
what if both p − 1and q − 1 have prime factors of around 20 decimal digits?
We could keep trying various random choices of a , hoping to get lucky. But
the above calculation shows that if there is a prime with |p− 1 but >B ,

−