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

1(mod p )isatmost1 / . This is very small if then the chance that a 1 ≡

≈ 10 20 . There seems to be no way to get the method to work. The elliptic

curve method has a much better chance of success in this case because it
allows us to change groups.
In the elliptic curve factorization method, we will need to choose random
elliptic curves mod n and random points on these curves. A good way to do
this is as follows. Choose a random integer A mod n and a random pair of
integers P =( u, v )mod n . Then choose C (the letter B is currently being
used for the bound) such that

C = v 2 u 3 − − Au (mod n ) .

This yields an elliptic curve y 2 = x 3 + Ax + C with a point ( u, v ). This is
much more e cient than the naive method of choosing A, C, u , then trying to
find v . In fact, since being able to find square roots mod n is computationally
equivalent to factoring n , this naive method will almost surely fail.
Here is the elliptic curve factorization method . We start with a com-
posite integer n (assume n is odd) that we want to factor and do the following.

1. Choose several (usually around 10 to 20) random elliptic curves E i :
y 2 = x 3 + A i x + B i and points P i mod n .

2. Choose an integer B (perhaps around 10 8 ) and compute ( B !) P i on E i
for each i .

3. If step 2 fails because some slope does not exist mod n ,thenwehave
found a factor of n .

4. If step 2 succeeds, increase B or choose new random curves E i and
points P i and start over.

Steps 2, 3, 4 can often be done in parallel using all of the curves E i simulta-
neously.
The elliptic curve method is very successful in finding a prime factor p of n
when p< 10 40 . Suppose we have a random integer n of around 100 decimal
digits, and we know it is composite (perhaps, for example, 2 n− 1

1(mod n ),
so Fermat's little theorem implies that n is not prime). If we cannot find a
small prime factor (by testing all of the primes up to 10 7 , for example), then
the elliptic curve method is worth trying since there is a good chance that n
will have a prime factor less than 10 40 .
Values of n that are used in cryptographic applications are now usually
chosen as n = pq with both p and q large (at least 75 decimal digits). For
such numbers, the quadratic sieve and the number field sieve factorization
methods outperform the elliptic curve method. However, the elliptic curve
method is sometimes used inside these methods to look for medium sized
prime factors of numbers that appear in intermediate steps.

≡