Elliptic

Lecture 9

curves12ᵗʰ July 2024

Lecture 8E

q pepp.im

axtbxtc.CH abice Fgysmooth0 in Fg

On E Fx

EFI

again aFor P

group structure

byX3

X a x

y

Pa

13 we

1

93

If P P satisfy

Thal

3

ELF

xs 93

9 Xx

HE

where

Check

definedefineP3 P Pz

xz.ba
xz

can

x

so

does Ps

is

a

group

FaitorizationnintegerofApplication

1

Fact 1

mod n

a

can

be computed

operation
2
fast loszk

Fact 2gedlaibl
abcan be computed

fast via Euclidean

algorithm

21082 261 operations

Pollard's algorithm
Idea

A number m iscalled B powersmooth
if all primelponent diffiff

Assume pl n and p 1 is productsmoothcalledsmallofprimesB smoothCompute

1in I
gedla
g

K products of small prime powersaIfffümption P I 1K

Runtime

OCB log B 10841

pig

B

mod

p

compare to OCR

Lenstra's elliptic

factorization

carve

TECH

es fait method

Pollard's als

Ep
a
calc

gedla

ELF

ms

mod p

KP

O

mod P

1 n

calc

KP

modn

T

T
works ifworks if P l is smoothisheuristic

Ptt P

e

PHP

ELF

is distributed

Hbxte

Pick aandsmoothwell that this is highly
likelyECMiden
1

ECFpll

a

carve

E

PointPEE 2 2e.s.FI Es

bist

148

4. Cubic Curves over Finite Fields

with each ki either 0 or 1. As before, we can do this with r ≤ log2 k. Next
we compute
P0 = PP1 = 2P0 = 2PP2 = 2P1 = 22 P
P3 = 2P2 = 23 P
..
..
.
.
Pr = 2Pr−1 = 2r P.

For this write
K

E

KP

Ea Pi

2

Finally we calculate

calculatekP = (sum of Pi ’s for which ki = 1).
to
2 TryThis allows us to compute kP in fewer than 2 log2 k steps of doubling andadding points.
Note, however, that we do not want to compute the coordinates of kP
as rational numbers, because the numerators and denominators would haveapproximately k 2 digits. Even for relatively small values of k, such as
k = 41!, this leads to numbers with more digits than there are elementary
particles in the known universe. So it is much better to perform all computations modulo n.
But n is not prime, so how can we use the formulas for addition anddoubling? Let’s consider the problem of adding two points Q1 = (x1 , y1 )and Q2 = (x2 , y2 ), where x1 , y1 , x2 , y2 are integers modulo n and we wantto perform all computations modulo n. Our formula for Q3 = Q1 + Q2 says
that

Fxmpeifx.tk

x3 = λ2 −x1 −x2

andy3 = −λx3 −(y1 −λx1 ),where λ =y2 − y1.
x2 − x1

The difficulty lies in computing λ, because the ring Z/nZ is not a field, so
x2 − x1 might not have an inverse. When we try to compute the inverseof x2 − x1 modulo n, there are three possible outcomes:(1)

gcd(x2 − x1 , n) = 1 In this case x2 − x1 has an inverse in Z/nZ,
so we can calculate Q3 modulo n. (Note that if gcd(a, n) = 1, then an
adaptation of the Euclidean algorithm gives a solution to the equationax ≡ 1 (mod n). So if the inverse exists, then there is a fast way to findit; see Exercises 4.18 and 4.24.)

4.4. A Factorization Algorithm Using Elliptic Curves

149

(2)

1 < gcd(x2 − x1 , n) < n In this case we cannot find Q3 , but wedon’t care because the integer gcd(x2 − x1 , n) is a non-trivial factor
of n. So the algorithm can be terminated here.

(3)

gcd(x2 − x1 , n) = n If this case occurs, then we have been very
unlucky. We could try a smaller value of k, or just go back to thebeginning and choose a new curve.

Similarly, to double a point Q = (x, y) modulo n, we need to computethe ratio
2x2 + 2ax + b
f ′ (x)=(mod n).
λ=2y2ySo we get the same three alternatives: either we can compute 2Q modulo n,
or we get a non-trivial factor of n, or gcd(y, n) = n and we have to start witha new curve.
Lenstra’s elliptic curve factorization is summarized in Table 4.2. The
description includes all of the essential underlying features of the algorithm,
although in practice there are many ways to make it more efficient.
We illustrate Lenstra’s algorithm by factoringEyn = 1715761513.

Let n ≥ 2 be a composite integer to be factored.

Step 1: Check that gcd(n, 6) = 1 and that n is not a perfect power.
Step 2: Choose random integers b, x1 , and y1 modulo n.
Step 3: Set P = (x1 , y1 ) and c ≡ y12 − x31 − bx1 (mod n).
Step 4: Let E be the elliptic curve E : y 2 = x3 + bx + c.

Step 5: Loop d = 2, 3, 4, . . . up to a specified bound dmax .
Step 6: Compute Q = dP (mod n) and set P = Q.
Step 7: If the computation in Step 6 fails,
then we have found a divisor g > 1 of n.
Step 8: If g < n, then success, return the value of g
Step 9: If g = n, go to Step 2 to pick a new curve and point.
Step 10: Increment d and, if d ≤ dmax , loop again at Step 5.
Step 11: Go to Step 2 to pick a new curve and point.

Table 4.2: Lenstra’s elliptic curve factorization algorithm

RuntimePE.EE

O explosipilostalpf

150

4. Cubic Curves over Finite Fields

The first thing to check is that n is not prime. Using the square-and-multiply
scheme described earlier, we easily calculate that
21715761512 ≡ 114094409(mod 1715761513).

Applying Fermat’s little theorem, this proves that n is not prime, so now wesearch for a factor.
The first step of Lenstra’s algorithm says to check that n is not a perfect
power. Using a calculator, we compute each of
√

n,

√
3

n,

√
4

n,

√
5

√
n, . . . , 31 n ≈ 1.9855.

None of them are integers, so n is not a perfect power.
Step 2 says to choose random integers b, x1 , and y1 modulo n. We willtake
x1 = 2 and y1 = 3, so P = (2, 3).
For b we will use various values until we find one that works, and for a given b,
we take c = 1−2b. Also, to make it clearer what’s happening as the algorithm
progresses, we write Pd for the point computed in Step 6 during the d’th loop.
Thus
Pd = dPd−1 = · · · = d!P1 .
Let’s start with b = 1 and c = −1, so we are looking at the curve andinitial point
C : y 2 = x3 + x − 1 and

P = P1 = (2, 3) ∈ C.

We’ll take dmax = 20, so we iterate the d-loop from Step 5 to Step 10, withd = 2, 3, . . . , 20. The points that we find are listed in Table 4.3.
So now we know that on the curve y 2 = x3 +x−1 considered modulo n =1715761513, the point P = (2, 3) satisfies
20!P = 2432902008176640000(2, 3) = (693588502, 858100579).
What does this tell us about the factors of n? Nothing! The whole point of
Lenstra’s algorithm is that it gives us a factor of n precisely when the addition
law breaks down. So if we are actually able to compute d!P (mod n), thenwe have to continue with either a larger multiplier d or a new point P andcurve C.
So suppose we stick with this point and curve and take d up to 50? Thenwe find that

4.4. A Factorization Algorithm Using Elliptic CurvesdPd
1(2, 3)
2 (524260463, 1437744601)
3 (1580374945, 1281688384)
4 (102166583, 726409659)
5 (1230754737, 656248933)
6 (1439423743, 261453828)
7 (649350388, 251146533)
8 (850659306, 148388675)
9 (859697522, 1168641628)
10 (1393637669, 651726681)

151

d
Pd
11 (535090466, 120781551)
12 (621168269, 1626584297)
13 (1562301880, 1546127470)
14 (1506757996, 1569723892)
15 (1234029292, 1672539306)
16 (1276800395, 664055804)
17 (1547160202, 159566783)
18 (495807207, 511034411)
19 (1226239889, 1164547094)
20 (693588502, 858100579)

Table 4.3: An example of factoring using elliptic curves
P50 = 50!P = (321131143, 586731948)(mod 1715761513).

This doesn’t help, so maybe it’s time to try a new curve. We stick with thepoint P = (2, 3), but now we take b = 2 and c = −3, and we compute up
to dmax = 20. Again we hit no obstacles to computing 20!P modulo n, nor
is there a problem with b = 3 or b = 4. But when we try b = 5, we hit the
jackpot. Everything goes smoothly as we compute up to
16!P = (962228801, 946564039)(mod 1715761513)
on the curvey 2 = x3 + 5x − 9.

But see what happens when we try to compute 17!P . Letting
Q = 16!P = (962228801, 946564039),
we have to compute 17Q, which we do via the double-and-add formula
17!P = 17Q = 2 · 2 · 2 · 2 · Q + Q.
First we compute 2i Q modulo n for i = 0, 1, 2, 3, 4,
Q = (962228801, 946564039)
2Q = (731126553, 1349251536)
4Q = (731200636, 806528011)
8Q = (108793287, 1488256803)
16Q = (505708443, 718251590).

152

4. Cubic Curves over Finite Fields

Then to compute 17Q, we need to add Q to 16Q. This involves finding theinverse, modulo n, of the difference of the x-coordinates of Q and 16Q, so
we need to invertx(16Q) − x(Q) = 505708443 − 962228801 = −456520358

modulo n.

But when we use the Euclidean algorithm to compute the gcd of this quantity
and n, we find that!
"gcd x(16Q) − x(Q), n = gcd(−456520358, 1715761513) = 26927.

This gives a non-trivial factor of n, and indeed in this case it gives the complete prime factorization of n,n = 1715761513 = 26927 · 63719.
With hindsight, we can see why this choice of elliptic curve managed tofactor n. The curve C : y 2 = x3 + 5x − 9 has the property that#C(F26927 ) = 24 · 32 · 11 · 17 and#C(F63719 ) = 22 · 3 · 5303.

So 17!P̃ = Õ in C(F26927 ), since the order of the group C(F26927 )
divides 17!, but not surprisingly, we have 17!P̃ ̸= Õ in C(F63719 ), since
the orders of most points in C(F63719 ) are multiples of 5303.
Of course, as with the example that we did for Pollard’s p − 1 algorithm,
there is no need to use elliptic curves to factor the comparatively small number n = 1715761513. Our aim is simply to illustrate the basic operation of
Lenstra’s algorithm.

Application 2
4.5 Elliptic Curve Cryptography

Sisnatines

The 1970s saw a revolutionary advance in the field of cryptography with
the introduction of public key cryptosystems by Diffie, Hellman, Merkle,
Rivest, Shamir, Adelman, and others. A cryptosystem allows two parties,
typically called “Bob” and “Alice”, to exchange information over an insecure communication channel in such a way that their adversary, “Eve”, isunable to determine the information. Mathematically, one may view a basic
cryptosystem as an injective function
f : {messages} −→ {encrypted messages}.
Bob encrypts his message m by computing c = f (m) and sending the valueof c to Alice, who decrypts the message by computing

A

Ü

B

RSA Mpg
metd

A.im
mmod
ein
f
m

ÄÄ

4.5. Elliptic Curve Cryptography
f

−1

153

(c) = f−1!
"
f (m) = m.

all

In classical private key cryptosystems, anyone who knows how to computethe function f is also easily able to compute f −1 . So it is essential that theprivate key, which is the function f , be a closely guarded secret known only
to Bob and Alice. In particular, before they can communicate securely, Bob
and Alice need to agree on a secret key f that is unknown to Eve.
But suppose that Bob and Alice have never met, and that their only meansof communication is via email or text messaging. Even if their personal
adversary Eve doesn’t have the resources to monitor their communications,
there are likely to be other agencies that do. Public key cryptography solves
this problem. In a public key cryptosystem, Alice can publish her encryption
key f , and despite the fact that Eve and a host of criminal enterprises andinitialed agencies know Alice’s public encryption key f , they are unable tocompute the inverse function f −1 required to decrypt messages.
It was a brilliant idea to conceive that public key cryptography might bepossible, as Diffie and Hellman did in 1976, but even knowing the concept,
it’s far from clear how one might actually construct a public key cryptosystem. Indeed, the Diffie–Hellman paper did not give an example. Various public key cryptosystems have been proposed, and many broken, over the subsequent decades. The best known, which you’ve probably seen, is the RSA
system. In this system, Alice’s public key is a large number N that is a productof two large primes, N = pq, and it is believed that in order to decrypt messages, Eve needs to find p and q. (For a brief reminder of how RSA works, see
Exercise 4.25.) So one says that the security of RSA relies on the difficulty offactoring large numbers. The most powerful factorization method currently
known is called the number field√sieve. The time that it takes to factor N is3
(more-or-less) proportional to ec log N for a small constant c.5 At present, it
is considered infeasible to factor numbers N that satisfy N ≥ 22048 ≈ 10617 .
Other public key cryptosystems rely on the difficulty of the so-called discrete logarithm problem (DLP), which asks the following: Let p be a prime,and let a and b be non-zero numbers modulo p.
DLP: Find an integer m that solves the congruence am ≡ b (mod p).
RSAET

It is clear why this is called a logarithm problem, since if we didn’t work
modulo p, then m would simply be the logarithm of b to the base a. If p is5

If the two prime factors of N = pq are of approximately the same size, then the number
field sieve is faster than the elliptic curve factorization method described in Section 4.4. But
if p is significantly
smaller than q, then the elliptic curve method may be faster, since it takes√c log psteps to factor N .
roughly e

3072

256 bit Keya malN

RIA

Earl

DiffiePrivatePublicHellman key
PrivateB

piga

A gamodp

modp_

exchangebB

gbmodp

Ab

modp

154

4. Cubic Curves over Finite Fields

large, this is a hard problem, with the best solution method (called the index
calculus
for reasons that we do not discuss) taking time roughly proportional√3
to ec log p . So as with RSA, DLP-based public key cryptosystems generally
use numbers satisfying p ≥ 22048 . See Exercise 4.27 for a brief descriptionof a DLP-based system called Elgamal.
Our modest goal in this section is to discuss how public key cryptosystems
can be created using a hard problem on elliptic curves, and to explain why
these elliptic curve systems appear to have practical advantages over RSA
and DLP cryptosystems. This not being a text on cryptography, we do notwant to enter too deeply into the details, and we acknowledge that we will
be sweeping under the rug a great number of important issues that affect the
security of such systems. There are many texts, such as [24] and [27], where
the interested reader can learn more about public key cryptography in general,and elliptic curve cryptography in particular.
The first step is to note that there is a Fürversion of the (discrete) logarithm
problem in any group. Thus if G is a given group and a, b ∈ G are elementsof G, we may ask for an exponent m solving the formula am = b in thegroup G. Taking G = F∗p , the multiplicative group of the field Fp , gives the
DLP described earlier. Taking G = R∗ (and allowing m ∈ R) gives classical logarithms that have been studied since the seventeenth century. And as
you have undoubtedly guessed, if we take G = C(Fp ) to be the group ofmod p points on an elliptic curve, then we have the elliptic curve discrete logarithm problem, which is abbreviated as the ECDLP. Since the group law onan elliptic curve is written additively, the ECDLP in C(Fp ) is the following:6
ECDLP: Given P, Q ∈ C(Fp ), find an integer m so that mP = Q.
Example 4.10. Consider the elliptic curve
C : y 2 = x3 + x2 + x + 1 over the fieldF97 .

The points P = (7, 20) and Q = (17, 46) are in C(F97 ). The ECDLP asks
for an integer m such that mP = Q. One way to solve this problem is to compute 2P, 3P, 4P, . . . until eventually finding that 47P = Q. A faster method
is to use what is called a “collision algorithm.” Here one makes two lists,
say P, 2P, 3P, . . . and Q − 10P, Q − 20P, Q − 30P, . . . , until finding a pointthat appears on both lists, say aP = Q − 10bP . Then (a + 10b)P = √Q, so
we can take m = a + 10b. (Here we choose 10 because 10 is close to 97.)Thus
6

We will always assume that P and Q are chosen so that there is such an m.

4.5. Elliptic Curve Cryptography155

P = (7, 20), 2P = (71, 70), 3P = (17, 51), 4P = (69, 40),
5P = (52, 75), 6P = (84, 26), 7P = (8, 87), . . . ,Q − 10P = (1, 2), Q − 20P = (61, 96), Q − 30P = (80, 93),

Q − 40P = (8, 87), Q − 50P = (17, 46), . . . .

Looking at the lists, we see the collision 7P = (8, 87) = Q − 40P , so
47P = Q.
√In general working over Fp , one takes n to be approximately p andmakes lists kP and Q − nkP for k = 1, 2, 3 . . . . Under suitable hypotheses,
one can show that a collision will occur for some k < n; see Exercise 4.28. So√
using the collision method only requires about 2 p additions on the curve,
as opposed to the naive method of computing P, 2P, 3P, . . . until finding Q,
which on average takes 12 p additions. For more about collision algorithms,
including a brilliant idea due to Pollard that achieves the same result without
having to store long lists of data, see [24, §§2.7, 5.4, 5.5].

wem

The Elgamal cryptosystem, and another important cryptographic construction called Diffie–Hellman key exchange (Exercise 4.26), can be formulated using the discrete logarithm problem in almost any group. So why
should we use an elliptic curve group C(Fp ), where the group law is socomplicated, rather than the multiplicative group F∗p , where the group law issimply multiplication modulo p? The answer lies in the differing degrees ofdifficulty of the discrete logarithm problem in different groups. As an extreme
example, consider the discrete logarithm problem in the cyclic group Zn .
Solving ma ≡ b (mod n) for m using the Euclidean algorithm takes atmost 2 log n steps, so it is very easy to find m even if n is enormous. On
the other hand, as we noted earlier, solving the DLP in F∗p currently takes√
3around ec log p steps, so is infeasible if p > 22048 .
In the mid-1980s, Neal Koblitz and Victor Miller (independently) suggested that the discrete logarithm problem on elliptic curves might bemuch more difficult than on F∗p . Using a collision algorithm as described in
Example 4.10,# one can solve the discrete logarithm problem in any group G
in roughly 2 o(G) steps; cf. Exercise 4.28. And despite decades of study,
no one has found a better algorithm to solve the ECDLP on general elliptic
curves, although faster methods are known in certain special cases. So as√of 2015, the best known algorithms take a small multiple of p to solve the
√
ECDLP
in
C(F
).
And
if
p
is
large,
thenp steps take much longer than
p
√
3p
c
the e
steps required to solve the DLP in F∗p using the index calculus. The
upshot is that instead of using a prime p > 22048 , it suffices for ECDLP-based
cryptosystems to take roughly p > 2200 .

156

4. Cubic Curves over Finite Fields

Why does this matter? Suppose that Alice wants to put her public key
on her credit card, or that an airline wants to use a public key in the bar
code on your printed airline ticket, or that a manufacturer wants to put apublic key on a computer chip in your car and your refrigerator and yourmicrowave.7 On such constrained devices, every bit stored and every bittransmitted is expensive. An RSA key, or an Elgamal key using F∗p , requires
around 2000 bits, while an Elgamal key using an elliptic curve C(Fp ) requires
only around 200 bits. That’s a huge savings, and explains why elliptic curve
cryptography is used in many real-world situations.
What might make us believe that the ECDLP in C(Fp ) is harder than the
DLP in F∗p ? One explanation comes from comparing the natural homomorphisms
Rp∗ −→ F∗p and C(Q) −→ C(Fp ),where Rp = {a/b ∈ Q : p ! b} is the local ring that we used in Section 2.4.
The index calculus, which is the strongest method known for solving the DLP,
uses this homomorphism and the fact that Rp∗ is infinitely generated withmany “small” generators. By way of contrast, Mordell’s theorem tells us thatthe group C(Q) is finitely generated, so it appears that an elliptic curve index
calculus cannot even get started.
Unfortunately, the preceding paragraph must be viewed as a mix of philosophy and marketing! It’s a disconcerting fact that we currently don’t know, inthe sense of having proofs, that integer factorization or the DLP or the ECDLP
is hard in an appropriately rigorous sense. For all that anyone knows, it may
be possible to factor N in time proportional to a small power of log N , or tosolve the ECDLP in C(Fp ) in time proportional to a small power of log p.
The question of rigorously classifying which mathematical problems can besolved in polynomial time, which problems require exponential time, andwhich problems lie between, is a fundamental research topic in computerscience and complexity theory.
Finally, we would be remiss without a quick mention of quantum computers, amazing devices that are under development, but which no one knows
when, or even if, will ever be built. What is known is that a working quantum
computer with enough quantum bits will be able to factor N and to solve the
DLP and ECDLP in polynomial time. So quantum computers, if they’re everconstructed, are likely to sound the death knell on the use of elliptic curves incryptography. But it’s unlikely that they, or any other discovery or invention
7

These are all actual real-world applications, although some use something called a digital
signature, rather than a public key cryptosystem.