Chapter 7
Other Applications
In the 1980s, about the same time that elliptic curves were being introduced
into cryptography, two related applications of elliptic curves were found, one
to factoring and one to primality testing. These are generalizations of classical
methods that worked with multiplicative groups Z× n . The main advantage of
elliptic curves stems from the fact that there are many elliptic curves mod a
number n, so if one elliptic curve doesn’t work, another can be tried.
The problems of factorization and primality testing are related, but are
very different in nature. The largest announced factorization up to the year
2007 was of an integer with 200 digits. However, it was at that time possible
to prove primality of primes of several thousand digits.
It is possible to prove that a number is composite without finding a factor.
One way is to show that an−1 ≡ 1 (mod n) for some a with gcd(a, n) = 1.
Fermat’s little theorem says that if n is prime and gcd(a, n) = 1, then an−1 ≡ 1
(mod n), so it follows that n must be composite, even though we have not
produced a factor. Of course, if an−1 ≡ 1 (mod n) for several random choices
of a, we might suspect that n is probably prime. But how can we actually
prove n is prime?
√ If n has only a few digits, we can divide n by each of the
primes up to n. However, if n has hundreds of digits, this method will take
too long (much longer than the predicted life of the universe). In Section 7.2,
we discuss efficient methods for proving primality. Similarly, suppose we have
proved that a number is composite. How do we find the factors? This is a
difficult computational problem. If the smallest prime √ factor of n has more
than a few digits, then trying all prime factors up to n cannot work. In
Section 7.1, we give a method that works well on numbers n of around 60
digits.
7.1 Factoring Using Elliptic Curves
In the mid 1980s, Hendrik Lenstra [75] gave new impetus to the study of
elliptic curves by developing an efficient factoring algorithm that used elliptic
189
© 2008 by Taylor & Francis Group, LLC
190 CHAPTER 7 OTHER APPLICATIONS
curves. It turned out to be very effective for factoring numbers of around 60
decimal digits, and, for larger numbers, finding prime factors having around
20 to 30 decimal digits.
We start with an example.
Example 7.1
We want to factor 4453. Let E be the elliptic curve y 2 = x3 + 10x − 2 mod
4453 and let P = (1, 3). Let’s try to compute 3P . First, we compute 2P . The
slope of the tangent line at P is
3x2 + 10 13
= ≡ 3713 (mod 4453).
2y 6
We used the fact that gcd(6, 4453) = 1 to find 6−1 ≡ 3711 (mod 4453). Using
this slope, we find that 2P = (x, y), with
x ≡ 37132 − 2 ≡ 4332, y ≡ −3713(x − 1) − 3 ≡ 3230.
To compute 3P , we add P and 2P . The slope is
3230 − 3 3227
= .
4332 − 1 4331
But gcd(4331, 4453) = 61 = 1. Therefore, we cannot find 4331−1 (mod 4453),
and we cannot evaluate the slope. However, we have found the factor 61 of
4453, and therefore 4453 = 61 · 73.
Recall (Section 2.11) that
E(Z4453 ) = E(F61 ) ⊕ E(F73 ).
If we look at the multiples of P mod 61 we have
P ≡ (1, 3), 2P ≡ (1, 58), 3P ≡ ∞, 4P ≡ (1, 3), . . . (mod 61).
However, the multiples of P mod 73 are
P ≡ (1, 3), 2P ≡ (25, 18), 3P ≡ (28, 44), . . . , 64P ≡ ∞ (mod 73).
Therefore, when we computed 3P mod 4453, we obtained ∞ mod 61 and a
finite point mod 73. This is why the slope had a 61 in the denominator and
was therefore infinite mod 61. If the order of P mod 73 had been 3 instead
of 64, the slope would have had 0 mod 4453 in its denominator and the gcd
would have been 4453, which would have meant that we did not obtain the
factorization of 4453. But the probability is low that the order of a point
mod 61 is exactly the same as the order of a point mod 73, so this situation
will usually not cause us much trouble. If we replace 4453 with a much larger
composite number n and work with an elliptic curve mod n and a point P
© 2008 by Taylor & Francis Group, LLC