Superconductor

Get your BN curve here

It looks like some researchers at RWTH Aachen University have an on-line tool for creating BN curves. These are elliptic curves that are particularly useful for pairing-based cryptography, like the identity-based encryption that Voltage uses. If you're interested in implementing pairing-based cryptography, this is a very useful resource to have.

It's generally true that there's no such thing as a free lunch, and this even applies to identity-based encryption. From the user's point of view IBE is great because it's simpler to use than alternatives. From an administrator's point of view IBE iss great because it's extremely simple to keep running. These two combine to make its TCO much lower than the TCO of alternatives.

On the other hand, all of these good features don't come for free, but they really involve things that users and administrators don't see. In particular, it can be very difficult to find elliptic curves that are suitable for use in IBE algorithms. Most elliptic curves don't work very well for this and it can be a bit tricky finding ones that do. BN curves happen to be an example of a type of curve that do work well, so having a place where you can get parameters for such curves can be very useful.

The parameters that you can get from this on-line tool aren't optimized to give you very good performance, so they're not what you'd want to use in a shipping commercial product, but if you're just doing development and testing they're very useful.

Violating the Nagell-Lutz theorem

In a recent post I gave examples of elliptic curves for each of the cases that Mazur's theorem allows. One of these is particularly interesting. It's the curve

y² + xy – 5y = x³ – 5x²

Over the rationals this has that E_tors = Z₂ x Z₄ = <(10,20),(1,2)> = {(1,2), (10,-25), (0,5), (0,0), (-5/4,25/8), (5,0), (10,20), O}.

Note that one of these points, (-5/4,25/8), doesn't have integer coordinates. Doesn't that violate the Nagell-Lutz theorem, which tells us that torsion points need to have integer coordinates?

Not really, and here's why.

Here's one form of the Nagell-Lutz theorem:

Let y² = x³ + ax + b be an elliptic curve over the rationals with integer coefficients and let D = 4 a³ + 27 b². Then if P = (x_P,y_P) is a rational point of finite order then P has integer coordinates and either y_P = 0 or y_P²|D.

Note that this only applies to elliptic curves of the form E: y² = x³ + ax + b. So because the curve in this example isn't of that form, its torsion points don't have to have integer coordainates.

Another look at the discriminant of an elliptic curve

This time, from the 19th-century point of view.

The singular elliptic curve y^2 = x^3

Consider the singular elliptic curve

E/Q: y² = x³

which is singular at the point S = (0,0).

Even though this curve is singular, we can still use the usual rule for adding points to get a group for all of the non-singular points: E_ns(Q) = E(Q) \ S. When we do this we find something interesting: the group of non-singular points on this curve is isomorphic to the rationals under addition, or that (E_ns, +) is isomorphic to (Q,+). And because this is true, we can see that E_ns(Q) isn't finitely generated, which is always the case with non-singular curves (the Mordell-Weil theorem).

To see why (E_ns, +) is isomorphic to (Q,+), we use the function

φ: E_ns(Q) → Q

defined by

φ(P) = φ(x,y) = x / y if P ≠O and

φ(O) = 0

This has an inverse

φ^-1: Q → E_ns(Q)

defined by

φ ^-1 (t) = (1 / t²,1 / t³) if t ≠0 and

φ ^-1 (0) = O

It's easy to see that φ is one-to-one and onto. Seeing why φ is a homomorphism is a bit more complicated.

Suppose that P_i = (x_i,y_i) are elements of E_ns with φ(P_i) = t_i.

What we want is that if P₁ + P₂ = P₃, then φ(P₁) + φ(P₂) = φ(P₃), or that t₁ + t₂ = t₃.

If we have that P₁ + P₂ = P₃ then P₁, P₂ and -P₃ are collinear. From the point-slope form of a line we have that the line through P₁ and P₂ is given by

y - y₁ = m (x - x₁)

where

m = (y₂ - y₁) / (x₂ - x₁)

or that

(x₂ - x₁) (y - y₁) = (y₂ - y₁) (x - x₁)

This line also passes through -P₃ = (x₃, -y₃) so we have that

(x₂ - x₁) (-y₃ - y₁) = (y₂ - y₁) (x₃ - x₁)

We also have that P₁ = (1 / t₁²,1 / t₁³), P₂ = (1 / t₂²,1 / t₂³) and P₃ = (1 / t₃²,1/ t ₃³). Substituting x₁ = 1/t₁², etc, we find that we have that

-(t₁ - t₂) (t₁ + t₃)( t₂ + t₃) (t₁ + t₂ - t₃) / (t₁³ t₂³ t₃³) = 0

If t₁, t₂ and t₃ are all different and non-zero, this gives us that t₁ + t₂ - t₃ = 0 or that t₁ + t₂ = t₃, so φ is a homomorphism like we want. The other cases can be handled similarly.

Mazur's theorem

Mazur's theorem tells us that the points of finite order on an elliptic curve over the rationals has to have a particular structure. In particular, if E_tors is the subgroup of E(Q) of points of finite order then E_tors has to have one of the following forms:

1. Z_n, a cyclic group of order n where 1≤n≤10 or n = 12

2. Z₂ x Z_2n, the direct product of a cyclic group of order 2 with one of order 2n for 1≤n≤4

There are examples of curves for each one of these possibilities in Exercise 8.12 on p. 238 of Silverman's The Arithmetic of Elliptic Curves.

I was curious what each of these curves looked like, so I decided to graph both the curves and the points of E_tors. Some of the cases were interesting. Others were not.

In any case, here's what I found.

Hasse's theorem

If we have an elliptic curve over GF(q)

y² = x³ + ax + b

then we should expect to have roughly q points on this curve.

In a finite field, roughly half of the elements have a square root, so if the cubic x³ + ax + b takes on values that are roughly representative of the entire field GF(q), then we should get a value that has a square root roughly half the time. Each of these values for x gives us two possible values for y, so we should expect about 2 x (q/2) = q points on such a curve.

It’s actually possible to prove that that has to be the case. If we write #E(GF(q)) for the number of points on an elliptic curve over GF(q), then Hasse’s theorem tells us that this is the case. It actually tells us that we have to have

-2√q ≤ #E(GF(q)) – (q + 1) ≤ 2√q

which we can also write as

q + 1 -2√q ≤ #E(GF(q))  ≤ q + 1 + 2√q

or

(√q - 1)² ≤ #E(GF(q)) ≤ (√q + 1)²

It's even possible to generalize Hasse’s theorem to hyperelliptic curves, where it turns out that the Jacobian of a curve of genus g over GF(q) has to have about q^g points^. This shouldn't be too surprising. If we think of the typical element of the Jacobian as

P = (P₁) + ... + (P_g) - g(O)

then we should expect about q ways to pick P₁, q ways to pick P₂, etc, for a total of q^g ways to pick P₁ through P_g.

It's even possible to show that for a hyperelliptic curve of genus g, we can put the following limits (the Hasse-Weil bound) on the size of the Jacobian #J(GF(q)):

(√q - 1)^2g ≤ #J(GF(q)) ≤ (√q + 1)^2g

This means that we can easily get a Jacobian that’s big enough to make it comparable in size to an elliptic curve group, and we can actually do this by using a value of q that’s smaller than we would need for the elliptic curve group.

On the other hand, while the best way to calculate discrete logs in an elliptic curve group is by using an algorithm like Pollard’s rho algorithm that doesn’t use the structure of the elliptic curve at all, there are ways to calculate discrete logs in the Jacobian of a hyperelliptic curve that are faster than Pollard’s rho algorithm. That doesn’t mean that hyperelliptic curves aren’t useful. It means that things just aren’t as good as we’d like them to be. Maybe that's a topic for a future post.

Elliptic curve point addition revisited

The usual way to add points on an elliptic curve uses the cord-and-tangent method. To add two points P and Q we draw the line through P and Q and find the third point where this line intersects the curve. We then reflect this point across the x-axis to get R = P + Q. This is shown in this picture, where we find that (-1,0) + (0,1) = (2,-3).

In this case, the point at infinity O acts like zero: P + O = P. It turns out that we don’t really need to use the point at infinity for zero, but if we don’t, the way that we add points changes slightly.

The picture above shows the elliptic curve

y = x³ + 1

The point Z = (0,-1) is on this curve, and we can define a way to add points on the curve in a way that this point acts like the zero element. Here’s how we do this. To add two points P and Q we draw the line through P and Q and find the third point where this line intersects the curve. We then draw the line through this point and Z and find the third point where this (second) line crosses the curve. We call this point R = P + Q. This is shown in this picture, where we find that (-1,0) + (0,1) = (2,3).

This picture is actually a bit tricky to follow. The line through (2,3) and Z actually touches the curve twice at (2,3), so the third point of intersection is also (2,3). (You even get this problem when you try to visualize the addition of points on this curve using the usual definition of addition, but I couldn’t think of an example that’s obviously better to use.)

In this case, the point at infinity doesn’t act like the zero element. If we add (2,3) to the point at infinity, for example, we find that the line between the two points intersects the curve at (2,-3). We then draw the line through (2,-3) and (0,-1) and find that it meets the curve at (-1,0), so we have that (2,3) + ∞ = (-1,0).

Showing that point addition with an arbitrary point acting as the zero element works out like we want to (associative and commutative) is actually fairly tedious, but it turns out to define a way that’s just as valid as the usual way, where we use the point at infinity for the zero element. (Come to think of it, showing that the usual version of point addition is associative and commutative is also fairly tedious, so this shouldn't really come as a surprise.)

It should also be clear that the usual form of point addition is really just a special case of the more general version. When we reflect a point across the x-axis, that's really the same as drawing a line through the finite point and the point at infinity and finding the third place where the line intersects the elliptic curve. This might be a case where it's useful to think of the point at infinity as the projective point (0,1,0), so that a line through the point at infinity is one that's parallel to the line x = 0. 

Elliptic curves and catastrophies

We usually think of elliptic curves of the form

y² = x³ + ax +b

What happens of we just look at the cubic part of an elliptic curve and think of it as an equation in a, b and x instead of just a polynomial in x?

It's even not too hard to draw a graph of that to see what it looks like. The first step is to use the cubic formula to write x as a function of a and b. Once we have that we can graph x = x(a,b) to see what's happening.

The cubic formula actually gives us three different roots:

 
   
  
Let's use the first of these because that looks like it's the most likely to give us a real number instead of a complex number and real numbers are easier to graph.

Using that for x, here's what you get when you graph x as a function of a and b:

 
The sudden discontinuity is actually just what we should expect because a cubic of the form x³ + ax is the very thing that causes a fold catastrophe, but until I made that graph I hadn't considered the connection between elliptic curves and catastrophe theory.

Projective and affine elliptic curves

Suppose that we have an elliptic curve

y² = x³ + ax + b

When we embed this in the projective plane by the change of variables

x = X/Z

and

y = Y/X

we get the homogeneous equation

Y²Z = X³ + aXZ² + bZ³

When we do this, something interesting happens: we actually end up with two copies of the original elliptic curve.

If we set Z = 1 we get

Y² = X³ + aX + b

which is obviously a copy of the original curve.

If we set Y = 1 we get

Z = X³ + aXZ² + bZ³

That's not an obvious copy of the original curve, but if we make the change of variables

X = X/Z

and

Z = 1/Z

we get that

Z² = X³ + aX + b

which makes the other copy of the curve clearer. 

The bottom line is that we can think of the projective version of the curve as being essentially two copies of the affine version of the curve that are glued together.

An invention motivated by spam

There’s apparently a doctor out there with the same name as me. I say this because I often get requests for permission to reprint various medical articles as weall as spam from biomedical companies. One of these recent spams advertised a product that identifies proteins by using mass spectrometry.

That made me wonder if it would be possible to invent a device that could automate the identification of the books on my desk. Maybe this machine would burn one of these books and determine from the ash whether the content of the book was number theory, algebraic geometry, elliptic curves, etc. Such a machine, of course, would be called a "math spectrometer." 

Weighted projective coordinates

Homogeneous coordinates are the simplest way to embed an elliptic curve

y² = x³+ ax + b

into a projective space. To do this we write

x=X/Z

and

y=Y/Z

to get

Y²Z = X³ + aXZ² + bZ³

From this form of an elliptic curve, it's easy to see what projective point corresponds to the point at infinity on the affine curve. This is where the projective form of the curve meets Z = 0. This happens when X = 0, or at (0,Y,0). In homogeneous coordinates we identify (x,y,z) with (cx,cy,cz) so we can identify (0,Y,0) with (0,1,0) giving O = (0,1,0) as a simpler way to write the point O.

With weighted projective coordinates we identify (x,y,z) with (c^ux,c^vy,c^wz) in (u,v,w)-weighted projective coordinates. The most common example of this is probably Jacobian projective coordinates, which are (2,3,1)-weighted. To use Jacobian coordinates to embed the elliptic curve

y² = x³+ ax + b

into projective space we write

x = X/Z²

and

y = Y/Z³

to get

Y² = X³ + aXZ⁴ + bZ⁶

In this case, the point at infinity is where Z = 0, or Y² = X³, or O = (c²,c³,0). We can we can identify (c²,c³,0) with (1,1,0) giving O = (1,1,0) as a simpler way to write the point O.

Weighted projective coordinates are also commonly used with hyperelliptic curves. For a curve of genus g, (1,g+1,1)-weighted coordinates are usually used. Suppose that we have a hyperelliptic curve given by

y² = x^2g+2 + a_2g+1x^2g+1 + …+ a₁x + a₀

To embed this curve in the projective plane using (1,g+1,1)-weighted coordinates we write

x = X/Z

and

y = Y/Z^g+1

to get

Y² = X^2g+2 + a_2g+1X^2g+1Z + …+ a₁XZ^2g+1 + a₀Z^2g+2

In this case, the point at infinity is where

Y² = X^2g+2

or

Y = ±X^g+1

or the points (X,±X^g+1,0). We can identify (X,±X^g+1,0) with (1,±1,0) giving us two points at infinity: (1,1,0) and (1,-1,0). The fact that we have two points at infinity for a curve of this form instead of one probably explains why most people just think about the simpler case, hyperelliptic curves of the form

y² = x^2g+1 + a_2gx^2g + …+ a₁x + a₀

Projective coordinates for hyperelliptic curves

The simplest way to embed a hyperelliptic curve in projective space is by the change of variables

x = X/Z

y = Y/Z

This causes a problem, however, because this actually makes the point at infinity singular. Here’s why.

Suppose that we have a hyperelliptic curve given by

y² = x^d + a_d-1x^d-1 + …+ a₁x + a₀

If we make the change of variable

x = X/Z

y = Y/Z

we then get

Y²Z^d-2 = X^d + a_d-1X ^d-1Z + …+ a₁XZ^d-1 + a₀Z^d

When Z = 0, we have that X^d = 0 or X = 0, so O = (0,1,0) is the point at infinity for this curve.

Writing

f(X,Y,Z) = Y²Z^d-2 - X^d - a_d-1X ^d-1Z - …- a₁XZ^d-1 - a₀Z^d

we find that

∂f/∂X = -dX^d-1-…-a₁Z^d-1

∂f/∂Y = 2YZ^d-2

∂f/∂Z = (d-2)Y²Z^d-3- a_d-1X^d-1 - … - da₀Z^d-1

If we have d ≥ 4, which includes all hyperelliptic curves , then substituting O = (0,1,0), or X = 0, Y = 1 and Z = 0, into each of these we find that at O we have that

∂f/∂X = ∂f/∂Y = ∂f/∂Z = 0

or that the point at infinity is singular. That's not good. Instead, a better change of variable to use is

x = X/Z

y = Y/Z^g+1

where g is the genus of the curve, that doesn’t give you a singular point at infinity, so it avoids that particular problem.

Adding points on hyperelliptic curves

Suppose that we have two points P and Q in the Jacobian of a hyperelliptic curve of genus 2 where

P = (P₁) + (P₂) - 2(O)

and

Q = (Q₁) + (Q₂) - 2(O)

where the curve is defined by

y² = f(x)

where f is a polynomial of degree 5.

Now suppose that we want to find P + Q = R where

R = (R₁) + (R₂) - 2(O)

Here's how we can use the structure of the hyperelliptic curve to do this.

In this picture

the red points represent P, the green points represent Q and the black points represent R. Let's write -R₁ and -R₂ for the blue points that we get by reflecting the black points across the x-axis even though that notation is a bit misleading, and let's look at three functions on the hyperelliptic curve: the curve u through P₁, P₂, Q₁, Q₂, -R₁ and -R₂, the vertical line v₁ through R₁ and -R₁ and the vertical line v₂ through R₂ and -R₂.

Note that if we write the cubic through P₁, P₂, Q₁, Q₂ as

y = g(x)

then we have

y² = g²(x)

The hyperelliptic curve is defined by

y² = f(x)

so we have that

g²(x) = f(x)

or that

g²(x) - f(x) = 0

which is a polynomial of degree 6 with zeroes at P₁, P₂, Q₁, Q₂, -R₁ and -R₂ and a pole of order 6 at O.

We can then write

div(u) = (P₁) + (P₂) + (Q₁) + (Q₂) + (-R₁) + (-R₂) - 6(O)

div(v₁) = (R₁) + (-R₁) - 2(O)

and

div(v₂) = (R₂) + (-R₂) - 2(O)

Combining these gives us that

div(u) - div(v₁) - div(v₂) = (P₁) + (P₂) + (Q₁) + (Q₂) - (R₁) - (R₂) - 2(O)

= (P₁) + (P₂) - 2(O) + (Q₁) + (Q₂) - 2(O) - (R₁) - (R₂) + 2(O)

= P + Q - R

or that

P + Q = R + div(u/v₁v₂)

which is very similar to what we get for an elliptic curve.

In practice, there's an easier way to do this, and that's with Cantor's algorithm. With Cantor's algorithm, we work with polynomials whose zeroes we get from the coordinates of points on a hyperelliptic curve instead of with the points themselves. Cantor's algorithm is more efficient, but it's hard to see the geometric meaning of what's going on with it. If we just work with divisors, adding points on hyperelliptic curves is probably easier to understand.

Hyperelliptic curves

Hyperelliptic curves are interesting for many reasons. The reason that we’re particularly interested in them at Voltage is that you can implement pairings using them and it might turn out that pairings on hyperelliptic curves can be more efficient than pairings on elliptic curves.

An elliptic curve is the set of points defined by an equation like

y² = x³ + ax + b

This gives you a structure that’s much like a torus – a shape that has a single hole in it, like a doughnut.

A hyperelliptic curve is defined by an equation like

y² = f(x)

where f is a monic polynomial of degree 2g + 1.

(There's really no reason to restrict the degree of f to being odd, and a polynomial of degree 2g + 2 will also work just as well. This makes some things trickier, so most people just stick to the odd degree case. One complication is that you actually get two different points at infinity instead of just one. More about that in a future post.)

When g = 1 this reduces to an elliptic curve, but the term “hyperelliptic curve” is usually reserved for the case where g is 2 or greater.

The number g defines the genus of the curve, a number which tells you how many holes the structure corresponding to an elliptic curve’s torus has. If the genus is 2, then the curve has a structure much like a doughnut with 2 holes, etc. The graph above is the graph of a hyperelliptic curve of genus 2.

Working with hyperelliptic curves causes some problems that aren’t there for elliptic curves. It’s possible to easily define a way to add points on an elliptic curve using the usual connect-the-dots algorithm, but this can’t be done for hyperelliptic curves. It’s possible, however, to add sets of g points on a hyperelliptic curve instead of single points. On a curve of genus 2, for example, we might add P = {P₁,P₂} to Q = {Q₁,Q₂} to get R = {R₁,R₂}. (Note that I've used brackets here instead of parentheses to make the notation more set-like. The order in which you list the elements isn't important for a set, and the order of the points isn't important here, either.)

The way that we add these sets of points is by thinking them as divisors, so that we're really adding divisors instead of adding points on a curve. The set of divisors on a curve, along with the rule that defines how to add them is called the Jacobian of the curve.

For a curve of genus g, we can reduce any divisor to one no bigger than one of the form

∑_i=1:g(P_i) – g(O)

For a curve of genus g = 2, for example, we can reduce any divisor to one like

P = (P₁) + (P₂) – 2(O)

So that when we calculate something like

P + Q = R

for a hyperelliptic curve we actually calculating

(P₁) + (P₂) – 2(O) + (Q₁) + (Q₂) – 2(O) = (R₁) + (R₂) – 2(O)

How we find R₁ and R₂ from P₁, P₂, Q₁ and Q₂ is very similar to how we add points on an elliptic curve. In the case of an elliptic curve, we fit a line through two points, find the third point where the line intersects the curve, and reflect this point across the x-axis.

In the case of a hyperelliptic curve of genus 2, we fit a cubic polynomial to the points P₁, P₂, Q₁ and Q₂. We then find the two additional points where this polynomial intersects the curve and then reflect each of those points across the x-axis to get R₁ and R₂. Here’s a picture that shows what it looks like when we add to points P (the red points) and Q (the green points) to get R (the black points).

Because doing operations on hyperelliptic curves are defined in terms of divisors, it shouldn't be much of a surprise that pairings, that are also calculated using divisors, work just as well on hyperelliptic curves as they do on elliptic curves. That means hyperelliptic curves might end up be useful in pairing-based cryptography. If there's a good use for them, they'll probably appear in Voltage's products in the future. Right now, however, elliptic curves seem to be good enough.

Zn vs. Z/nZ

If you read papers about cryptography, you'll see the mathematical structure where integers are added modulo n written two different ways. Computer scientists tend to write this as Z_n while mathematicians tend to write this as ℤ/nℤ. I've explained this so many times in the past year or so that I've decided to put an explanation here that I can just point people to in the future.

The notation Z_n is fairly easy to understand. It's just the set {0,1,…,n-1} along with addition modulo n. The notation ℤ/nℤ is a bit trickier.

If we write the integers as ℤ where

ℤ = {…,-1,0,1,…}

then we can write

nℤ = {…,-n,0,n,…}

Elements of ℤ/nℤ are nℤ along with

1 + nℤ = {…,-n+1,1,n+1,…}

2 + nℤ = {…,-n+2,2,n+2,…}

⋮

along with an operation on ℤ/nℤ that acts just like addition, where we have that

(a + nℤ) + (b + nℤ) = (a + b) + nℤ

It should be fairly clear that we can identify elements of Z_n with elements of ℤ/nℤ in the obvious way, with a∈Z_n corresponding to a + nZ∈ℤ/nℤ. Because they mean essentially the same thing, why would anyone want to use the more cumbersome ℤ/nℤ notation?

It turns out that there are lots of mathematical objects that have structure that lets you define operations on them that aren't division but that behave much like division does. In the case of group theory, for example, the third isomorphism theorem says that when some technical conditions are satisfied for groups G, H and K then we can write

(G/K) / (H/K) ≅ G/H

where the "≅" symbol indicates that the two structures are isomorphic, or essentially the same, just like Z_n and ℤ/nℤ are. So while the mathematical notation may be both cumbersome and confusing, it actually can be a good way to show that there's additional structure present that the simpler notation doesn't suggest.

Why Do People Hate Math?

How does this topic fit into a blog on security? Because crypto is an important part of security and math is an important part of crypto.

Many people say, "I'm no good at math." And then there is the subset of those who go a bit further than simply saying, "I'm no good at math." They say it with pride. I think they see math as not particularly human.To them, people who are good at math are more machine than person. Maybe they have heard that the left brain is logical and the right brain is creative, so those who are good at math are not creative and being creative is a mark of a superior human.

It is true, of course, that there are people who believe that those who are good at math are superior humans. For example, Robert Heinlein wrote, "Anyone who cannot cope with mathematics is not fully human. At best he is a tolerable subhuman who has learned to wear shoes, bathe, and not make messes in the house."

So I'm not going to say that those who think creative people are better humans (more evolved, on a higher plane than the rest of us plebians) are doing anything worse than what some in the numerate community do. But I still don't think it's a good idea: that it is better to be bad at math than to be good at it, that those who do well at math are really the lower form.

Some people who are bad at math blame the schools. "It's the way they teach math. It's too boring." Or "They make it too confusing." Or "Some people just can't explain math, and that's who I had in school."

That's possible, there are bad teachers in the world. But I also think too many people view learning as a passive activity. They sit back while the teacher does all the work. It's the teacher's job to pour knowledge and skill into the student's brain. Something I read once illustrates this. A college student had gotten a bad grade in a class and had written a letter to the dean arguing that it was undeserved. One of his arguments was that he had earned good grades in all his classes for over two years, so he was smart and teachable, meaning that a bad grade from this teacher was proof the teacher was at fault.

I think part of the problem people have with math is that it moves from memorization to thinking. When you first learn math you memorize most of it, from formulas to times tables to division rules. But later on, you are required to actually think. It starts with word problems then moves on to geometry proofs and then algebra and trigonmetry. Before, students just had to do pattern recognition: this pattern means to apply that formula. But pattern recognition does not work when the solution requires thinking. I once tutored a high school student in math. When I explained the difference between pattern recognition and thinking, she went from C's and D's to B's.

When people say, "I'm no good at math," here's what I think is happening. "I'm no good at math, it's not my fault, I was just born that way. That means I don't have to work hard. If I stress myself over this, I still won't understand it and I'll be stressed. If I just give up, I won't understand it but I won't be stressed. Either way I don't understand it, but in one scenario there's no stress."

And there you go. They don't have to try, they don't have to do any work. Life is so much easier if you never do anything difficult.

There have been times when I've tutored or helped people who claimed, "I'm no good at math." I thought I could be successful by teaching some very simple things so that they could build confidence, so that they would see that they indeed could do math. However, I quickly learned that these people refused to learn. They steadfastly and absolutely refused to understand even simple concepts. My theory was that they knew (maybe only subconsciously) that if they admitted they understood something about math, that if they allowed themselves to understand even simple math concepts, their argument "I'm no good at math," would go away and they would have to try. They would then have no excuse for failing and would then be forced to do a little hard work or else fail for no good reason. It's much easier to refuse to learn.

This is not to say that all people have natural math ability. I firmly believe that for some people, math is going to be much harder. There are indeed people whose brains are wired in a way that makes seeing math connections more difficult. It's not just math, some people have difficulty learning foreign languages, or music, or map reading, or computer programming. Or conversely, some people have brains that immediately come up with a witty remark in any situation, others will be able to know the best technique to sell a product to person A and that they'll need a different pitch to sell to person B. Some people have brains that understand math easily. Brains are wired differently.

But that's no excuse for not trying. That's no excuse for not working a little harder. And besides, I suspect that very few of the people who claim, "I'm no good at math," really have brains that just cannot make the connections to understand the basic and even intermediate elements of math. It's probably the case that many people who claim their brains are just not wired for math are either lazy or believe that non-math people are superior.

By the way, as I understand it, this attitude tends to appear mostly in the US. From what I've read, in other parts of the world, being good at math is neither a mark of superiority or inferiority. Maybe it's part of US culture that allows or even rewards people who say, "I hate math." Maybe in other cultures, children are expected to learn math just like they're expected to read. Maybe in other cultures children do not go to school with an existing fear of math.

Finding primes

In cryptography, we often need to find large prime numbers. One way to do this is to pick random numbers that are the right size until you find one that's a prime. This might take a while when we're working with numbers that are as big as the ones that we typically use in cryptography. How long will this take?

One way to answer that question is by using the prime number theorem. Let the function π(x) be the number of primes less than or equal to x. The prime number theorem says that lim_x→∞π(x) / (x / log x) = 1, or that x / log x is a good approximation to π(x) for large values of x.

Here's how well π(x) (black) and x / log x (red) agree:

An even better approximation to π(x) is x / (log x + 1). Here's how well π(x) (black) and x / (log x + 1) (green) agree:

But since for numbers of the sizes that we often use in cryptography log x and log x + 1 are fairly close, so we can use the easier approximation without worrying too much.

One consequence of the prime number theorem is that the probability of a number n being prime is roughly 1 / log n. Here's what log n looks like for numbers that are the sizes of those that we often use in cryptography:

n	log n
2512	354.891
21,024	709.783
21,536	1064.67

So suppose that we want to generate two random 512-bit primes, like we might need to create a 1,024-bit RSA modulus. The chances of a randomly-chosen 512-bit integer being prime is about 1 in 355, so that we'd expect to find a prime in about 355/2, or about 177 attempts.

This obviously isn't the best strategy: half of randomly-chosen integers will be even, so we don't want to waste time considering them. If we look at only odd integers, this will reduce the expected number of trials by 1/2, or down to about 89 attempts. We could even continue this strategy for other small primes. One-third of randomly-chosen integers are multiples of 3, for example, so we might not want to consider multiples of 3, etc. But for the simple strategy of just trying random odd 512-bit integers, we should expect to find a 512-bit prime in about 89 tries.

Proof that elliptic curves rock

It looks like I'm not alone in thinking that elliptic curves are interesting. The collective wisdom of the Internet seems to feel the same way. Here's proof: a perfect 10 out of 10 on the sucks/rocks meter. Who ever would have thought?

The j-invariant of an elliptic curve

If we have an elliptic curve

y² = x³ + ax + b

then the j-invariant of the curve is given by

j(a,b)= 4a³ / (4a³ + 27b²)

or perhaps by some constant multiple of this. Sometimes there's an additional factor of 1728 thrown in there that makes some calculations come out cleaner, but it's not really necessary. Why does this definition make sense? Elliptic curves with the same j-invariant are isomorphic, or are really the same curve in disguise, and here's why.

Suppose that we have a lattice L in the complex plane with basis ω₁ and ω₂. When we multiply each of these basis elements by the same non-zero constant to get the basis cω₁ and cω₂ , we end up with essentially the same lattice, and the j-invariant captures that idea.

The Weierstrass invariants g₂ and g₃ for L are given by

g₂ = 60 ∑ ω^-4

and

g₃ = 140  ∑ ω^-6

where the sums are over all non-zero ω = nω₁ + mω₂.

If we multiply both ω₁ and ω₂ by a non-zero constant c we get the basis for a lattice L′ we get that

g₂' = 60 ∑ (cω)^-4 = c^-4 60 ∑ ω^-4 = c^-4 g₂

and

g₃' = 140 ∑ (cω)^-6 = c^-6 140 ∑ ω^-6 = c^-6 g₃

The value

j(g₂,g₃) = g₂³ / (g₂³ – 27 g₃²)

is invariant under this change of variables, so that

j(g₂' ,g₃' ) = j(g₂,g₃)

How is this reflected in an elliptic curve that's parameterized by the Weierstrass ℘-function that we get from these lattices?

If we have an elliptic curve

y² = 4x³ – g₂x – g₃

or

(y/2)² = x³ –g₂/4 x – g₃/4

and write this as

y² = x³ + ax + b

then we have that g₂ = -4a and g₃ = -4b so that

j(g₂,g₃) = j(-4a,-4b)

= (-4a)³ / ((-4a)³ – 27(-4b)²))

= 4a³ / (4a³ + 27b²)

which is the form that's usually given for the j-invariant, at least up to a constant.

We can also see how the mapping of L to cL, which maps z to cz, is reflected in the coordinates of a point on an elliptic curve.

The x-coordinate of a point on an elliptic curve that's parameterized by the Weierstrass ℘-function is given by

℘_L(z) = z^-2 + ∑ ((z - ω)^-2 - ω^-2)

so that

℘_cL(cz) = (cz)^-2 + ∑ ((cz - cω)^-2 - (cω)^-2)

= c^-2 (z^-2 + ∑ ((z - ω)^-2 - ω^-2))

= c^-2 ℘_L(z)

or that x gets mapped to c^-2x.

Similarly, we have that

℘′_L(z) = -2 ∑ (z - ω)^-3

so that

℘′_cL(cz) = c^-3 ℘′_L(z)

or that y gets mapped to c^-3y.

Here's a table that summarizes the correspondences between (x,y) on E: y² = x³ + ax + b and (x′,y′) on the isomorphic E′: (y′)² = (x′)³ + a′x′ + b′:

E	E′
a	a′ = c-4a
b	b′ = c-6b
x	x′ = c-2x
y	y′ = c-3y
j	j′ = j

Now suppose that we want to find an elliptic curve with a particular j-invariant, say J. If we have

a = b = (27/4) (J / (1 - J))

then we get that

j(a,b) = J

so the elliptic curve

y² = x³ + ax + b

has that j-invariant.

Now, if I could just learn why a j-invariant is called a j-invariant I'd be happy. I've never been able to track down that particular bit of history.

A use for equivalent divisors

Two divisors are equivalent if they differ by the divisor of a rational function. When it comes to calculating the pairings that we want to implement for pairing-based cryptography, it can be useful to know when two divisors are equivalent because there are lots of cases where we just need a divisor equivalent to a particular divisor instead just a particular divisor.

If this is the case, then we can pick a divisor that's nice in some way and use it instead of an equivalent but less nice form. In particular, this can help get rid of the point at infinity and use a finite point on an elliptic curve instead. We get Tate pairing of point P of order n and a second point Q, for example, by finding a rational function equivalent to the divisor

n(P) - n(O)

and evaluating this function at a divisor equivalent to

(Q) - (O)

To do this, having a way to get rid of the points at infinity can be useful. Here's a way to do this.

Suppose that we have two divisors on an elliptic curve

D₁ = (P₁) - (O)

and

D₂ = (P₂) - (O)

Let's say that P₁ + P₂ = P₃ and write u as the line through P₁, P₂ and -P₃ and v as the line through P₃ and -P₃. To help visualize things, the following picture may be useful:

 
Like we saw in a previous post, we can use u and v to write

(P₁) - (O) + (P₂) - (O) = (P₃) - (O) + div(u/v)

Now let's replace P₁ with P, P₂ with R and P₃ with P + R. With this change of notation we have that

(P) - (O) + (R) - (O) = (P + R) - (O) + div(u/v)

Rearranging terms a bit gives that

[ (P) - (O) ] - [ (P + R) - (R) ] = div(u/v)

or that the divisors

(P) - (O)

and

(P + R) - (R)

are equivalent because their difference is just div(u/v), which is the divisor of a rational function.

So if we need to do a calculation with a divisor equivalent to (P) - (O), we can just pick a random point R and use the divisor (P + R) - (R) instead of (P) - (O). The point at infinity can make it difficult to do calculations with (P) - (O), but that's not a problem with  (P + R) - (R).

There are also other ways to avoid dealing with the point at infinity. Some of these are actually simpler to implement, but they're also a bit more difficult to understand. Maybe that's a topic for a future post.

More values of trig functions using radicals

I recently stumbled across the fact that there are nice, clean expressions for the sine and cosine of both π/5 and π/12. These turn out particularly simple for π/12 where we have that

sin(π/12) = (-1 + √3) / (2 √2)

and

cos(π/12) = (1 + √3) / (2 √2)

In high-school trigonometry, we learn these facts:

n	cos(π/n)	sin(π/n)
1	-1	0
2	0	1
3	1/2	√3/2
4	√2/2	√2/2
6	√3/2	1/2

I always assumed that we weren't taught the values of trig functions at other angles of the form π/n because they didn't have nice, clean forms, but it turns out that this isn't really true. Instead, a necessary and sufficient condition for it being possible to write the trig functions of angles of the form π/n using radicals is that φ(n) is a power of 2, or that φ(n) = 2^m for some integer m. The first several values for which this holds are the following:

1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40, 48, 51, 60

These values are actually sequence A003401 in The On-Line Encyclopedia of Integer Sequences.

Power series, Taylor series and Fourier series

 

Here's another thing that I just recently realized and wish that someone had pointed out when I was in school. It concerns Taylor series and Fourier series. They're really the same thing.

Suppose (with a little bit of hand waving) that we have an analytic function that we write as

f(z) = ∑a_nzⁿ

If we write

z = re^iθ

and substitute that back into the power series representation for f(z) we get that

f(re^iθ) = ∑a_n(re^iθ)ⁿ = ∑a_nrⁿe^inθ

Now suppose that we fix θ. In that case we can write

f(r) = ∑(a_ne^inθ)rⁿ= ∑A_nrⁿ

which is just a Taylor series.

If we fix r then we can write

f(θ) = ∑(a_nrⁿ)e^inθ = ∑B_ne^inθ

which is just a Fourier series.

To get the coefficients of a Taylor series, you calculate lots of derivatives. To get the coefficients of a Fourier series, you calculate lots of integrals. The fact that these two types of series are closely related probably tells you something profound about the connection between differentiation and integration of functions of a complex variable if you think about it for a while.

How many factors can we expect?

To use the RSA public-key scheme you need to generate a large number that's the product of two primes. The usual way to do this is to generate two primes and multiply them together. Suppose that we just pick a large number at random. What are the chances that it's of this form? In other words, what is the probability that a large number is the product of two primes? That's not an easy question to answer, but a closely related question is: what is the probability that a large number is the product of two distinct primes?

We can write 15 = 3 x 5, so 15 is the product of two primes. It's also the product of two distinct primes. But because we can write 45 = 3 x 3 x 5 = 3² x 5, 45 it's the product of three primes, but only the product of two distinct primes.

A profound theorem by Paul Erdös and Mark Kac (the Erdös-Kac theorem) tells us that the number of distinct prime factors of an integer n is asymptotically normally distributed, and has both mean and variance equal to log log n. Even for numbers as big as the ones that we commonly use in cryptography, log log n isn't very big, so such numbers tend to not have too many distinct prime factors.

Here's what log log n looks like for common RSA key sizes.

n	Log log n
21,024	6.65496
22,048	7.25811
23,072	7.66357

This means that we can expect a 1,024-bit number or 2,048-bit number to have about seven distinct prime factors, and we can expect a 3,072-bit number to have about eight distinct prime factors. Because log log n grows so slowly, there's really not much difference between the number of distinct factors that we expect over this huge range. So even for numbers as big as those that we encounter in cryptography, we really don’t expect numbers to have too many distinct prime factors.

Isomorphic elliptic curves

Elliptic curves with the same j-invariant are isomorphic. But exactly where are they isomorphic?

Consider the elliptic curve over the rationals given by

y² = x³ + b

Let's use E_tors to represent the group of points of finite order on the curve E and #E_tors to represent the number of points in E_tors. The structure of E_tors as well as the value of #E_tors of depends on what the value of b is. Here's what we get for a few different curves with different values of b:

Curve	#Etors	Structure of Etors
y2 = x3 + 1	6	Z6 = <(2,3)>
y2 = x3 + 2	1	Z1 ={O}
y2 = x3 + 4	3	Z3 = <(0,2)>
y2 = x3 + 8	2	Z2 = <(-2,0)>
y2 = x3 + 9	3	Z3 = <(0,3)>

Each of these curves has the same j-invariant. In each case we have that j = 0, but the structure of E_tors varies from curve to curve.

Here's another example of curves with the same j-invariant that have different structures for E_tors:

Curve	#Etors	Structure of Etors
y2 = x3 + x	2	Z2 = <(0,0)>
y2 = x3 + 4x	4	Z4 = <(2,4)>
y2 = x3 – 4x	4	Z2 × Z2 = <(2,0),(0,0)>

Curves with the same j-invariant are supposed to be isomorphic. What's going on here?

Curves with the same j-invariant are only isomorphic over some extension field, not over the field that the elliptic curves are defined over. So although the curves in these examples aren't isomorphic over the rational numbers, they're isomorphic over some extension to the rational numbers.

Let E be the elliptic curve given by

y² = x³ +1

and E′ be the elliptic curve given by

y² = x³ + 4

We can write the isomorphism φ:E→E′ as

φ(x,y) = (c²x,c³y)

where

c = ∛2

Here's what we get when we look at what happens to the subgroup of points on E generated by P = (2,3) under the isomorphism φ, where φ(P) = P′, etc.

Point on E	Multiple of P	Point on E′	Multiple of P′
(2,3)	1	(25/3,6)	1
(0,1)	2	(0,2)	2
(-1,0)	3	(-22/3,0)	3
(0,-1)	4	(0,-2)	4
(2,-3)	5	(25/3,-6)	5
O	6	O	6

Not all of the multiples of  φ(P) = P′ have rational coordinates, but the ones that do give us a subgroup isomorphic to Z₃. So if we insist on rational coordinates, then we find that we only have three points of finite order, but if we extend what we allow for the coordinates of points to include ∛2 then we find that we have all six points. So although E and E′ aren't isomorphic over the rationals, they're isomorphic over an extension of the rationals that includes ∛2.

The "tors" in "E_tors" stands for "torsion." Points of finite order on an elliptic curve are sometimes called "torsion points," but nobody quite seems to know exactly why. If you know this bit of elliptic curve history, be sure to let me know.

Divisors on elliptic curves revisited

When we talk about divisors on elliptic curves, we're often careless (well, at least I am), which makes it hard for people who are just figuring out divisors to understand what's going on. Here's an attempt to clarify things a bit, yet still without using terminology from algebraic geometry. There's still some handwaving here, but not as much as in my first attempt at this.

Suppose that we have points P₁ and P₂ on an elliptic curve and that their sum is P₁ + P₂ = P₃. Let u be a function that has zeroes at P₁, P₂ and –P₃ and v be a function that has zeroes at P₃ and –P₃. The picture that we usually draw of this looks like this:

We'd like to write

div(u) = (P₁) + (P₂) + (-P₃) – 3(O)

and

div(v) = (P₃) + (-P₃) – 2(O)

How do we think of u and v so that this makes sense?

First, a quick comment about poles of polynomials. It's clear what the zeroes of a polynomial are. What about their poles? A function f(x) has a pole at infinity if f(1/x) has a pole at 0, so if we have

f(x) = a x + b

then

f(1/x) = a/x + b

= (a + b x) / x

so that f has a pole or order 1 at infinity. Similarly, any polynomial of degree n has a pole of order n at infinity.

Now suppose that we have an elliptic curve defined by

y² = x³ + a x + b

and that the line through P₁, P₂ and –P₃ is given by

y = c x + d

Squaring the equation for the line gives

y² = (c x + d)²

So that where the elliptic curve intersects the line we have that

x³ + a x + b = (c x + d)²

or that

x³ + a x + b - (c x + d)² = 0

That's a polynomial of degree 3 that has zeroes at P₁, P₂ and –P₃ and because it's of degree 3 it also has a pole of order 3 at infinity. So if u is where the elliptic curve intersects the line through P₁, P₂ and –P₃ then u has zeroes at P₁, P₂ and –P₃ and a pole of order 3 at O so we can write

div(u) = (P₁) + (P₂) + (-P₃) – 3(O)

Similarly, if the line through P₃ and –P₃ is given by

x = c

then where the elliptic curve intersects this line we have that

y² = c³ + a c + b

That's a polynomial of degree 2 that has zeroes at P₃ and –P₃ and because it's of degree 2 it also has a pole of order 2 at infinity. So if v is where the elliptic curve intersects the line through P₃ and –P₃ then v has zeroes at P₃ and –P₃ and a pole of order 2 at O so we can write

div(v) = (P₃) + (-P₃) – 2(O)

Maybe that will clarify things a bit.

Jack Bauer Day - Spurring Innovation

“I know what it's like to feel like it's never going to end.” – Jack Bauer

One of the challenges which face many world-class engineering organizations is how to maintain an atmosphere of innovation while still delivering on customer commitments and scheduled releases. During the early stages of a start up innovation is rampant; there are typically no customers to worry about, no backward compatibility issues and no upgrade paths to test.

As a company matures I have seen many engineering teams stagnate, innovation slows down, and morale suffers. As a VP of Engineering I spend time on the lookout for the warning signs, at Voltage we are blessed with a strong highly motivated team.

Recently within the Voltage engineering team we held our first “Jack Bauer Day.” 24 hours of the engineering team doing anything they wanted to do. From 9 am in the morning of February 2^nd (2/4 for all us in the USA) until 9 am in the morning of February 3^rd the team had free rein with very little direction. The one condition: you had to present what you worked on to the rest of the team.

It was fascinating to watch how ad hoc teams formed; perhaps one of the most interesting was a team of three engineers who took on the task of developing Format Preserving Encryption on regular expressions as described by Bellare, Ristenpart, Rogaway and Stegers in their Format-Preserving Encryption paper.

Within the allocated time period the team was able to demonstrate features such as:

Given a regular expression R describing a regular language and a plaintext p which matches R, then p can be encrypted to a ciphertext c which also matches R and has the same length as p, and c can be decrypted back to p. For example:

Plaintext: jobs@voltage.com

Ciphertext: 3y90zagb@2GMK.com

Decrypted ciphertext: jobs@voltage.com

The team then expanded the initial implementation with some different length encryption. Given regular expressions R1 and R2 (each describing a regular language, with certain restrictions on R2) and a plaintext p which matches R1, then p can be encrypted to a ciphertext c which matches R2 (with varying options for the length of c), and c can be decrypted back to p.

For example:

Plaintext: 4005 Miranda Ave, Palo Alto, CA, 94043

Ciphertext: 8 Bauzvvbuwg Dr, Szptny Oqo, AZ, 25601

It never ceases to amaze me what a small team of focused engineers can achieve if left alone.

Was Jack Bauer day a success? Yes absolutely. We will be holding them on a regular basis.

Acknowledgments: Portions of this post was taken from team rugby’s write up of their Jack Bauer day.

Adding points on an elliptic curve

It's actually fairly easy to derive the formulas for adding points on an elliptic curve. Here's how to do it.

Suppose that we have three points

P₁ = (x₁,y₁)

P₂ = (x₂,y₂)

and

P₃ = P₁ + P₂ = (x₃,y₃)

on the elliptic curve

y² = x³ + ax + b

First, let's assume that P₁ = P₂. Let m be the slope of the line through the points P₁ and P₂ so that

m = (y₂ – y₁) / (x₂ – x₁)

From the point-slope form of a line we have that

y – y₁ = m(x – x₁)

so that

y = m(x – x₁) + y₁

and that

y² = (m(x – x₁) + y₁)²

= m²(x – x₁)² + 2my₁(x – x₁) + y₁²

We also have that

y² = x³ + ax + b

so that we have that

x³ + ax + b = m²(x – x₁)² + 2my₁(x – x₁) + y₁²

or that

x³ + ax + b - m²(x – x₁)² + 2my₁(x – x₁) + y₁² = 0 (∗)

This polynomial has three roots: x₁, x₂ and x₃, so we can also write it as

(x – x₁)(x – x₂)(x – x₃) = 0

or

x³ – (x₁ + x₂ + x₃)x² + … = 0 (∗∗)

Equating the coefficients for x² in (∗) and (∗∗) we see that

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

Solving this for x₃ gives us that

x₃ = m² – x₁ – x₂

Now because (x₃,y₃) is on the line defined by

y – y₁ = m(x – x₁)

we have that

y₃ – y₁ = m(x₃ – x₁)

or that

y₃ = m(x₃ – x₁) + y₁

This gives that

m = (y₂ – y₁) / (x₂ – x₁)

x₃ = m² – x₁ – x₂

y₃ = m(x₃ – x₁) + y₁

If P₁ = P₂ then we find m in a different way. In this case we have

y² = x³ + ax + b

so that

2yy′ = 3x² + a

so that

y′ = (3x² + a) / (2y)

so that we want

m = (3x₁² + a) / (2y₁)

but everything else is the same. We can then write

m = (3x₁² + a) / (2y₁)

x₃ = m² – 2x₁

y₃ = m(x₃ – x₁) + y₁

Another visualization of elliptic curves

Here's another way to visualize an elliptic curve. The elliptic curve

y² = x³ - 2x + 3

is the intersection of the surfaces

z = -x³ + y²

and

z = -2x + 3

Here's what that looks like:

The virial theorem in the workplace

There's a theorem from mathematical physics that may have an application in the workplace. This is the virial theorem, and its workplace analogy may explain why every job has its annoying parts.

One version of the virial theorem roughly says that for a finite collection of point particles interacting gravitationally, the time average of the kinetic energy is half the time average of the potential energy, or

<K> = - <U> / 2

The virial theorem is useful to astronomers because you can use it get a good idea of masses of distant objects, which you can't really observe, from their kinetic energy, which you can observe. The reason that we think that dark matter exists is basically from observations like those plus the virial theorem.

Driving in to work today, I had the thought that an appropriate analogy for the virial theorem the workplace might be that the bad parts of a job are always proportional to the good parts of a job. In my experience, this seems to have always been true.You probably have some relationship like this, for example:

<Bad> = - <Good> / 2

When I was an officer in the US Army, there were lots of good aspects of the job. There's nothing in the world as rewarding as working with soldiers, for example, and getting paid to work with explosives and fire guns is also lots of fun. To make up for this, however, there's also the fact that the military is really part of the government, so you're really part of a large, mind-numbingly bureaucratic organization.

Or when I used to do what's probably best called applied physics research, it was great fun working with things like lasers and electron microscopes. To make up for this, however, there's the never-ending battle that you have to fight to get funding for those expensive gadgets.

Or when I did mergers and acquisitions consulting, it was great fun getting a look inside lots of different companies in lots of different industries and seeing how they worked. The pay wasn't bad, either. To make up for this, however, there were the 20-hour days and the backstabbing from other consultants (particularly the lawyers) involved in the M&A projects that you had to keep a constant eye out for.

So although I'm not sure that you can write down a set of assumptions that lets you rigorously prove an analogy for virial theorem for the workplace, it certainly seems to be true. If there's a job out there for which it doesn't hold, I'd definitely like to hear about it.

The converse of the Nagell-Lutz theorem

The Nagell-Lutz tells us that rational points of finite order have integer coordinates, but it doesn't tell us that points with integer coordinates have finite order. As a reminder, here's the statement of the Nagell-Lutz theorem.

Let y² = x³ + ax + b be an elliptic curve over the rationals with integer coefficients and let D = 4 a³ + 27 b². Then if P = (x_P,y_P) is a rational point of finite order then P has integer coordinates and either y_P = 0 or y_P²|D.

Here are some examples of points with integer coordinates that don't have finite order.

The point P = (1,2) is on the elliptic curve

y² = x³ + 3

but (1,2) isn't a point of finite order. We have that

2P = (-23/16,-11/64)

for example. Since 2P doesn't have integer coordinates, it's not a point of finite order, so P isn't either.

For another example, consider the elliptic curve

y² = x³ + 17

There are 16 points with integer coordinates on this curve. These are the following

(-2,±3)

(-1,±4)

(2,±5)

(4,±9)

(8,±23)

(43,±282)

(52,±375)

(5234,±378661)

Although we can find a few cases where adding these points gives another point with integer coordinates, like

(-2,3) + (-1,4) = (4,9)

most cases don't. We have that

(-1,4) + (-1,4) = (137/64, -2651/512)

for example.

Even worse, we have that

(5234,378661)  + (5234,378661)  = (187618163896928/143384152921, -1/4)

None of these points actually have finite order although they have integer coordinates. So points of finite order have to have integer coordinates, but not all points with integer coordinates have finite order.

An example of bad reduction mod p

Elliptic curves are a natural construction over the complex numbers, but curves over the complex numbers aren’t very useful in computing. For that, we need elliptic curves that are defined over a finite field. It turns out that an elliptic curve over the integers can be reduced to one over a finite field in most cases. In particular, if we have an elliptic curve defined by

y² = x³ + ax + b

which has discriminant

D = -4a³ - 27 b²

then we want to look at what happens if reduce everything modulo a prime p. As long as p isn’t a factor of D, everything works fine. If p is a factor of D, however, then we get a singular curve when we reduce mod p. For example, the curve

y² = (x - 3)(x - 8)(x + 11)

= x³ – 97x + 264

has no repeated roots over the complex numbers, which is reflected in its non-zero discriminant

D = 1768900

= 2² 5² 7² 19²

But because 19 is a factor of D, this curve becomes singular when we reduce everything modulo 19. In particular, we find that this curve becomes

y² = x³ – 97x + 264

≡ x³ + 17x + 17 (mod 19)

 ≡ (x + 11)² (x + 16) (mod 19)

The cubic part of the curve has multiple roots so it's singular over GF(19). Modulo 19 this curve also has discriminant

D = -4(17)² – 27(17)³

= -27455

≡ 0 (mod 19)

which also tells us that this curve is singular over GF(19).

Convergence of power series

Some thoughts on the convergence of power series - with pictures.

Consider the three functions

f₁(x) = 1 / (1 - x²)

f₂(x) = 1 / (1 + x²)

f₃(x) = √(1 + x²)

If we expand each of these in a power series around x = 0 we find that

f₁(x) = Σ x²ⁿ

f₂(x) = Σ (-1)ⁿx²ⁿ

f₃(x) = Σ x²ⁿ Binomial(1/2,n)

and that each converges for -1 < x < 1.

In the case of f₁, it's easy to see why that's the case. Here's the graph of f₁, and it behaves badly at -1 and 1.

In the case of f₂, it's not immediately obvious why reaching -1 and 1 causes problems. Here's the graph of f₂, and it certainly doesn't behave badly at all at these points.

On the other hand, the graph of what we get by summing the first few terms in the power series for f₂ looks like this, which does behave badly at -1 and 1.

This is easy to explain. If we look at |f₂| as a function of a complex variable, we see that f₂ has poles at i and –i, and the location of those poles limits the radius of convergence of the power series.

In the case of f₃, it's slightly more complicated. Here's what f₃ looks like. It also doesn't behave badly at -1 or 1.

Here's what |f₃| looks like as a function of a complex variable, and there aren't any poles there to cause problems. What's going on here?

What's causing problems in this case are the branch cuts that you need to define for f₃. Here's a graph of the imaginary part of f₃. Note that it's the locations of the branch cuts that limit the radius of convergence of the power series.

I don't recall being taught about branch cuts limiting the radius of convergence of a power series when I was in school. Like many other things, I'm not sure why this was overlooked.

Points of order three on elliptic curves

In an earlier post, we saw how it’s easy to tell which points on an elliptic curve y² = x³ + ax + b have order 2. What about order 3? That’s not much harder. If we have 3P = O then 2P =  –P, and we can use what we know about points of order 2 to find out what happens for points of order 3.

Let’s write

P₁= (x₁,y₁)

and

P₂ = 2P₁ = (x₂,y₂)

so that

 –P₁ = (x₁, –y₁)

From the earlier post on point doubling we have that

x₂ = (x₁⁴  – 2ax₁²  – 8bx₁ + a²) / [4 (x₁³ + ax₁ + b)]

If 2P₁ =  –P₁ then we have that

x₂ = x₁

or

(x₁⁴ – 2ax₁² – 8bx₁ + a²) / [4 (x₁³ + ax₁ + b)] = x₁

or

(x₁⁴ – 2ax₁² – 8bx₁ + a²) / [4 (x₁³ + ax₁ + b)] - x₁ = 0

so that

x₁⁴ – 2ax₁² – 8bx₁ + a² – 4x₁⁴ – 4ax₁² – 4bx₁ = 0

or that

3x₁⁴ + 6ax₁² + 12bx₁ – a² = 0

Example

For the elliptic curve y² = x³ + 1 we have that the x-coordinates of the points of order 3 need to have the property that

3x⁴ + 6ax² + 12bx – a² = 0

with a = 0 and b = 1 this means that we have

3 x⁴ + 12x  = 3x (x³ + 4) = 0

the only rational solution of which is x = 0. Thich corresponds to the points (0,1) and (0,-1) on the elliptic curve. Here’s what this looks like:

Another point of view

From the formula for doubling a point we get that

x₂ = m² – 2x₁

where

m = y′ = (3x₁² + a) / (2y₁)

And because x₂ = x₁ we can write

x₁ = m² – 2x₁

or that

m² = 3x₁

Now if we have that

y² = x³ + ax + b

then we have that

2 y y′ = 3x² + a

and that

2 y y′′  + 2 (y′)² = 6x

so that

y′′ = (6x – 2 (y′)²) / (2y)

This means that we have y′′ = 0 when

6x – 2 (y′)² = 0

or

(y′)² = 3x

or

m² = 3x

As we saw above, this happens at a point of order 3, so at a point of order 3 we have that y′′ = 0.

Using Pari for elliptic curves

I recently tried Pari, a piece of software that’s designed for doing number-theoretical calculations – like those you need to do in cryptography. After using it for a few hours, I have to say that I’m very impressed by it. It has lots of built-in functions for doing calculations involving elliptic curves, and because lots of the technology that we use at Voltage involves elliptic curves, I found that very useful.

On the other hand, Pari seems to assume that you already know a lot about things before you start using it. Here’s an example of defining the elliptic curve y² = x³ + 1 and finding all of the points of finite order on the curve:

 

The ellinit() function initializes a data structure for an elliptic curve, but what it tells you when it does this probably isn’t useful to most people. Here's how the Pari User's Guide explains the output of ellinit():

a1-a6,b2-b8,c4-c6: coefficients of the elliptic curve

area: volume of the complex lattice defining E

disc: discriminant of the curve

j: j-invariant of the curve

omega: [ω₁,ω₂], periods forming the basis of the complex lattice defining E (ω₁ is the real period and ω₂ belongs to Poincare's half-plane).

eta: quasi-periods [η₁,η₂] such that η₁ω₂ - η₂ω₁ = 2πi.

roots: roots of the associated Weierstrass equation

tate: [u²,u,v] in the notation of Tate

w: Mestre's w (this is technical)

The elltors() function finds all of the points of finite order. Its output is slightly more user-friendly, but it’s probably not obvious to most people what it’s telling you.

So overall, I’d have to say that I’m very impressed with Pari, and I’ll probably be using it a lot in the future. On the other hand, I can’t really recommend it for most people. If you feel comfortable reading Silverman’s The Arithmetic of Elliptic Curves, you’ll probably find it very useful. You'll also understand how to interpret the output of ellinit(). Otherwise, you might find its output a bit cryptic and tricky to interpret.

Visualizing complex multiplication

Here's an attempt to create a way to visualize elliptic curves with complex multiplication. With any luck, it will also give some insight into why the term "complex multiplication" is used.

An endomorphism of an elliptic curve is a homomorphism that maps points on the curve to other points on the curve. The multiplication-by-n maps

φ_n: P→ nP

all do this. For most elliptic curves, those are all the endomorphisms that exist, but some elliptic curves have other endomorphisms. Curves like those are said to have complex multiplication, and if we look at a few examples, it's not hard to see why it's called this.

Example 1

For the elliptic curve

y² = x³ + x

the mapping given by

φ(x,y) = (-x,iy)

is an endomorphism that’s not a multiplication-by-n map. It also has the property that

φ²(P) = φ∘φ(P) = (x,-y) = -P

Because φ² acts roughly like multiplication by -1, we can think of φ as acting roughly like multiplication by the complex number  i.

If we think of this elliptic curve as being parametrized by the Weierstrass ℘-function with periods ω₁ and ω₂, we find that

ω₁ = 1.85407 – 1.85407 i

and

ω₂ = 1.85407 + 1.85407 i

Note that ω₂ = iω₂.

Here’s what the lattice L of points nω₁ + mω₂ looks like:

 

Here's what multiplication by i does to a typical point in this lattice:

 

Note that this lattice has the property that iL = L, so the same multiplication by i that maps points on the elliptic curve to other points on the curve also maps points in the lattice to other points in the lattice.

Example 2

For the elliptic curve

y² = x³ + 1

we have that the mapping given by

φ(x,y) = (ξx,y)

where

ξ = e^2πi/3, a complex cube root of 1 that's also a root of x² + x + 1 = 0

is an endomorphism that’s not a multiplication-by-n map. It also has the property that

φ³(x,y) = φ∘φ∘φ(x,y) = (x,y)

Because φ³ acts roughly like multiplication by 1, we can think of φ as acting roughly like multiplication by the complex number ξ.

If we think of this elliptic curve as being parametrized by the Weierstrass ℘-function with periods ω₁ and ω₂, we find that

ω₁ = 2.10327 -1.21433 i

and

ω₂ = 2.42865 i

Note that we have that ω₂ = ξω₁.

Here’s what the lattice L of points nω₁ + mω₂ looks like:

 

Here's what multiplication by ξ does to a typical point in this lattice:

Note that this lattice has the property that ξL = L, so the same multiplication by ξ that maps points on the elliptic curve to other points on the curve also maps points in the lattice to other points in the lattice.

Example 3

Consider the elliptic curve

y² = x³ - 4320 x + 96768

If we think of this elliptic curve as being parametrized by the Weierstrass ℘-function with periods ω₁ and ω₂, we find that

ω₁ = -0.296858 i

and

ω₂ = 0.419821

Note that ω₂ = √2iω_1.

Here’s what the lattice L of points nω₁ + mω₂ looks like:

 

In this lattice, if we multiply a point z by (√2i)² we get the point -2z. This looks something like this: 

This will also be reflected in the points on the elliptic curve, so this curve has complex multiplication by √2i. In this case, however, it's not at all obvious what the endomorphism is that's not a multiplication-by-n map.

Making change

My wife went out for pizza last week and came back with an incredible story. She ordered two pizzas on-line and went to the store to pick them up. When she arrived at the pizza store their computer was down. When she paid with cash, she was surprised to see the cashier pull out a calculator that she used to calculate the change due from my wife's purchase. The cashier explained that they had to use a calculator to figure out how much change to give a customer and that they would get fired if they were caught making change without the use of the calculator.

I'd guess that the pizza store didn't just make the use of calculators mandatory for no reason. They almost certainly did this because their employees couldn't do it accurately without a calculator.

It's somewhat popular these days to criticize the exit exam that California high school students have to pass to graduate. Opponents like to say that it forces teachers to teach just the material that's covered on the test, and that this reduces the overall quality of education. Supporters of the exam maintain that it's just testing basic skills and that its requirements are quite reasonable. If pizza stores have to require their employees to use calculators to make change accurately, I'd guess that the exit exam isn't testing enough.

The fact that people can pass the exit exam and still can't make change accurately may account for the following joke:

Question: What is 2+2?

Answer: A question on the California high-school exit exam

Another example of rational points on an elliptic curve

Here's another example of finding rational points of finite order on an elliptic curve.

Suppose that we have the elliptic curve y² = x³ - 2x + 1. In this case we have that D = 5, so that the possibilities for the y-coordinate of a rational point of finite order are limited to 0, ±1 by the Nagell-Lutz theorem. A quick check of these possibilities shows that we have the following points:

P₁ = (1,0)

P₂ = (0,1)

P₃ = (0,-1)

Here's what this looks like:

These points form this subgroup of the points on the curve:

Rational points on y² = x³ - 2x + 1

+	O	P1	P2	P3
O	O	P1	P2	P3
P1	P1	O	P3	P2
P2	P2	P3	P1	O
P3	P3	P2	O	P1

We can also think of the elliptic curve y² = x³ - 2x + 1 as being parameterized by the Weierstrass ℘-function with periods ω₁ and ω₂ where we have approximately

ω₁ = -2.01891 i

and

ω₂ = 2.96882

All of the points on y² = x³ - 2x + 1 that have the property 4P = O come from the complex numbers shown here: 

 
Of these 16 points, these are the ones that we get the subgroup of rational points of finite order from (z₁ corresponds to P₁, etc., and z₀ corresponds to O):

Why use projective coordinates?

Projective coordinates are often used to represent points on an elliptic curve. This is useful for two reasons. It provides an easy way to represent the point O on an elliptic curve using the same coordinate system that all of the other points use. It also may be more efficient to do operations on projective coordinates than on the usual, or affine, coordinates.

Projective coordinates represent ratios of numbers instead of just numbers. So the number 4 could be represented as either 4 = 4/1 or as 4 = 8/2, which we would write as (4,1) and (8,2) in projective coordinates. Clearly, there's not a unique way to represent affine points in projective coordinates.

To encode the point at infinity, we just set the last coordinate to 0, using division of anything by 0 to indicate infinity.

If we have to numbers x₁ and x₂ we can write them in projective coordinates as

x₁ = X₁/Z₁

or

(X₁,Z₁)

and

x₂ = X₂/Z₂

or

(X₂,Z₂)

If we want to calculate x₁/x₂ we can use the projective coordinates to find that

x₁/x₂ = (X₁/Z₁) / (X₂/Z₂)

= X₁Z₂ / X₂Z₁

which we can write as

(X₁Z₂,X₂Z₁)

in projective coordinates.

Note that this means that we've actually calculated x₁/x₂ without using any division operations at all. The tradeoff is that it takes more operations to implement projective operations. In this example, we've calculated x₁/x₂ without using any division operations, but at the cost of using two multiplications instead of one division. But if division operations are significantly more expensive that other operations, this can be a useful way to avoid using the more expensive operation.

There are actually more than one way to define projective coordinates in a useful way for points on elliptic curves. The most common way writes an affine point

P = (x,y)

as the projective point

P' = (X,Y,Z)

where

x = X/Z

and

y = Y/Z

This form of projective coordinates also has the advantage that division operations on coordinates can be implemented without using any division operations. Whether or not it's actually preferable to using affine coordinates depends on exactly how fast additions, subtractions, multiplications and divisions are on a particular platform.

The discriminant of an elliptic curve

 

If you're a fan of using high-powered techniques to solve easy problems, you can replace the first step with this.

Pokemon combinatorics

Collectable card games are incredibly popular. The cards for these games are typically sold in packages of several cards. The manufacturers print several sheets of cards, and include cards from the different sheets in these packages with different frequencies. They might include four cards from sheet A, two cards from sheet B and a single card from sheet C, calling the cards from sheet A “common,” the ones from sheet B “uncommon” and the cards from sheet C “rare.” Your ability to complete a collection of the entire set of cards is clearly limited by your ability to collect all of the rare cards.

How many packages of cards can you expect to have to buy before you complete a set?

A solution to this problem was described by Paul Erdős and Alfréd Rényi in 1961. Here’s roughly how their solution goes.

Suppose that we already have k different rare cards out of a total set of n possible cards. The next time we buy a pack of cards the probability to not get a new rare card is k/n so the probability that we need to buy exactly p packs of cards to get another new rare card is

(k/n)^p-1 (1 - k/n)

so the expected number of packs of cards that we’ll need to buy to a new rare card is

Σ_p≥1 (k/n)^p-1 (1 - k/n) p = 1 / (1 - k/n)

= n / ( n - k)

So the expected number of packs of cards that we’ll need to buy to get all n rare cards is

Σ_k=0:n-1 n / ( n - k) = n/n + n/(n - 1) + … + n/2 + n/1

= n (1/n + 1/(n - 1) + … + 1/2 + 1/1)

= n H_n

So you should expect to buy packs equal to about H_n times the number of rare cards to get a complete set. If there are 50 rare cards in a set, for example, you should expect to buy about H₅₀ (approximately 4.5) times 50, or about 225 packs to get a complete set.

Here's how H_n grows as a function of n:

So for the number of rare cards in a typical set of collectable cards, a good rule of thumb is that you can expect to have to buy a number of packs of cards equal to between four and five times the number of rare cards to complete your set.

Marginally interesting

 

Here's a picture of a notable page from a relatively unknown book. Apparently the right margin was just big enough to hold this:

Cubum autem in duos cubos, aut quadrato-quadratum in duos quadrato-quadratos, et generaliter nullam in infinitum ultra quadratum potestatem in duos eiusdem nominis fas est dividere cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.

Elliptic curves - connected or not

The graphs of some elliptic curves have one component like this one, the graph of y² = x³ + 1.

 

Others have two components like this one, the graph of y² = x³ – 2x + 1.

It turns out to be easy to tell these two cases apart. If the elliptic curve is defined by the equation y² = x³ + ax + b and we write D = -4 a³ - 27 b², then if D > 0 then the graph of the elliptic curve has two components and if D < 0 then the graph has one component. Here’s why.

D is the discriminant of the cubic f(x) = x³ + ax + b. So if we write

x₃ + ax + b = (x – x₁)(x – x₂)(x – x₃)

then we have that

D = (x₁ – x₂)²(x₁ – x₃)²(x₂ – x₃)²

Whether the graph of y² = f(x) has one or two components is determined by how many real roots f(x) has. If there is a single real root then the graph crosses the x-axis once and the graph has a single component, like we get with y² = x³ + 1. If there are three real roots then the graph then the graph crosses the x-axis three times and the graph has two disconnected components, like we get with y² = x³ – 2x + 1.

If f(x) has three real roots then D is clearly positive. What about the case of a single real root and a complex conjugate pair of roots?

Let’s write the roots of f(x) as

x₁ = a + bi

x₂ = a - bi

x₃ = c

where a, b and c are real. We can then write

D = (x₁ – x₂)²(x₁ – x₃)²(x₂ – x₃)²

= ((a + bi)– (a – bi))²(a + bi – c)²(a - bi – c)²

= (2bi)²((a - c) + bi)²((a – c) – bi)²

= -4b²((a - c)² + b²)

which is always negative, just like we wanted.

Rational points on elliptic curves

If you look at the rules for adding points on an elliptic curve, you'll see that the coordinates of P₃ = P₁ + P₂ are rational functions of the coordinates of P₁and P₂. This means that if P₁and P₂ have rational coordinates then P₃ also does because its coordinates are rational functions of these rational coordinates.

It turns out that rational points on an ellipic curve also have other interesting properties. In particular, rational points of finite order have to have integer coordinates and the y-coordinate of these points has to either be 0 or divide the discriminant of the cubic that defines the elliptic curve. This is the Nagell-Lutz theorem, which is the following:

Let y² = x³ + ax + b be an elliptic curve over the rationals with integer coefficients and let D = 4 a³ + 27 b². Then if P = (x_P,y_P) is a rational point of finite order then P has integer coordinates and either y_P = 0 or y_P²|D.

Example

Suppose that we have the elliptic curve y² = x³ + 1. In this case we have that D = -27, so that the possibilities for the y-coordinate of a rational point of finite order are limited to 0, ±1, ±3. A quick check of these possibilities shows that we have the following points, and the Nagell-Lutz theorem tells us that that's all of them:

P₁ = (-1,0)

P₂ = (0,1)

P₃ = (0,-1)

P₄ = (2,3)

P₅ = (2,-3)

Here's what this looks like:

 

It's also easy to check that these points plus O form a subgroup of the points on the curve. If you add any two of these points together you always get another of of these points. Here's this subgroup:

Rational points on y² = x³ + 1

+	O	P1	P2	P3	P4	P5
O	O	P1	P2	P3	P4	P5
P1	P1	O	P5	P4	P3	P2
P2	P2	P5	P3	O	P1	P4
P3	P3	P4	O	P2	P5	P1
P4	P4	P3	P1	P5	P2	O
P5	P5	P2	P4	P1	O	P3

We can also think of the elliptic curve y² = x³ + 1 as being parameterized by the Weierstrass ℘-function with periods ω₁ and ω₂ where we have approximately

ω₁ = 2.10327 + 1.21433 i

and

ω₂ = 2.42865 i

All of the points on y² = x³ + 1 that have the property 6P = O come from the complex numbers shown here: 

   

Of these 36 points, these are the ones that we get the subgroup of rational points of finite order from (z₁ corresponds to P₁, etc., and z₀ corresponds to O):

   

Degenerate elliptic curves

Suppose that we have an elliptic curve of the form

y² = 4 x³ - g₂ x - g₃

Many mathematicians require that the right hand side of that equation have no repeated roots and insist that you really don't have an elliptic curve if this happen. The benefit of doing this is that it saves a few words. If you don't do that then you need to be careful to say something like a "non-singular elliptic curve" instead of just an "elliptic curve" in most contexts. Because this post is about the cases where you have repeated roots, I won't follow this convention here.

What happens if we do have repeated roots?

Two repeated roots

For an example of this, consider the elliptic curve

y² = 4 (x - 1)² (x + 2)

= 4 x³ - 12 x + 8

or where

g₂ = 12

and

g₃ = -8

This corresponds to the Weierstrass ℘-function with periods

ω₁ = -π i / √3

and

ω₂ = ∞

or really only being having one period instead of two. If we plot the magnitude of this ℘-function, this is fairly obvious. Here's what that looks like.

Three repeated roots

There's essentially only one way to get three repeated roots, and that's the case when we have an elliptic curve that looks like

y² = 4 x³

or that

g₂ = g₃ = 0

If that happens, the ℘-function shows no periodic nature at all. Here's what a plot of its magnitude looks like in this case:

 

From the post a few days ago, we can see that in this case we have to have

℘(z) = z^-2

which explains the shape of this graph. We also have to have

℘′(z) = -2 z^-3

When we think of (x, y) as coming from (℘(z), ℘′(z)), we see that we have

y² = 4 x³

when this happens.

More interesting elliptic curve stuff

It turns out that we can easily tell some things about an elliptic curve of the form

y² = 4 x³ - g₂ x - g₃

Suppose that we get this elliptic curve from the Weierstrass ℘-function with periods ω₁ and ω₂. Then it turns out that we we can also write this elliptic curve as

y² = 4 (x - x₁)(x - x₂)(x - x₃)

where

x₁ = ℘(ω₁ / 2)

x₂ = ℘(ω₂ / 2)

and

x₃ = ℘((ω₁ + ω₂) / 2)

For an example of this, consider the elliptic curve

y² = 4 (x - 1)(x - 2)(x + 3)

= 4 x³ - 28 x + 24

which we get from the Weierstrass ℘-function with periods approximately

ω₁ = -1.48441 i

and

ω₂ = 2.01891

In this case, we find that 

℘(ω₁ / 2) = -3

℘(ω₂ / 2) = 2

and

℘((ω₁ + ω₂) / 2) = 1

Adding points on an elliptic curve

An interesting identity that can be proven for the Weierstrass ℘-function is that

det

℘(z1) ℘′(z1) 1 ℘(z2) ℘′(z2) 1 ℘(z1+z2) -℘′(z1+z2) 1

=

0

If we think about this for a while, we see that this is explains why addition of points on elliptic curves works the way it does. Here's why.

A fact that's usually covered in high-school algebra classes is that

det	x1 y1 1 x2 y2 1 x3 y3 1	=	0

if and only if the three points (x₁,y₁), (x₂,y₂) and (x₃,y₃) are colinear.

Now from the point of view of the correspondence that we saw in the previous post that identified the complex number z with the point (℘(z),℘′(z)) on an elliptic curve, let's write

P₁ = (℘(z₁), ℘′(z₁))

P₂ = (℘(z₂), ℘′(z₂))

and

P₃ = (℘(z₁+z₂), ℘′(z₁+z₂))

So the property of the ℘-function that's shown above tells us that although the points P₁, P₂ and P₃ aren't colinear, if we reflect P₃ across the x-axis to get -P₃, then we get three points that are.

So to find P₃ from P₁ and P₂, we need to first find the third point where the line that connects P₁ and P₂ intersects the elliptic curve. This point will be -P₃. Once we find that point, we reflect it across the x-axis to get P₃.

If we do this, we add the point P₁ that we get from z₁ to the point P₂ that we get from z₂ and get the point P₁ + P₂ = P₃ that we get from z₁ + z₂. In other words, adding points on an elliptic curve is really just adding complex numbers, but hidden by the mapping that takes z to the point (℘(z),℘′(z)) on the elliptic curve.

An example

For an example of how this works, let's look at the elliptic curve

y² = 4 x³ - 4x + 4

which we get from the Weierstrass ℘-function with periods approximately

ω₁ = -2.19658 i

and

ω₂ = 2.35354 + 1.09829 i

We have these two points on the curve

P₁ = (-1,2) = (℘(z₁),℘′(z₁)) for z₁ = 0.291202 + 1.09829 i

P₂ = (0,3) = (℘(z₂),℘′(z₂)) for z₂ = 0.73997 + 1.09829 i

for which we find that

P₃ = P₁ + P₂ = (1,-2) = (℘(z₃),℘′(z₃)) for z₃ = 1.03117

We also find that we have that

z₃ ≡ z₁ + z₂ (mod ω₁, ω₂)

just like we would expect to see.

Parameterizing elliptic curves

Here's an example of parameterizing an elliptic curve of the form

y² = 4 x³ - g₂ x - g₃

using the Weierstrass ℘-function.

Consider the elliptic curve

y² = 4 (x - 1)(x - 2)(x + 3)

= 4 x³ - 28 x + 24

This is a handy elliptic curve to use because we can easily see where its graph crosses the x-axis, etc. Identifying this with

℘′(z)² = 4 ℘(z)³ - g₂ ℘(z) - g₃

we have that

g₂ = 28

and

g₃ = -24

To plot the graph of this elliptic curve when it's parameterized as (℘(z), ℘′(z)) we first need to find the periods ω₁ and ω₂, which we can find from g₂ and g₃. Those turn out to be approximately

ω₁ = 1.48441 i

and

ω₂ = 2.01891

Here's what the magnitude of the corresponding ℘-function looks like over a few of its periods (graphed using Mathematica, as usual).

If we then plot the graph of (℘(z), ℘′(z)) as z goes along the real line from 0.7 to 1.4,  we get the following graph, which is the graph of y² = 4 x³ - 28 x + 24:

 

Another example

Doing the same thing for

g₂ = 4

and

g₃ = -4

and plotting the graph of (℘(z), ℘′(z)) as z goes along the real line from 0.7 to 4.0 we get this, which is the graph of y² = 4 x³ - 4 x + 4:

That's definitely another elliptic curve.

Why elliptic curves make sense

The way in which we can add points on an elliptic curve is often presented in a way that doesn't explain at all why adding points in that way makes sense. Adding points can roughly be summarized like this:

1. Draw a line through the two points that you want to add together
2. Find the third place where this line intersects the elliptic curve
3. Reflect that point across the x-axis and call the resulting point the sum of the first two points

Doing this actually makes perfect sense, but seeing why requires looking at a particular elliptic function called the Weierstrass ℘-function.

An elliptic function is a function of a complex variable that's doubly periodic: it has two periods instead of one. This means that we have both

f(z ) = f(z + ω₁)

and

f(z) = f(z + ω₂)

for complex numbers ω₁ and ω₂. 

It turns out that the function defined by

℘(z ) = z^-2 + Σ [ (z - ω)^-2 - ω^-2]

where the sum is over all ω = n₁ω₁ + n₂ω₂ not equal to zero, is an elliptic function with periods ω₁ and ω₂, and this particular elliptic function is called the Weierstrass ℘-function.

If we write

G_k = Σ ω^-2k

where the sum is over all ω = n₁ω₁ + n₂ω₂ not equal to zero, we find that we can write

℘(z) = z^-2 + 3 G₂ z² + 5 G₃ z⁴ + ...

and

℘′(z) = -2 z^-3 + 6 G₂ z + 20 G₃ z³ + ...

and that we can use these to find that we have that

℘′(z)² = ℘(z)³ - 60 G₂ ℘(z) - 140 G₃

For historical reasons it's traditional to write

g₂ = 60 G₂

and

g₃ = 140 G₃

so that we have that

℘′(z)² = ℘(z)³ - g₂ ℘(z) - g₃

If we write

 y = ℘′(z)

and

x = ℘(z)

we then have

y² = 4 x³ - g₂ x - g₃

which is just a quick change of variable away from the form that we usually see for an elliptic curve:

y² = x³ + a x + b

So it looks like we can parametrize an elliptic curve using the ℘-function just like we can parametrize a circle

x² + y² = 1

as

cos²t + sin²t = 1

using the usual trigonometric functions.

And just like understanding the properties of the trig functions tells us how to understand what's happening on a circle, understanding the ℘-function tells us how to understand what's happening on an elliptic curve. Like the addition of points.

More on that tomorrow.

Linear recursions and geometric series

As I mentioned in a previous post, one way to look at a linear recursion is as a matrix. When you do this, it's natural to think about the eigenvalues and eigenvectors of that matrix, and the eigenvectors turn out to be the initial conditions for the recursion that get it to greate a geometric series. We can use this fact to create an nth order recursion that creates n different geometric series of our choice, with the particular series being created determined by the initial conditions of the recursion. So if we pick any two numbers, it's possible to find a single second-order linear recursion that we can make create a geometric series with our chosen numbers as the ration of consecutive terms. Which ratio we get is determined by the initial conditions for the recursion.

Suppose that we write the recursion

x_n = a_k-1 x_n-1 + … + a₁ x_n-k+1 + a₀ x_n-k

as

xn-k+1 ... ... xn

=

0 1 ... 0 1 a0 a1 ... ak-1

xn-k ... ... xn-1

If λ is a solution to

x^k – a_k-1 x ^k-1 - … - a₁ x – a₀ = 0

then

1 λ ... λk-1

is an eigenvector that corresponds to the eigenvalue λ, and this eigenvector is also the initial state that turns the recursion into a geometric series: if we have

x₀ = 1, x₁ = λ, x₂ = λ², …, x_k-1 = λ^k-1

then we’ll always have x_n = λⁿ.

This means that for an nth order recursion, we can pick any n values λ_i (which are exactly these eigenvalues), and find initial conditions for the recursion such that x_n = λ_iⁿ. The eigenvectors are the initial conditions that do this, and they get the recursion to create a geometric series with the ratio between successive terms being the eigenvalue which corresponds to the eigenvector. It's also easy to write down the recursion that does this for us. In particular, if the eigenvalues are the roots of

x^k – a_k-1 x ^k-1 - … - a₁ x – a₀ = 0

then the recursion

x_n = a_k-1 x_n-1 + … + a₁ x_n-k+1 + a₀ x_n-k

does this for us.

An example

Suppose that we want to find a second-order recursion that will create either the series

x_n = (-2)ⁿ

or

x_n = 3ⁿ

This corresponds to having

λ₁ = -2

and

λ₂ = 3

for the zeroes of

(x - λ₁) (x - λ₂) = (x + 2) (x - 3)

= x² - x - 6

so that the recursion

x_n+2 = x_n+1 + 6 x_n

will do this for us.

The initial conditions

x₀ = 1

and

x₁ = -2

give

x_n = (-2)ⁿ

and the initial conditions

x₀ = 1

and

x₁ = 3

give

x_n = 3ⁿ

The Fibonacci sequence, the golden ratio and Egyptian fractions

It turns out that there's a way to use the Fibonacci sequence to write the golden ratio in terms of Egyptian fractions. Here's how.

If we write the Fibonacci sequence as

f(n + 2) = f(n + 1) + f(n)

then we can write

f(n) = (aⁿ – bⁿ) / (a – b)

where

a = (1 + √5) / 2

and

b = (1 – √5) / 2

Using this form of f(n) it's easy to show that

f(n)² – f_n+1 f_n-1 = (-1)^n-1

which we can rewrite as

f_n+1 / f_n = f_n / f_n-1 + (-1)^n-1 / (f_n f_n-1)

But we also have that

f_n / f_n-1 = f_n-1 / f_n-2 + (-1)^n-2 / (f_n-1 f_n-2)

so that

f_n+1 / f_n = f_n-1 / f_n-2 + (-1)^n-2 / (f_n-1 f_n-2) + (-1)^n-1 / (f_n f_n-1)

If we keep making similar substitutions, we find that we get that

f_n+1 / f_n = f₂ / f₁ + 1 / f₁ f₂ - 1 / f₂ f₃ + … + (-1)^n-1 / f_n-1 f_n-2

The golden ratio a is the limit of f_n+1 / f_n as n gets large, so we have that

a = f₂ / f₁ + 1 / f₁ f₂ - 1 / f₂ f₃ + 1 / f₃ f₄ + …

= 1 + 1 - ¹⁄₂ + ¹⁄₆ - ¹⁄₁₅ + ...

Each of the terms in this sum happen to be fractions of the form ¹⁄_n for some integer n, which are exactly the so-called Egyptian fractions. Apparently, the classical Egyptians used only fractions of that form, plus the single additional fraction ²⁄₃, to represent all rational numbers.

If you try to actually do a few computations with Egyptian fractions, you'll probably come to the same conclusion that I did: that representing rational numbers this way is probably one of the greatest technical blunders of all time.

In any event, the above representation for the golden ratio that we got from the Fibonacci sequence is actually a way to represent it as a sum of Egyptian fractions. Yet another aspect of the Fibonacci sequence that I didn't expect.