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— . The main advantage of
n
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 di¬erent 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 ¬nding 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 e¬cient methods for proving primality. Similarly, suppose we have
proved that a number is composite. How do we ¬nd the factors? This is a
factor of n has more
di¬cult computational problem. If the smallest prime √
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 e¬cient factoring algorithm that used elliptic


189

© 2008 by Taylor & Francis Group, LLC
190 CHAPTER 7 OTHER APPLICATIONS

curves. It turned out to be very e¬ective for factoring numbers of around 60
decimal digits, and, for larger numbers, ¬nding 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 ¬nd 6’1 ≡ 3711 (mod 4453). Using
this slope, we ¬nd 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 ¬nd 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
¬nite point mod 73. This is why the slope had a 61 in the denominator and
was therefore in¬nite 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
191
SECTION 7.1 FACTORING USING ELLIPTIC CURVES

on E, then the main problem we™ll face is ¬nding 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, it is likely that at least one
of them will allow us to ¬nd such 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

a1 ≡ aB! (mod n), and gcd(a1 ’ 1, n).

Note that we do not compute aB! and then reduce mod n, since that would
over¬‚ow the computer. Instead, we can compute aB! mod n recursively by
b
ab! ≡ a(b’1)! (mod n), for b = 2, 3, 4, . . . , B. Or we can write B! in binary
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 ’ 1 is 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/2 and
B). Therefore,
a1 ≡ aB! ≡ 1 (mod p)
by Fermat™s little theorem (we ignore the very unlikely case that p|a).
Now suppose q ’ 1 is divisible by a prime > B. Among all the elements in
the cyclic group Z— , there are at most (q ’ 1)/ that have order not divisible
q
by and at least ( ’ 1)(q ’ 1)/ that have order divisible by . (These
numbers are exact if 2 q ’ 1.) Therefore, it is very likely that the order of
a is divisible by , and therefore

a1 ≡ aB! ≡ 1 (mod q).

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

gcd(a1 ’ 1, pq) = p.

If all the prime factors of q ’ 1 are less than B, we usually obtain gcd(a1 ’
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 a1 becomes too
lengthy. So we need to choose B of medium size, maybe around 108 . But
what if both p ’ 1 and 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,




© 2008 by Taylor & Francis Group, LLC
192 CHAPTER 7 OTHER APPLICATIONS

then the chance that a1 ≡ 1 (mod p) is at most 1/ . This is very small if
≈ 1020 . 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 ’ u3 ’ Au (mod n).

This yields an elliptic curve y 2 = x3 + 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
¬nd v. In fact, since being able to ¬nd 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 Ei :
y 2 = x3 + Ai x + Bi and points Pi mod n.

2. Choose an integer B (perhaps around 108 ) and compute (B!)Pi on Ei
for each i.

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

4. If step 2 succeeds, increase B or choose new random curves Ei and
points Pi and start over.

Steps 2, 3, 4 can often be done in parallel using all of the curves Ei simulta-
neously.
The elliptic curve method is very successful in ¬nding a prime factor p of n
when p < 1040 . Suppose we have a random integer n of around 100 decimal
digits, and we know it is composite (perhaps, for example, 2n’1 ≡ 1 (mod n),
so Fermat™s little theorem implies that n is not prime). If we cannot ¬nd a
small prime factor (by testing all of the primes up to 107 , 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 1040 .
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 ¬eld 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.




© 2008 by Taylor & Francis Group, LLC
193
SECTION 7.1 FACTORING USING ELLIPTIC CURVES

Why does the elliptic curve method work? For simplicity, assume n = pq.
A random elliptic curve E mod n can be regarded as an elliptic curve mod p
and an elliptic curve mod q. We know, by Hasse™s theorem, that
√ √
p + 1 ’ 2 p < #E(Fp ) < p + 1 + 2 p.
√ √
In fact, each integer in the interval (p + 1 ’ 2 p, p + 1 + 2 p) occurs for some
elliptic curve. If B is of reasonable size, then the density of B-smooth integers
in this interval is high enough, and the distribution of orders of random elliptic
curves is su¬ciently uniform. Therefore, if we choose several random E, at
least one will probably have B-smooth order. In particular, if P lies on this
E, then it is likely that (B!)P = ∞ (mod p) (as in the p ’ 1 method, the
main exception occurs when the order is divisible by the square of a prime
near B). It is unlikely that the corresponding point P on E mod q will satisfy
(B!)P = ∞ (mod q). (If it does, choose a smaller B or use the techniques
of Section 6.8 to factor n.) Therefore, when computing (B!)P (mod n), we
expect to obtain a slope whose denominator is divisible by p but not by q.
The gcd of this denominator with n yields the factor p.
In summary, the di¬erence between the p ’ 1 method and the elliptic curve
method is the following. In the p ’ 1 method, there is a reasonable chance
that p ’ 1 is B-smooth, but if it is not, there is not much we can do. In the
elliptic curve method, there is a reasonable chance that #E(Fp ) is B-smooth,
but if it is not we can choose another elliptic curve E.
It is interesting to note that the elliptic curve method, when applied to
singular curves (see Section 2.10), yields classical factorization methods.
First, let™s consider the curve E given by y 2 = x2 (x + 1) mod n. We showed
in Theorem 2.31 that the map
x+y
(x, y) ’
x’y
is an isomorphism from Ens = E(Zn )\(0, 0) to Z— . (Actually, we only showed
n
this for ¬elds. But it is true mod p and mod q, so the Chinese Remainder
Theorem allows us to get the result mod n = pq.) A random point P on
Ens corresponds to a random a ∈ Z— . Calculating (B!)P corresponds to
n
computing a1 ≡ aB! (mod n). We have (B!)P = ∞ (mod p) if and only if
a1 ≡ 1 (mod p), since ∞ and 1 are the identity elements of their respective
groups. Fortunately, we have ways to extract the prime factor p of n in both
cases. The ¬rst is by computing the gcd in the calculation of a slope. The
second is by computing gcd(a1 ’ 1, n). Therefore, we see that the elliptic
curve method for the singular curve y 2 = x2 (x + 1) is really the p ’ 1 method
in disguise.
If we consider y 2 = x2 (x + a) when a is not a square mod p, then we get
the classical p + 1 factoring method (see Exercise 7.2).
Now let™s consider E given by y 2 = x3 . By Theorem 2.30, the map
x
(x, y) ’
y




© 2008 by Taylor & Francis Group, LLC
194 CHAPTER 7 OTHER APPLICATIONS

is an isomorphism from Ens = E(Zn ) \ (0, 0) to Zn , regarded as an additive
group. A random point P in Ens corresponds to a random integer a mod
n. Computing (B!)P corresponds to computing (B!)a (mod n). We have
(B!)P = ∞ (mod p) if and only if (B!)a ≡ 0 (mod p), which occurs if and
only if p ¤ B (note that this is much less likely than having p ’ 1 be B-
smooth). Essentially, this reduces to the easiest factorization method: divide
n by each of the primes up to B. This method is impractical if the smallest
prime factor of n is not small. But at least it is almost an e¬cient way to
do it. If we replace B! by the product Q of primes up to B, then computing
gcd(Q, n) is often faster than trying each prime separately.




7.2 Primality Testing
Suppose n is an integer of several hundred decimal digits. It is usually
easy to decide with reasonable certainty whether n is prime or composite.
But suppose we actually want to prove that our answer is correct. If n is
composite, then usually either we know a nontrivial factor (so the proof that
n is composite consists of giving the factor) or n failed a pseudoprimality test
(for example, perhaps an’1 ≡ 1 (mod n) for some a). Therefore, when n
is composite, it is usually easy to prove it, and the proof can be stated in
a form that can be checked easily. But if n is prime, the situation is more
di¬cult. Saying that n passed several pseudoprimality tests indicates that n
is probably prime, but does not prove that n is prime. Saying that a computer

checked all primes up to n is not very satisfying (and is not believable when n
has several hundred digits). Cohen and Lenstra developed methods involving
Jacobi sums that work well for primes of a few hundred digits. However, for
primes of a thousand digits or more, the most popular method currently in use
involves elliptic curves. (Note: For primes restricted to special classes, such
as Mersenne primes, there are special methods. However, we are considering
randomly chosen primes.)
The elliptic curve primality test is an elliptic curve version of the classical
Pocklington-Lehmer primality test. Let™s look at it ¬rst.


PROPOSITION 7.1

Let n > 1 be an integer, and let n ’ 1 = rs with r ≥ n. Suppose that, for
each prime |r, there exists an integer a with

(n’1)/
an’1 ≡ 1 (mod n) and gcd a ’ 1, n = 1.

Then n is prime.




© 2008 by Taylor & Francis Group, LLC
195
SECTION 7.2 PRIMALITY TESTING

e
PROOF Let p be a prime factor of n and let be the highest power of
(n’1)/ e
dividing r. Let b ≡ a (mod p). Then
e e’1 (n’1)/
≡ an’1 ≡ 1 (mod p) and b
b ≡a ≡ 1 (mod p),
(n’1)/
’ 1, n = 1. It follows that the order of b (mod p) is e .
since gcd a
Therefore, e |p ’ 1. Since this is true for every prime power factor e of r, we
have r|p ’ 1. In particular, √
p > r ≥ n.

If n is composite, it must have a prime factor at most n. We have shown
this is not the case, so n is prime.

REMARK 7.2 A converse of Proposition 7.1 is true. See Exercise 7.3.



Example 7.2
Let n = 153533. Then n ’ 1 = 4 · 131 · 293. Let r = 4 · 131. The primes
dividing r are = 2 and = 131. We have

2n’1 ≡ 1 (mod n) and gcd 2(n’1)/2 ’ 1, n = 1,

so we can take a2 = 2. Also,

2n’1 ≡ 1 (mod n) and gcd 2(n’1)/131 ’ 1, n = 1,

so we can take a131 = 2, also. The hypotheses of Proposition 7.1 are satis¬ed,
so we have proved that 153533 is prime. The fact that a2 = a131 can be
regarded as coincidence. In fact, we could take a2 = a131 = a293 = 2, which
shows that 2 is a primitive root mod 153533 (see Appendix A). So, in a sense,
the calculations for the Pocklington-Lehmer test can be regarded as progress
towards showing that there is a primitive root mod n (see Exercise 7.3).
Of course, to make the proof complete, we should prove that 2 and 131 are
primes. We leave the case of 2 as an exercise and look at 131. We™ll use the
Pocklington-Lehmer test again. Write 130 = 2 · 5 · 13. Let r = 13, so we have
only one prime , namely = 13. We have

2130 ≡ 1 (mod 131) and gcd 210 ’ 1, 131 = 1.

Therefore, we can take a13 = 2. The Pocklington-Lehmer test implies that
131 is prime. Of course, we need the fact that 13 is prime, but 13 is small
enough to check by trying possible factors.

We can compactly record the proof that an integer n is prime by stating
the values of the prime factors of r and the corresponding integers a . We




© 2008 by Taylor & Francis Group, LLC
196 CHAPTER 7 OTHER APPLICATIONS

should also include proofs of primality of each of these primes . And we
should include proofs of primality of the auxiliary primes used in the proofs
for each , etc. Anyone can use this information to verify our proof. We never
need to say how we found the numbers a , nor how we factored r. √
What happens if we cannot ¬nd enough factors of n ’ 1 to obtain r ≥ n
such that we know all the prime factors of r? This is clearly a possibility if
we are working with n of a thousand digits. As in the case of the p’1 factoring
method in Section 7.1, an elliptic curve analogue comes to the rescue. Note
that the number n ’ 1 that we need to factor is the order of the group Z— . If
n
we can use elliptic curves, we can replace n ’ 1 with a group order near n, but
there will be enough choices for the elliptic curve that we can probably ¬nd
a number that can be partially factored. The following is due to Goldwasser
and Kilian [47]. Recall that a ¬nite point in E(Zn ) is a point (x, y) with
x, y ∈ Zn . This is in contrast to the points in E(Zn ) that are in¬nite mod
some of the factors of n and therefore cannot be expressed using coordinates
in Zn . See Section 2.10.


THEOREM 7.3
Let n > 1 and let E be an elliptic curve mod n. Suppose there exist distinct
prime numbers 1 , . . . , k and ¬nite points Pi ∈ E(Zn ) such that

i Pi = ∞ for 1 ¤ i ¤ k
1.
2
k
> n1/4 + 1 .
2. i=1 i

Then n is prime.


Let p be a prime factor of n. Write n = pf n1 with p n1 . Then
PROOF

E(Zn ) = E(Zpf ) • E(Zn1 ).

Since Pi is a ¬nite point in E(Zn ), it yields a ¬nite point in E(Zpf ), namely
Pi mod pf . We can further reduce and obtain a ¬nite point Pi,p = Pi mod p
in E(Fp ). Since i Pi = ∞ mod n, we have i Pi = ∞ mod every factor of n.
In particular, i Pi,p = ∞ in E(Fp ), which means that Pi,p has order i . It
follows that
i | #E(Fp )

for all i, so #E(Fp ) is divisible by i. Therefore,
k

2 2
1/4
¤ #E(Fp ) < p + 1 + 2 p = p1/2 + 1
n < ,
+1 i
i=1
√ √
so p > n. Since all prime factors of n are greater than n, it follows that n
is prime.




© 2008 by Taylor & Francis Group, LLC
197
EXERCISES

Example 7.3
Let n = 907. Let E be the elliptic curve y 2 = x3 + 10x ’ 2 mod n. Let = 71.
Then
2
> 9071/4 + 1 ≈ 42.1.

Let P = (819, 784). Then 71P = ∞. Theorem 7.3 implies that 907 is prime.
Of course, we needed the fact that 71 is prime, which could also be proved
using Theorem 7.3, or by direct calculation.
How did we ¬nd E and P ? First, we looked at a few elliptic curves mod 907
until we found one whose order was divisible by a prime that was slightly
larger than 42.1. (If we had chosen ≈ 907 then we wouldn™t have made much
progress, since we would still have needed to prove the primality of ). In fact,
to ¬nd the order of the curve, we started with curves where we knew a point.
In the present case, E has the point (1, 3). Using Baby Step, Giant Step, we
found the order of (1, 3) to be 923 = 13·71. Then we took P = 13(1, 3), which
has order 71.

For large n, the hardest part of the algorithm is ¬nding an elliptic curve
E with a suitable number of points. One possibility is to choose random
elliptic curves mod n and compute their orders, for example, using Schoof™s
algorithm, until an order is found that has a suitable prime factor . A more
e¬cient procedure, due to Atkin and Morain (see [7]), uses the theory of
complex multiplication to ¬nd suitable curves.
As in the Pocklington-Lehmer test, once a proof of primality is found, it
can be recorded rather compactly. The Goldwasser-Kilian test has been used
to prove the primality of numbers of more than 1000 decimal digits.




Exercises
7.1 Let E be y 2 = x3 ’ 20x + 21 mod 35, and let P = (15, ’4).
(a) Factor 35 by trying to compute 3P .
(b) Factor 35 by trying to compute 4P by doubling twice.
(c) Compute both 3P and 4P on E mod 5 and on E mod 7. Explain
why the factor 5 is obtained by computing 3P and 7 is obtained by
computing 4P .

7.2 This exercise shows that when the elliptic curve factorization method is
applied to the singular curve y 2 = x2 (x+a) where a is not a square mod
a prime p, then we obtain a method equivalent to the p + 1 factoring
method [134]. We ¬rst describe a version of the p + 1 method. Let p be
an odd prime factor of the integer n that we want to factor. Let t0 = 2
and choose a random integer t1 mod n. De¬ne tm by the recurrence




© 2008 by Taylor & Francis Group, LLC
198 CHAPTER 7 OTHER APPLICATIONS

relation tm+2 = t1 tm+1 ’ tm for m ≥ 0. Let β, γ be the two roots of
f (X) = X 2 ’ t1 X + 1 in Fp2 . Assume that t2 ’ 4 is not a square in Fp ,
1
so β, γ ∈ Fp . Let sm = β m + γ m for m ≥ 0.
Show that β m+2 = t1 β m+1 ’ β m for m ≥ 0, and similarly for γ.
(a)
Show that sm+2 = t1 sm+1 ’ sm for all m ≥ 0.
(b)
Show that tm ≡ sm (mod p) for all m ≥ 0.
(c)
Show that β p is a root of f (X) (mod p), and that β p = β. There-
(d)
fore, γ = β p .
(e) Show that β p+1 = 1 and γ p+1 = 1.
(f) Show that tp+1 ’ 2 ≡ 0 (mod p).
(g) Show that if p + 1|B! for some bound B (so p + 1 is B-smooth) then
gcd(tB! ’ 2, n) is a multiple of p. Since there are ways to compute
tB! mod n quickly, this gives a factorization method.
We now show the relation with the elliptic curve factorization method.
Consider a curve E given by y 2 = x2 (x + a) mod n, where a is not a
square mod p. Choose a random point P on E. To factor n by the
elliptic curve method, we compute B!P . By Theorem 2.31, P mod p

corresponds to an element β = u + v a ∈ Fp2 with u2 ’ v 2 a = 1.
(h) Show that β is a root of X 2 ’ 2uX + 1.
(i) Show that B!P = ∞ mod p if and only if β B! = 1 in Fp2 .
(j) Let t1 = 2u and de¬ne the sequence tm as above. Show that
B!P = ∞ mod p if and only if p divides gcd(tB! ’ 2, n). Therefore,
the elliptic curve method factors n exactly when the p + 1 method
factors n.
7.3 (a) Show that if n is prime and g is a primitive root mod n, then a = g
satis¬es the hypotheses of Proposition 7.1 for all .
(b) Suppose we take r = n ’ 1 and s = 1 in Proposition 7.1, and
suppose that there is some number g such that a = g satis¬es the
conditions on a for each . Show that g is a primitive root mod
n. (Hint: What power of divides the order of g mod n?)
7.4 The proof of Theorem 7.3 works for singular curves given by a Weier-
strass equation where the cubic has a double root, as in Theorem 2.31.
This yields a theorem that uses Z— , rather than E(Zn ), to prove that n
n
is prime. State Theorem 7.3 in this case in terms of Z— . (Remark: The
n
analogue of Theorem 7.3 for Zn is rather trivial. The condition that
Pi is a ¬nite point becomes the condition that Pi is a number mod n
such that gcd(Pi , n) = 1 (that is, it is not the identity for the group law
mod any prime factor of n). Therefore i Pi = ∞ translates to i Pi ≡ 0
(mod n), which implies that i ≡ 0 (mod n). Since i is prime, we must
have n = i . Hence n is prime.)




© 2008 by Taylor & Francis Group, LLC