• Introduction
• Technical Definition
• Elliptic Group
• Continuous Group
• Anticurve
• Finite Fields
• Families of Curves
• When the Cubic Splits
• Norm and Antinorm
• The s Factor
• From Rationals to Integers
• Elliptic Curve Factoring
• Elliptic Curve Cryptography
• Elliptic Curves in Characteristic 2

An elliptic curve can be drawn in the xy plane, but it has nothing to do with an ellipse. An ellipse is the graph of a quadratic equation such as 2x² + 3y² = 11. These were discussed in detail in quadratic forms. In contrast, an elliptic curve is the graph of a cubic equation, such as y² = x³ - 26. In this regard, elliptic curves are (perhaps) poorly named. But that's what they're called, so on we go.

As you explore the properties of elliptic curves, you might wonder how these structures came to be. "How did anybody ever think of that?", you might ask. Well they come from algebraic geometry, as a special case of a more general, abstract shape. In this context, an elliptic curve is a projective nonsingular curve of genus 1, with a base point p₀. We will explore the deep connection to algebraic geometry later on in this book, but for now, That would only serve to confuse. Besides, you don't need an advanced course in algebraic geometry to appreciate the beauty and the power of the elliptic curve.

It would be difficult to overstate the importance of elliptic curves in pure and applied mathematics. They are used in primality testing, factorization, public key cryptography, and the proof of Fermat's last theorem, to name a few. No wonder so much is written about this subject.

Let F be a field, such as the reals, and let a and b be elements of F such that a and b are not both zero. The elliptic curve G, determined by a and b, is the set of points (x,y) such that y² = x³ + ax + b. (The formula is different when F has characteristic 2; I'll get to that later.) I use the letter G because the points of the elliptic curve form a group; we'll see this below.

In addition to the aforementioned relation on F cross F defined by our cubic equation, G includes ω, the point at infinity. Note, ω is the last letter in the Greek alphabet, and is often used for the point at infinity - something beyond the natural world. Thus ω is not in the xy plane. Travel in any direction, out to infinity, and find the point ω. If the xy plane curled up into a sphere, with the origin at the south pole, ω would be the north pole. G needs ω to become a group. In fact ω is the identity element. For this reason, some books refer to this element as O or E.

It is easy to see that two points determine the curve. Start with the equation y² = x³ + ax + b, and substitute in the points x₁,y₁ and x₂,y₂. This gives two linear equations in a and b, so solve for a and b and find the curve. This won't work for x₁,y₁ and x₁,-y₁, since both give the same equation in a and b - so assume the two x coordinates are different. The two points are not simply reflections of each other through the x axis, by negating y. With different x coordinates, you get different coefficients on a, and there is no trouble solving for a and b.

Where does the curve cross the x axis? In other words, when is y equal to 0? This occurs whenever x is a root of the cubic polynomial p(x) = x³ + ax +b. This will depend on the field F. For instance, if p is irreducible over F, then y is never equal to 0.

Suppose p has the root r with multiplicity 3. Thus p = (x-r)³. Expand, and find the term 3rx², which is not present in p. Thus there is no triple root. Actually we need to be a bit careful here. If F has characteristic 3 then p could be x³ - r³, which is (x-r)³. If F has characteristic 3, we require a to be nonzero, so there is no triple root. (A triple root would violate the group structure of G; that's why we try to avoid it.)

Other possibilities are three distinct roots, a root and a double root, or a root and an irreducible quadratic.

When p(x) comes out nonzero, and a square, x can be paired with y or -y. Thus the elliptic curve is symmetric about y = 0. Within the xy plane, the elliptic curve is reflected through the x axis, like a mirror.

Let F = R, the reals, so that the elliptic curve lives in the xy plane. When x approaches positive infinity, y increases as x to the 3/2 power. The curve is more than linear, and less than quadratic. It arcs upward towards infinity, while its lower half, reflected through the x axis, arcs downward towards -infinity.

As x goes negative, p(x) becomes negative, and y² cannot equal a negative number. The curve has a definite left edge where p(x) first equals 0.

Here is a way to visualize the curve. Graph y = p(x), keep only the sections that lie above the x axis, take the square root, and reflect the result through the x axis. This is the elliptic curve in the xy plane.

Given a and b, when is p(x) ≥ 0? If p is monotonically increasing, i.e. a ≥ 0, then p(x) remains positive after its first root, which is its only root. Take the square root and the result is still monotonically increasing, up to infinity.

If p dips down to a local minimum before arcing back up to infinity, i.e. a < 0, it may cross the x axis at 1 2 or 3 places. Use x³ - 3x + b as a model for p. The local maximum is at -1 and the local minimum is at 1. For large b, p crosses the x axis at a low negative number and remains positive thereafter. It bends down and then up again near the y axis, then arcs on up to infinity. Taking the square root doesn't change the overall shape of this cubic curve; it still has a dip just to the right of the y axis.

Next, lower the cubic curve until the local minimum rests on the x axis. This is accomplished by setting b = 2. Take the square root, and the elliptic curve still has one continuous branch, but its local minimum rests on the x axis at x = 1. If we include the reflection, the two halves just kiss each other at x = 1.

Lower the curve some more, by setting b = 0 for example, and there are two separate branches separated by a gap. These range from -sqrt(3) to 0, and from +sqrt(3) to infinity.

Lower b down to -2, and the first branch shrinks to a point at x = -1, where the local maximum just touches the x axis from below. Meantime the second branch has shifted to the right. Smaller values of b cause the first branch to disappear completely, leaving only the second branch.

When y is positive, calculus can be used to differentiate the elliptic curve. In fact it is infinitely differentiable. The first derivative is p′/2y. This will be 0 only when p′ is 0, in at most two places, x = -sqrt(-a/3) if the hump is above the x axis, and x = +sqrt(-a/3) if the dip is above the x axis. These are the local maximum and minimum of the elliptic curve, and they correspond to the local maximum and minimum of p(x).

When y = 0 we have to run the difference quotient by hand. Let r be a root of p(x), and take the limit of sqrt(p(r+h)) over h. Apply l'hopital's rule, giving p′(r+h) over 2sqrt(p(r+h)). If we are not at a local maximum or minimum, the top is nonzero, and the bottom is zero, giving a ratio that approaches infinity. The elliptic curve is perfectly vertical at this point. If we include the reflection, the upper and lower curves meet at this point and form one large smooth branch.

On the other hand, r could be a double root, whence p attains a local minimum at r. Go back to the difference quotient and square it. Since square root is a continuous function, the square root of the limit gives the limit of the original difference quotient. Evaluate p(r+h) over h² using l'hopital's rule. This gives p′(r+h) over 2h, which is still zero over zero, so apply the rule again, giving p′′(r+h) over 2. The limit is 3r, hence the difference quotient approaches sqrt(3r). If r is 0 then p is x² times x-s, where s is some other root. Yet s must also be 0, since p has no squared term. There is no triple root in an elliptic curve, so 3r is nonzero. This looks like a contradiction, a function with a local minimum and a nonzero derivative. However, we must remember that the difference quotient is really a one sided limit. On either side of r, we are evaluating sqrt(p(r+h)) over h. This is positive to the right of r and negative to the left of r. The one sided derivatives are ±sqrt(3r). G strikes the x axis at an angle, and like a mirror, it bounces back up at the same angle, on its way to infinity. So if G has a local minimum, the dip is smooth, unless it rests on the x axis, whence it makes a sharp point similar to the letter V.

The sharp corner described above, that looks like the letter V, causes trouble; it messes up the structure of the group. Thus I will include an additional constraint on a and b:

4a³ ≠ -27b²

This certainly prevents a and b from being 0, which was a previous requirement. It also prevents a from being 0 when F has characteristic 3. Therefore this constraint encompasses the prior constraints.

Suppose r is a root of p(x), and also a root of p′(x). In the reals, this creates the sharp corner on the x axis, which we don't want. The roots of p′ are ±sqrt(-a/3). One of these roots is also a root of p(x). Substitute in for p and find this.

(-a×sqrt(-a))/(3×sqrt(3)) + a×sqrt(-a/3) + b = 0

2/sqrt(27) × a×sqrt(-a) = -b

Square both sides and clear denominators to produce the forbidden relation on a and b. Therefore there is no double root.

Again, we must treat characteristic 3 as a special case. Note that 3x²+a = a, which is nonzero. The "derivative" is always nonzero. If p has a double root at r, the theory of formal derivatives tells us p′ would be divisible by x-r; yet p′ is a constant. There is no double root. For every field F, our constraint forbids a double root.

Let F = C, the complex numbers. For any x, p(x) splits in the complex numbers. In other words, p has 3 complex roots, and these roots are distinct, thanks to the constraint given above. When x is one of these roots, y = 0. Every other value of x produces two values of y, with ± symmetry. It would be difficult to describe this elliptic curve, a 2 dimensional surface swirling about in 4 space, so I'm not going to try. We may investigate certain cross sections later, e.G. when x is real, or pure imaginary. We will explore other fields as well, such as Q and Z/p.

A binary operator turns the points of an elliptic curve G, including ω, into an abelian group. In fact ω is the identity element. Each x³ + ax + b defines its own elliptic curve, and a corresponding elliptic group.

Once again let's start with the reals, to obtain a geometric interpretation. Embed the curve in the xy plane, as we did in the previous section. Given two points on the curve, draw the line connecting them, and extend the line until it intersects the curve in a third point. Reflect this point through the x axis, i.e. replace y with -y. This becomes the sum of the first two points. Clearly this operator is commutative, but is it well defined?

If the two points are reflections of each other through the x axis then the line is vertical, and does not intersect the graph in any other points. In this case, set the sum to ω. In other words, points that are reflections of each other are inverses in G.

Two points that are not reflections exhibit a well defined slope m. Write the line as y = mx+c. Substitute mx+c in y², and move everything to one side, giving a new cubic polynomial q(x), with at most 3 roots. Thus the elliptic curve and the line intersect in at most 3 points, corresponding to the roots of q(x). We already have two roots in hand, the values of x corresponding to the two points we are given. Since q has two roots in the field F, it splits fully over F, and has a third root. By unique factorization in F[x], this third root is well defined. Conversely, let x be any root of q(x), and set y = mx+c. Obviously this point is on the line. Reverse the algebra that built q, and show x,y satisfies y² = x³ + ax + b. The roots of q establish the three points of intersection. The group operator in G is well defined.

There is one case we haven't considered. In an abelian group, an element can be added to itself. How do you add a point on the curve to itself? Use calculus to draw the tangent line, find the other point of intersection, and reflect through the x axis. If the tangent line is vertical, set the sum to ω. See below for more details.

Here are the formulas for the group operator, under any field F. Start with two points p₁ and p₂ on the elliptic curve. We want to compute p₃, the sum of p₁ + p₂.

If p₁ = ω, let p₃ = p₂. If p₂ = ω, let p₃ = p₁. ω is the identity element of G.

If neither summand is ω, let p₁ and p₂ have coordinates x₁,y₁ and x₂,y₂ respectively. If x₁ = x₂ and y₁ (nonzero) = -y₂, let p₃ = ω. This is the vertical line that crosses G in two points, reflections of each other, then extends up to infinity.

If p₁ = p₂, and their common y coordinate is 0, let p₃ = ω. This is the tangent line that is vertical, and meets G at infinity.

With ω as group identity, each point has a unique inverse. The inverse of ω is ω, and the inverse of x,y is x,-y.

At this point p₁ and p₂ have different x coordinates, or they are equal with a nonzero y coordinate. We need to find the slope of the chord or tangent line. Set m = y₂-y₁ over x₂-x₁. (This is the same if we swap p₁ and p₂.) If p₁ = p₂, set m = (3x²+a)/2y. This is the formula you would get from calculus.

For notational convenience, let j = x₁ and let k = y₁. The line is given by the formula y = m×(x-j) + k. This is a subspace of dimension 1 in F cross F. The same line would appear if we swapped p₁ and p₂. The values of j and k would change, but the subspace would remain the same. The points of intersection are the same, and the group operation remains commutative.

Substitute m×(x-j) + k in y² and build the following polynomial. This and subsequent algebra can be verified by this program.

q(x) = x³ - m²x² + (2jm²-2km+a)x + b - j²m² + 2jkm - k²

Since j is a root, use synthetic division to divide out x-j. The remainder is j³+aj+b-k², which has to be 0, since j,k is a point on the elliptic curve. Replace q with the quotient as follows.

q(x) = x² + (j-m²)x + a + jm² + j² -2km

Consider the tangent line first, whence m = (3j²+a)/2k. Substitute for m, clear denominators, and regroup to get this.

(x-j) × (4k²x - a² + 8jk² -6aj² - 9j⁴)

We have another factor of x-j. The double root of q is revealed. (Yes, q can have a double root - although p cannot.) Remove this and solve for x, which will determine p₃.

x₃ = (9j⁴ + 6aj² + a² - 8jk²) / 4k²

x₃ = m² - 2j

With x₁ = x₂ = j, we may write it this way.

x₃ = m² - (x₁+x₂)

There is a problem when F has characteristic 2; m is not well defined. Remember, the tangent formula has a 2 in the denominator. That's why the elliptic curve has a different formula when F has characteristic 2. I'll get to that later.

Next assume p₁ and p₂ are distinct. For notational convenience, let s = x₂ and let t = y₂. Recall the polynomial q(x), after x-j was factored out.

q(x) = x² + (j-m²)x + a + jm² + j² -2km

With s as a root, divide through by x-s. This gives a rather bizarre remainder.

m²×(j-s) - 2km + j² + js + s² + a

Remember that m×(j-s) = k-t, so this becomes:

-(k+t)×m + j² + js + s² + a

It would be comforting to know this is 0. Plug j,k and s,t into the elliptic equation and subtract, giving this.

t² - k² = s³ - j³ + (s-j)a

Divide through by s-j to get this.

(t+k)×m = s² + js + j² + a

This is the aforementioned remainder. Yes indeed, x-s is a root, and when it is factored out of q(x), the quotient is x+j+s-m². Therefore x₃ = m²-j-s, or m²-(x₁+x₂), which is exactly the same formula we saw earlier. It doesn't matter whether p₁ and p₂ are equal or distinct, p₁+p₂ is given by the following formula.

x₃ ← m² - (x₁+x₂)
-y₃ ← y₁ + m*(x₃-x₁)

The last and trickiest part is associativity. Well - not really tricky - it's just algebra - but very tedious. I'm not going to fill up five pages trying to prove it. In fact, the real proof of associativity, the proof that you almost get for free, comes from the definition of an elliptic curve as a projective variety in algebraic geometry, which is many chapters ahead. For now let's just run with it.

The group operator employs addition and subtraction, multiplication and division. If the operands lie in the field F, so does the result. Restrict F to a smaller subfield E, and the same elliptic curve (defined by a and b) establishes a subgroup of the original group, assuming a and b are contained in E.

Under the reals, an elliptic curve builds an uncountable group as x runs to positive infinity. Restrict to the rationals and find a countable subgroup. Intermediate fields, such as the algebraic closure of Q, produce intermediate subgroups.

Recall the geometric definition of the group operator. A line is drawn between two points p₁ and p₂ on the curve, and extended out until it intersects the curve in a third point p₃. Slide p₁ and p₂ along the curve, ever so slightly, and p₃ moves proportionally. The output is a continuous function of the inputs. If p₁ and p₂ merge, the chord becomes the tangent line, and the operator is still continuous. That's the idea; let's prove it with a bit more rigor.

Review the definitions from point set topology. G is a continuous group if the operator * is a continuous map from G cross G into G. Take an open set O in G, or a base open set if you prefer, and the preimage, i.e. all the points a,b such that a*b is in O, forms an open set in G cross G under the product topology. It is often easier to prove continuity pointwise - for any z in O and any a,b such that a*b = z, a is in an open set K, and b is in an open set L, such that K*L lies in O.

Restrict G to a subspace G′, with the subspace topology. An open set O′ in G′ must come from an open set O in G. Select a, b, and z as above, and a lies in K and b lies in L, with K*L in O. It follows that K′ * L′ is in O′, where K′ and L′ are open in the subspace topology. The * operator remains continuous on the subgroup G′. What does this have to do with elliptic curves? If elliptic groups over a field F are continuous, and E is a subfield of F with the subspace topology, then elliptic groups over E are also continuous. Prove continuity for F, and the same is true for all the subfields of F. Start with the largest field, such as the complex numbers, and you prove continuity for the reals, the rationals, the algebraic closure of the rationals, and all other intermediate fields.

Although my primary focus is the complex numbers, the following proof also works for the p-adic numbers, which are based on the rationals, with a quite different topology.

Remember that the underlying space, F cross F, which gives the elliptic curve its topology, is augmented by ω. How does this change the topology?

The metric space F cross F, as C or as p-adic, is locally compact and hausdorff. The introduction of ω represents a compactification of the space. The sets that were open remain open, and in addition to these, for any given r, the points that are farther than r from the origin join with ω to make a new base open set. If the plane curls up to make a sphere, with ω at the north pole, the new base open sets form small open discs about ω, above the arctic circle. As r increases, the disks shrink towards the north pole.

The standard mathematical operators, plus minus times divide, are all continuous functions of R cross R into R. Complex math is based on real math, hence the complex operators, plus minus times divide, are also continuous. If F is p-adic, the operations are once again continuous.

Think of m, the slope of the chord or the tangent line, as a function of p₁ and p₂ in F cross F. If either operand is ω, let m = ω. If p₁ and p₂ are reflections, let m = ω. Thus m is defined across our entire domain. Demonstrate the continuity of m by showing continuity at each input p₁ cross p₂. Take the easy case first, when p₁ and p₂ are in F, and not equal to each other, and not reflections. The function m gives the slope of the line from p₁ to p₂, and remains well defined throughout neighborhoods of p₁ and p₂. Since m consists of standard mathematical operators, m is continuous at p₁ and p₂.

Next assume p₁ = p₂, with a nonzero y coordinate. Let u and v be points on the curve that stray from p₁, but keep them close to p₁. When u = v, use the tangent formula, otherwise use the chord formula. The tangent formula is continuous. If u and v move along the curve in lockstep, equal to each other, passing through p₁, m(u,u) can be held arbitrarily close to m(p₁,p₁). Hold the u,v chords close to nearby tangent lines, and all the chords in our box are close to m(p₁,p₁), and we're done.

Here's the next case - p₁ = p₂, with a zero y coordinate. This is the vertical tangent line. Again, chords are close to tangents, so let's look at nearby tangents. The tangent formula has y in the denominator, so m increases without bound. In fact we can keep m arbitrarily large, simply by keeping y small. This meets the definition of continuity at m(p₁,p₁) = ω.

Let p₁ and p₂ be reflections in F, with the same x coordinate and opposite y coordinates. Near p₁ and p₂, chords have slopes that are infinite, or arbitrarily large. Once again the limit is ω, and m is continuous.

With m continuous, let's move on to the group operator. Let p₁ and p₂ lie anywhere on the elliptic curve, other than ω. The formula for p₃ is based on m and mathematical operators, hence it is continuous across the board - although we need to look at the cases where p₃ = ω. In either the vertical tangent line or the vertical line through reflections, m approaches infinity, hence x₃ = m²-(x₁+x₂) approaches infinity, and y₃ approaches infinity, and p₃ approaches ω. As long as p₁ and p₂ are not ω, the group operator is continuous.

Consider p₁ = p₂ = ω. Points close to ω are high on the elliptic curve. The slope of the chord or tangent line is large, in absolute value, which makes m² large, which makes x₃ large, which pushes p₃ towards ω. Once again we have continuity.

Finally let p₂ = ω, with p₁ somewhere in F cross F. Consider points near ω. For points high on the curve, y increases faster than x. The slope approaches infinity, and the connecting line is practically vertical. This line intersects the curve in a point that is almost the reflection of p₁. Remember that we negate the y coordinate, so the result is arbitrarily close to p₁. The group operator is continuous when either of the two inputs is ω.

That completes the proof. Elliptic groups on complex numbers, or p-adic numbers, or any subfields thereof, are continuous groups.

Let c₁ be the elliptic curve y² = x³ + ax + b over the field F. Extend the field F by i, where i² is a nonsquare in F. The obvious example is the square root of -1 over the reals. The curve y² = x³ + ax + b is valid within the extended field. Build a new curve c₂ based on pairs x,iu where x and u are in F. Given two distinct points, the slope is i times something in F. The new x is in F, and the new y is i times something in F. In the same way, the slope of the tangent line is i times something in F, and the double point has the proper form. c₂ is a valid curve, in fact, a valid subcurve, or subgroup, of c₁ in the extended field.

Each value of x has two points on c₁, or two points on c₂, as x³ + ax + b is a square or a nonsquare respectively. If x is a root of the cubic, that is an exception, defining a point on both curves. In some sense, c₂ is the anticurve, though it is called the outside curve in a later section.

Let F be a finite field with order r. (Remember that r has to be a power of a prime.) Fix a and b, and the resulting elliptic group is a finite abelian group, which is a direct product of cycles.

When plugged into our cubic polynomial, each x in F leads to 0, a square, or not a square. If we believe the distribution is pseudo random, and it probably is, we can expect the elliptic group to have a size near r. The maximum size is 2r+1, when each x produces a valid ±y, and ω is brought in. For instance, y² = x³ + 2x + 1 mod 3 admits 6 solutions, giving an elliptic group of Z/7. The smallest group is of course 1, when there are no solutions to the cubic equation, and we are left with only ω. This is illustrated by y² = x³ + 2x + 2 mod 3. These cases are somewhat pathological. For a random curve and large r, the size of the group will be very close to r. Thus we would not expect one elliptic group to be a proper subgroup of another, one group half as large as the other. Some groups turn out to be isomorphic, as we shall see below.

Let's start with an easy example. Assume r = 2 mod 3, and a = 0. The map x³ is injective and onto, hence x³ + b covers all the values of F. When x³ + b = 0, y = 0. Setting this aside, half the values have two distinct square roots, and the other half have none. Bring in ω, and |G| = r+1.

Is |G| even or odd? Write a finite abelian group as a direct product of prime power cycles. Such a group has even order iff one of its cycles is a power of 2, iff there is an involution, i.e. a group element that is its own inverse. In the elliptic group, an involution has y = 0, hence a solution to the cubic equation. Therefore the group has odd order iff the cubic is irreducible over F.

One root corresponds to the involution in the middle of an even cycle, and three roots come from two even cycles running in parallel. Add any two involutions together and get the third. In the reals, the line connecting these three points is the x axis.

Sometimes elliptic curves can be clumped together into families. Start with the curve x³ + ax + b over F. Let c be any nonzero element of F. Let u = xc² and let v = yc³. Let a′ = ac⁴ and let b′ = bc⁶. Verify that v² = u³ + a′u + b′. In other words, each point on the first curve maps to a point on the second. Set d = 1/c to show this map is reversible. Therefore the two groups have the same order.

There is a catch; is the second elliptic curve valid? Assume 4a³ + 27b² is nonzero. Multiply through by c¹², and 4a′³ + 27b′² is nonzero. Yes, the implied curve is valid.

Is this map a group isomorphism? Everything is ok when either of the two summands is ω, so let the sum equal ω. Thus the two summands are inverses, exhibiting y and -y. The map creates inverse points, yc³ and -yc³, so we're ok.

If m is the slope between two points, or the slope of the tangent line, then m is multiplied by c in the second curve. Sure enough, x₃ is multiplied by c², just like x₁ and x₂, and y₃ is multiplied by c³. The map is a group isomorphism.

If a and b define a valid curve, then ac⁴ and bc⁶ give the same group. Groups clump together by the nonzero fourth powers of F. Set c to the fourth root of 1 (if F permits), and you can negate b without changing the group.

If F has order 307, or anything 3 mod 4, each square is automatically a fourth power. Groups clump together in families of size 153 for a = 1, or a = 2 (2 is a nonsquare mod 307), and various values of b. Of course a could be 0, whence the size of the group is determined by the residue of b as a sixth power. These families have size 51. Each entry in the second column in the table below is divisible by 51, and most are divisible by 153.

If everything in F is a fourth power and a sixth power, like the complex numbers, then a can be set to 1, or a = 0 and b = 1.

I wrote a small C program to find the order of all elliptic groups mod p. For grins I ran it on p = 307. Here is the distribution of the groups by order. Note that a group of order 289 could be Z/289, or Z/17 * Z/17. I didn't separate the groups by structure.

Let's analyze an elliptic group with b = 0, mod 307, or any other finite field that is 3 mod 4. Remember that squares and fourth powers are the same. Thus there are only two distinct groups: y² = x³ + x, and y² = x³ - x. (I'm using -x because -1 is a nonsquare mod p.)

When x = 0 then y = 0, so consider the nonzero values of x. Consider first the squares, and then the nonsquares.

The squares are squared, giving the fourth powers, but that is the same set as the squares. Add or subtract 1 to give a set S. Partition S into S₁ (nonsquares) and S₂ (squares). Each of these values is multiplied in turn by some square x. Thus there are 2S₂ solutions. We have to be a bit careful here; if the cubic comes out 0 then y and -y are not distinct. This can't happen for x³ + x, as x would have to be 0 or the square root of -1. So 2S₂ it is. However, for x³ - x, x could be 1 or -1. Thus 1 yields a singleton value of y = 0. There are 2S₂ solutions (+x), or 2S₂-1 (-x).

Move on to the nonsquares. Square these, and add or subtract 1, and get the same set S, partitioned into S₁ and S₂. These are multiplied by nonsquares, giving 2S₁ solutions. But there could be one more solution, multiplying 0 from S₂ by the nonsquare -1.

Put these together and get 2(S₁+S₂) = 2S solutions. S has size (p-1)/2, so there are p-1 solutions. Bring in 0, and ω, and the group has order p+1, or r+1 for any finite field that is 3 mod 4.

Assume the cubic splits into x-r times x-s times x-t. What is the size of the elliptic group? We're going to look at every x, which is the same as looking at every x+c. Let c be the average of r and s. Relabel the roots, and the product is now x-s times x+s times x-t.

Note that s cannot be 0, else the cubic has a double root.

Assume t = 0, giving x³ - s²x. If p = 3 mod 4, |G| = p+1, as we saw earlier. So let p = 1 mod 4.

Relabel s as c²u, where u is 1, or your favorite nonsquare. Looking through every x is like looking through every c²x. Pull out c⁶ and find x³ - u²x. In other words, we can normalize s down to 1 or u. Groups come in only 2 sizes here: G = x³ - x and H = x³ - u²x. Both groups have the origin and ω. G has±1,0 and H has ±u,0. Beyond this there is a correspondence. Suppose x does not come out a square in G. Write y²u = x³ - x. Multiply through by u³. Thus (yu²)² = (ux)³ - u²(ux). When x fails in G, ux succeeds in H. Similarly, if x succeeds in G then ux fails in H. Put this together and |G| and |H| average out to p+1.

Next assume t is nonzero. Normalize s down to 1 or u, where u is your favorite nonsquare. The formula is (x²-1) * (x-t) or (x²-u²)*(x-t). When x = 0 we have 2 solutions, iff t is a square. The size of the group bounces all around with various values of t, but is always a multiple of 4. This because the cubic polynomial has 3 roots, producing 3 involutions in the group.

Let F be a base field, and let K/F be a field extension of dimension 2, so that K is F adjoin the square root of some d in F. Conjugation (replacing d with -d) is a field automorphism, and it induces a group automorphism on the elliptic group over K, fixing the elliptic subgroup over F. If z is an elliptic point, call it real if its x and y components live in F. Call it imaginary if its components are something in F times the square root of d. If d = -1, then real and imaginary have their usual connotations. As mentioned above, the real points form a real subgroup of the larger elliptic group. Another subgroup consists of points whose x coordinate is real and y coordinate is imaginary. Verify that this is closed under the elliptic operator. I call this the outside group because it looks like x,0 | 0,y*sqrt(d) - with the nonzero coordinates on the outside. (This was called the anticurve earlier.)

Let a and b come from F. In other words, a and b are real. For a fixed real x, let v = x³ + ax + b. The real group has solutions iff v is a square in F; the outside group has solutions iff v is a nonsquare (or v = 0). These two groups typically do not have the same order. For v nonzero, the two solutions wind up in the real group or the outside group. For v = 0 there is one solution, but it appears in both groups. Bring in ω, and the order of the real group + the order of the outside group is 2r+2.

Let z be a point on the elliptic curve. The conjugate of z, z, is obtained by conjugating the x and y components. Since conjugation is a field automorphism, the result is still on the elliptic curve over K.

Let the norm of z be z+z, using the elliptic group operator. Let the antinorm of z be z-z (z + the inverse of the conjugate of z). Since the group is abelian, the norm of z is fixed by conjugation. Such a point has to be real. Norm is a group homomorphism from the elliptic group into the real group.

Take the conjugate of the antinorm of z and get z-z, which is the inverse of the antinorm of z. Thus the antinorm is inverted by conjugation. This puts the antinorm in the outside group. Antinorm is a group homomorphism.

Norm doubles the real group, and antinorm doubles the outside group.

Norm maps the outside group to ω, and antinorm maps the real group to ω. In fact these are the kernels of the respective homomorphisms.

Since a and b are real, each real x leads to the square root of a real number. The result is 0, or two points in the real group, or two points in the outside group. Bring in ω, and the size of the real group, plus the size of the outside group, is 2r+2, where r = |F|.

The size of the entire elliptic group over K is kernel times quotient. The kernel of the norm homomorphism is the outside group, and the image is the real group or perhaps half the real group. It is at least half the real group, since the real group is doubled by the norm. Thus |G| is the product of two numbers, whose sum is 2r+2, or perhaps it is half this product. I made a statistical argument earlier in this chapter, that |G| is going to be pretty close to |K|. It won't be half of |K|, so |G| is almost certainly the product of these two numbers.

Let a = 0 and let r (the size of F) be 2 mod 3. The real group has size r+1, as described earlier. The outside group also has size r+1. Therefore the entire group has size (r+1)².

The same analysis holds if b = 0 and r = 3 mod 4. Again the real and outside groups have size r+1, and |G| = (r+1)².

You can extend this field, if you like, by another square root, from K to L, and perform the above analysis all over again for the new extension. The two groups sum to 2r²+2. If the real, relative to K, group is (r+1)², the outside group is (r-1)², making the new group (r+1)²(r-1)².

Let a and b define a curve, where b = as+s³. Double a point and add s to the resulting x coordinate. The tangent slope is (3x²+a)/2y. Square this to get (9x⁴+6ax²+a²) / 4(x³+ax+b). Add in (s-2x), with the common denominator of course. The denominator is already a square. The numerator is the square of 2s² - 2sx - x² + a. Therefore x+s is a square for all the points in the subgroup produced by doubling G.

The converse is (sometimes) true. The points outside this subgroup are all nonsquares for some primes, but for other primes they are 2/3 nonsquares and 1/3 squares. Let's see why this is so.

Note that -s is always a root of the cubic, giving an involution at (-s,0), thus G has even order, and the double group is a proper subgroup of G. The cubic becomes (x+s) × (x²-sx+s²+a). The discriminant is -3s²-4a. This determines whether the cubic splits fully. G is an odd subgroup, cross a power of 2, cross another power of 2 iff the cubic splits fully, iff -3s²-4a is a square. When this happens, the double group has index 4, and the points outside are 2/3 nonsquares and 1/3 squares, the squares being the points where the values within the two power 2 cycles are both odd.

Use the jacobi procedure to determine whether x+s is a square mod p, and that will tell you whether the elliptic point is in the double group (one even cycle), or whether the point has the same parity in the two even cycles.

As a special case, let a = -3s², whence b = -2s³. This turns the expression 2s² - 2sx - x² + a into a square. (I'm assuming p = 1 mod 4, so -1 is a square.) If 2y is a square, its double has x+s a fourth power, and if 2y is not a square, its double has x+s a square but not a fourth power. Unfortunately, 4a³ + 27b² comes out 0, so it's not really an elliptic curve. No help here.

The homomorphism from the elliptic group into the quadratic residue [x+s\p] is not well defined on the root -s, since -s+s is 0, which does not yield a valid jacobi symbol. In this case you can use a+3s² instead of x+s. This determines whether -s maps to a square or nonsquare in the homomorphism. I don't know why it works, but a+3s² is the derivative of as+s³, and that is probably not a coincidence.

Now let's make things a bit more complicated. After doubling a point, ask whether x²+sx+t is a square. Let a = t-s². Let b = -st. Compute the new x, then x²+sx+t, and get the square of s⁴ - 2s³x - 2sx³ - x⁴ - 4s²t - t² - 6x²t + 6sxt. (Verify with this program.) The degenerate case ( t = s²/4, wherein x²+sx+t is always a square anyways, leads to an invalid elliptic curve, with 4a³ + 27b² = 0.

s is a root, and the cubic becomes (x-s) × (x²+sx+t). The discriminant s²-4t determines whether there are 2 parallel even cycles.

Again it would be fun if, for a double point, the square root of x²+sx+t was itself minus a square. Let t = ks², and aim for -(x²+sx+cs²)². Equate coefficients on x²s² and get 2c+1 = 6k. Equate coefficients on xs³ and get 2c = -6k+2. Thus k = ¼. That works, but again a = -3s²/4 and b = -s³/4 is not valid.

Moving on to cubes, let a = 27s⁴+6st, and let b = -27s⁶+t². Triple any point, and y+3sx+t is a cube. In fact, the residue of y+3sx+t is a group homomorphism from the elliptic group onto the integers mod 3, with the triple points mapping to 0.

Here is another square, and then a fourth power. Let a = t-s²-2r⁴+3r²s, and let b = -st-r⁶+2r⁴s-r²s²+r²t. Double a point, and 2ry+x²+sx+t is a square. (Set r = 0 to get the equation we saw earlier for x²+sx+t). Set t = s²/4-3r²s+3r⁴, and multiply a point by 4, and the expression 2ry+x²+sx+t becomes a fourth power. This yields a homomorphism from the elliptic group into the integers mod 4.

Yes, there is a homomorphism from elliptic points into Z/5, but I haven't taken the time to turn it into a formula. Here are some curves and expressions mod 241 with coefficients limited to ± 40.

curve x³ - 37x + 39
xy - 23x²+ 17y+ 40x - 14
xy+ 23x²+ 17y - 40x+ 14

curve x³ - 36x - 40
xy - 12x² - 38y+ 25x - 2
xy+ 12x² - 38y - 25x+ 2

curve x³ - 29x - 11
xy - 14x² - 3y+ 19x - 19
xy+ 14x² - 3y - 19x+ 19

curve x³ - 26x - 21
xy - 24x² - 18y - 16x+ 35
xy+ 24x² - 18y+ 16x - 35

curve x³ - 24x - 36
xy - 19x² - 10y - 24x+ 36
xy+ 19x² - 10y+ 24x - 36

curve x³ - 22x - 23
xy - 25x²+ 33y - 25x+ 1
xy+ 25x²+ 33y+ 25x - 1

curve x³ - 22x + 10
xy - 20x²+ 0y+ 22x+ 19
xy+ 20x²+ 0y - 22x - 19

curve x³ - 21x - 4
xy - 20x² - 23y+ 34x - 18
xy+ 20x² - 23y - 34x+ 18

curve x³ - 20x + 33
xy - 20x²+ 8y+ 13x - 40
xy+ 20x²+ 8y - 13x+ 40

curve x³ - 15x - 34
xy - 23x² - 19y - 39x - 25
xy+ 23x² - 19y+ 39x+ 25

curve x³ - 15x - 15
xy - 29x² - 19y - 6x - 22
xy+ 29x² - 19y+ 6x+ 22

curve x³ - 14x - 22
xy - 33x² - 2y - 10x+ 0
xy+ 33x² - 2y+ 10x+ 0

curve x³ - 14x - 16
xy - 34x² - 4y - 27x - 7
xy+ 34x² - 4y+ 27x+ 7

curve x³ - 12x + 12
xy - 27x²+ 38y - 17x+ 8
xy+ 27x²+ 38y+ 17x - 8

curve x³ - 9x + 24
xy - 2x² - 17y - 22x - 13
xy+ 2x² - 17y+ 22x+ 13

curve x³ - 8x + 27
xy - 31x²+ 30y+ 5x - 17
xy+ 31x²+ 30y - 5x+ 17

curve x³ - 3x + 37
xy - 19x²+ 13y+ 10x - 14
xy+ 19x²+ 13y - 10x+ 14

curve x³ + 1x - 40
xy - 31x² - 24y - 39x - 10
xy+ 31x² - 24y+ 39x+ 10

curve x³ + 1x - 25
xy - 13x²+ 6y+ 20x+ 18
xy+ 13x²+ 6y - 20x - 18

curve x³ + 2x + 35
xy - 32x²+ 4y - 12x - 16
xy+ 32x²+ 4y+ 12x+ 16

curve x³ + 3x - 6
xy - 38x²+ 9y+ 1x+ 30
xy+ 38x²+ 9y - 1x - 30

curve x³ + 4x - 29
xy - 34x²+ 16y+ 5x - 7
xy+ 34x²+ 16y - 5x+ 7

curve x³ + 7x - 31
xy - 4x² - 8y - 36x - 2
xy+ 4x² - 8y+ 36x+ 2

curve x³ + 15x - 29
xy - 5x²+ 31y+ 15x+ 33
xy+ 5x²+ 31y - 15x - 33

curve x³ + 15x - 6
xy - 37x² - 2y - 19x - 36
xy+ 37x² - 2y+ 19x+ 36

curve x³ + 18x - 12
xy - 40x² - 25y - 3x+ 3
xy+ 40x² - 25y+ 3x - 3

curve x³ + 22x + 18
xy - 4x²+ 14y - 8x - 13
xy+ 4x²+ 14y+ 8x+ 13

curve x³ + 22x + 20
xy - 10x²+ 6y - 36x - 32
xy+ 10x²+ 6y+ 36x+ 32

curve x³ + 22x + 27
xy - 34x²+ 32y - 31x+ 20
xy+ 34x²+ 32y+ 31x - 20

curve x³ + 29x - 12
xy - 10x²+ 17y - 30x+ 33
xy+ 10x²+ 17y+ 30x - 33

curve x³ + 29x + 40
xy - 29x²+ 39y - 24x - 10
xy+ 29x²+ 39y+ 24x+ 10

curve x³ + 30x - 36
xy - 30x²+ 5y+ 38x - 39
xy+ 30x²+ 5y - 38x+ 39

curve x³ + 31x - 22
xy - 13x²+ 32y - 10x+ 0
xy+ 13x²+ 32y+ 10x+ 0

curve x³ + 31x - 6
xy - 6x²+ 4y - 30x - 16
xy+ 6x²+ 4y+ 30x+ 16

curve x³ + 33x - 9
xy - 38x² - 10y - 40x - 17
xy+ 38x² - 10y+ 40x+ 17

curve x³ + 37x - 25
xy - 15x² - 11y - 8x - 10
xy+ 15x² - 11y+ 8x+ 10

curve x³ + 38x + 33
xy - 27x²+ 39y - 11x - 28
xy+ 27x²+ 39y+ 11x+ 28

Strangely, none of these curves show up mod 521, and I only get this one.

curve x³ + 11x + 35
xy - 34x² - 32y - 2x + 25
xy + 34x² - 32y + 2x - 25

Let a and b be integers that define the elliptic curve y² = x³ + ax + b over the rationals. Let a rational point s/t,u/v satisfy the elliptic curve. Fractions are in lowest terms. If s = 0 then u has to be the square root of b, assuming b is a perfect square. If u = 0 then s/t is a root of the cubic polynomial - but such a root has a denominator dividing the lead coefficient, thus t = 1, and a numerator dividing the constant coefficient, thus s is a factor of b. There are 0 1 or 3 such solutions. These are involutions in the group. Set these cases aside, and assume s and u are nonzero. Clear denominators and get this.

u²t³ = v² × (s³ + ast² + bt³)

Since u and v are coprime, v² divides into t³. Moving to the right hand side, no prime in t divides the second factor, hence t³ divides v². Put this together and v² = t³. By unique prime factorization, there is a common integer w such that v = w³ and t = w². Rewrite the elliptic equation this way.

u² = s³ + asw⁴ + bw⁶

The original solution is s/w², u/w³, where s and u are both coprime to w. If s and u have a gcd, it must divide bw⁶, hence it divides b. Of course this is no constraint if b = 0.

Consider the case of b = 0. The following implies s is a factor of u².

u² = s × (s² + aw⁴)

The origin is a solution, as is ±sqrt(-a)w²,0, if -a is a square. Look for other solutions, where u and s are nonzero.

s divides u². This does not mean s divides u. Let g be the gcd of s and u, and let h be the extra piece of s that goes into the other copy of u. Note that h is a factor of g. In fact I'm going to relabel g = g/h, so that s = gh². Then I'm going to relabel u = u/gh, so the left side becomes (ugh)². Divide through by s and get this.

gu² = g²h⁴ + aw⁴

Since g and w are coprime, g divides a. Divide through by g and get this.

u² = gh⁴ + (a/g)w⁴

When a = ±1, g = ±1. A sum or difference of fourth powers yields a square. This is impossible, unless one of the variables is equal to 0. We've already handled the case of u = 0, hence there are no new solutions. The elliptic curve x³ + x consists of the origin and ω. That's an elliptic group of Z/2. The elliptic curve x³ - x has two more solutions at 1,0 and -1,0, leading to the group Z/2 * Z/2. There are infinitely many rationals to choose from, yet an elliptic group over Q can be finite.

Next consider the special case of a = 0.

u² = s³ + bw⁶

Double the point s/w²,u/w³ and see where it leads. The slope is 3s²/2uw. Square this and subtract 2s/w², and the new x coordinate is (9s⁴-8su²) / 4u²w². Subtract another s/w² and the change in x is (9s⁴-12su²) / 4u²w². Multiply by slope and get 9s³ × (3s³-4u²) / 8u³w³. Add in u/w³ and get (8u⁴ + 9s³ × (3s³-4u²)) / 8u³w³. Negate this for the new y coordinate.

If s, u, and w are nonzero mod 3, then numerators and denominators remain nonzero mod 3 forever, even after fractions are reduced to lowest terms.

Let's look at an example; set b = 3. The first point is 1,2. Double this point again and again and again. As shown above, coordinates will always be nonzero mod 3, so we will never run into the x or y axis. Also, when fractions are in lowest terms, numerators will be coprime, because the only factor they might have in common divides b, and b is 3, and we already said these numbers are nonzero mod 3. Apply the earlier formula to find 2p = -23/16,-11/64. The integer that seeds both denominators is 4. Apply the formula again to get this.

4p = 2540833/88² | 4050085583/88³

8p = 41677742803929195922238593/712815062608² |
269065159484683478575364835230449703617/712815062608³

I want to prove that this group is infinite, that the doubling never repeats a point. As fractions are created, they must be reduced. Starting with 2p, all points in the sequence have odd numerators. The denominator, at 2p, has w = 4. With each step, the denominator is multiplied by 2u, where u is the numerator of the previous y coordinate. The denominator is multiplied by 2 times an odd number. Some of the odd number might be reduced away, but the 2 is not. With each step the denominator gains another power of 2. It increases forever, and the fractions never repeat. Therefore y² = x³ + 3 defines an infinite elliptic group.

As a corollary, there are infinitely many coprime integer solutions to y² = x³ + 3w⁶.

There is no square root of 3 in the rationals, nor a cube root of 3, hence all solutions have s and u nonzero. Write u² = s³ + 3w⁶. If s is even then look mod 4. Since s and w are coprime, w is odd. The result is 1 = 3 mod 4, which is impossible. Therefore s is odd. Thereafter, all numerators are odd. The point has infinite order, as per the above proof. The elliptic group is torsion free.

By selecting a random elliptic curve mod p, we can work with a new group G that is not Z/p. In most cases |G| is close to p, but we might get lucky and stumble on a group whose order is divisible by many small primes. Let's see how this is going to work.

For purposes of illustration, let n = p×q, where p and q are large primes, and p±1 and q±1 are not particularly smooth. None of the easy factoring algorithms will help.

The first task is to select an elliptic curve and a point on the curve mod n. This implies a curve and a point on the curve mod p and mod q. It also implies two elliptic groups, and if all goes well, our point will have a smooth order in one of the two groups.

Start with a point u, defined by two integers x and y mod n, and select any a, and let b = y² - x³ - ax. Now u lies in both elliptic curves (mod p and q), defined by the parameters a and b.

Multiply u by 2, 3, 5, 7, and so on through the small primes. This can be done efficiently mod n. We're hoping to reach ω in one of the two groups. This is discovered by a zero denominator mod p or mod q. When a denominator d is 0 mod p, then gcd(d,n) extracts p, and factors n, so run gcd on each denominator as you go. If u has a smooth order (divisible by many small primes) in the elliptic group mod p, some multiple of u will reach ω, and gcd will extract p from n.

The trick is knowing when to give up on an elliptic curve, or suspend it, and look elsewhere. One cpu might investigate hundreds of curves sequentially, or simultaneously, using a time share approach, or a collection of distributed processors might follow their own elliptic curves, parceled out by a central server or chosen at random. There's plenty of room for creative programming here, but that is beyond the scope of this book.

To estimate performance, Assume the elliptic group has an order that is a pseudo-random number near p. Multiplying u by small primes removes these primes from |u|. This may remove 20 digits from |u|, if we're lucky. Setting these small primes aside, |u| is approximately p/10²⁰. If p is 50 digits, this still isn't good enough. We can only hope for an elliptic group whose size is unusually smooth, a 50 digit number that consists of many small primes. The probability of such an occurrence is difficult to quantify. With this in mind, it is better to try many different elliptic curves, rather than pursuing one curve for a long time.

The pbc program, that is included with this book, includes an elliptic curve factoring algorithm. It can usually crack a 60 digit number without too much fuss.

factor 10^60+17
elliptic
3^2 * 79 * 167 * 1481 * 6131 * 99846211187 * 26779254206695087 * 346894557385750113599

Alice and Bob agree on a finite field, and an elliptic curve, and a base point p on the curve. Alice generates a random number k, which is her private key, and computes kp, which is her public key. Bob selects a random number l and computes lp.

Alice sees Bob's public key, which is lp on the elliptic curve, and multiplies it by her private key k. Bob does the same. Both parties now have a point on the curve, namely klp. This is a secret that they share - their shared key. This secret, that is inaccessible to everyone else, is typically used to run other, simpler encryption schemes that require a shared key. (These are not described here.) If repeated use of the shared key might jeopardize its security, Alice and Bob can renegotiate a new key any time they wish. They select new random numbers, which act as private keys, post the corresponding public keys, combine their results to create a new shared key, and off they go. The security of elliptic curve cryptography relies on the difficulty of computing k given kp. This is sometimes called the discrete log problem, and it seems to be intractable in many situations. Thus private keys remain private, and secure communication is assured.

Since any field will do, fields of characteristic 2 are often used. These are amenable to rapid computation. For example, addition is merely an exclusive or operation. Elliptic curves of characteristic 2 are described in the next section.

Let F be a field of characteristic 2. Since the tangent formula has a 2 in the denominator, and 2 = 0 in such a field, something has to give. Curves are defined by a new template. There are still two parameters a and b, but b cannot equal 0.

y² + xy = x³ + ax² + b

Let j,k be a solution to this equation. Plug j into the cubic on the right, and the result equals k² + jk. Watch what happens if k is replaced with k+j. Substitute this in y² + xy and get k² + jk back again. This is the "other" root. (The left hand side is quadratic, and can only have two roots.) In some sense, this is the reflection of j,k. If two distinct points share the same x coordinate, reflections of each other, their y coordinates will differ by the x coordinate. These points, inverses of each other, sum to ω in G.

If j = 0 then j,k is its own reflection. In particular, k is the square root of b, and there is only one such animal.

Consider two distinct points, j,k and s,t, that are not equal to ω, and are not reflections of each other. In other words, j ≠ s. Let m be the slope of the chord, given by the usual formula (t-k) / (s-j). Of course t-k is the same as t+k, but I'll stick with t-k, because it's more familiar.

Intersect the line and the cubic curve to find the third point. Replace y, in the elliptic equation, with m×(x-j) + k, and move everything to one side.

q(x) = x³ + (a-m-m²)x² + (jm-k)x - j²m² - k² + b

Since x-j is a root of q(x), divide it out, leaving a remainder of j³ + aj² + b - k² - jk, which has to be 0. With x-j factored out, the new polynomial looks like this.

q(x) = x² + (a+j-m²-m)x - jm² + aj + j² - k

Since x-s is a root, divide it out, leaving this remainder. (I'm replacing - with + whenever I feel like it.)

m²(s+j) + a(s+j) + j² + js + s² + ms + k

m(t+k) + a(s+j) + j² + js + s² + ms + k

Multiply this by j+s.

(t+k)² + a(s+j)² + j³+s³ + (k+t)s + k(j+s)

k²+t² + aj²+as² + j³+s³ + jk+st

This is the elliptic equation evaluated at j,k, plus the elliptic equation evaluated at s,t, which is zero. We are once again comforted to know that our remainder is zero. So the quotient gives the third root: m²+m+a+j+s. This is the x coordinate of the third point on the line. The y coordinate is m(x₃-x₁) + y₁. Remember, however, that we use to negate the y coordinate. We want the reflection. In this case the reflection is produced by adding the x coordinate.

x₃ ← m²+m + a + x₁+x₂
y₃ ← m(x₃-x₁) + y₁ + x₃

Now we're ready to handle p₁ = p₂, that is, p₁+p₁ in G. We need something analogous to the tangent line. If the x coordinate is 0, the tangent line is vertical, and p₁+p₁ = ω. Otherwise m = j + k/j. I'll present the aforementioned q(x) (with x-j factored out) for review, then substitute for m and multiply through by j².

q(x) = x² + (a+j-m²-m)x - jm² + aj + j² - k

(x+j) × (j⁴ + aj² + jk + k²) + j⁴+j²x²

Since (x+j)² = x²+j², the second term is also divisible by x+j. The entire expression is divisible by x+j, and j is a double root. Factor it out and get this.

j²x + j²a + j⁴ + j³ + jk + k²

The third root doesn't change if we divide by something nonzero, like j². The expression becomes x+a+m²+m.

We could write this as x₃ = m²+m + a +x₁+x₁. This seems a bit silly, since x₁+x₁ = 0, but it does reveal an underlying symmetry. This expression is the same formula we saw earlier when the two points were distinct, but this time x₁ is equal to x₂. Similarly, y₃ is computed using the same formula as above. Substitute for m and write the simpler doubling formula.

x₃ ← m²+m + a
y₃ ← x₁² + (m+1)x₃

Congratulations - we have a well defined binary operator on G, with ω acting as identity. The inverse of x,y is its reflection x,(y+x), which works even if x = 0 (giving the same point back again). Since the operator is based on the intersection of a line and a cubic curve, the same third point is extracted for p₁+p₂ and p₂+p₁, hence the operator is commutative. It is also associative, but as above, I'm asking you to accept that on faith, until these curves are defined as structures in algebraic geometry. Therefore G is a group. G is also continuous in the 2-adic numbers.