Elliptic curve calculator

What’s the cheapest calculator you know of? Basic calculators are much cheaper than their scientific counterparts, and you can probably get one for £2. A slide rule is even cheaper: you could strap together two plastic rulers with logarithmic scales for about 20p — a saving of an order of magnitude. Pretty impressive for a couple of sliding scales.

We can do much better than this, though. You can print a fully functional calculator, capable of multiplication, division and extraction of square roots, on a single sheet of A4 (or A3 for ‘double precision’!) paper. This is probably an order of magnitude again cheaper than a regular slide rule, costing about 2 pence.

Elliptic Curve Calculator

A sheet of paper capable of multiplication, division and square root computation, with similar precision to a slide rule but for one tenth of the price.

Clicking the above image will link to a full-size version, which you can print off and use. Note that it has two scales, red and blue, running in opposite directions on an elliptic (non-singular cubic) curve. The scales are reciprocals of each other; for any point labelled x in red and y in blue, xy = 1.

To multiply two numbers together, find them (ignoring decimal places; 10x and x are represented by the same point) in the same colour and draw a straight line through them. This will intersect the elliptic curve in a third point. Read the result off on the oppositely-coloured scale; this is the product of the two numbers!

Multiplication with the Elliptic Curve Calculator

Find two numbers (a and b) in the same colour (blue), and project a line through them to meet the curve in a third point. Read this off in the opposite colour (red) to obtain the product, ab.

Similarly, you can divide and compute square-roots, as shown in the pictorial instructions at the foot of the image. It’s very simple to use, but to explain why it works is much more difficult; it relies on some advanced algebraic geometry and group theory typically encountered in degree-level mathematics. If you really want to know why, continue reading. But be warned: the mathematics gets quite complicated.

It all boils down to the fact that the points on an elliptic curve form an Abelian group. This has a similar structure to the real numbers, which means that we can interchange between the two. (This is not so straightforward, requiring a transcendental function related to the Weierstrass P-function. I used repeated interval bisection and polynomial interpolation to obtain a good approximation instead.)

We define an operation on the points of the elliptic curve. We’ll represent this with a funky symbol such as @. For three collinear points on the curve, A, B and C, we say that A @ B @ C = e, where e is the identity element. It’s pretty obvious that B @ A @ C = e, as well, since the order of points on the line is unimportant. In other words, A @ B = B @ A — the group operation is commutative. It suffices only to show that A @ (B @ C) = (A @ B) @ C — associativity — before we can treat @ like addition or multiplication, which are themselves equivalent due to the exponential function. Proving associativity is possible with a lovely theorem called Cayley-Bacharach.

In my elliptic curve calculator, I have used @ to emulate multiplication. Division is rather routine, since it’s just reverse-engineering multiplication. Finding the point B with a tangent intersecting the curve at A is equivalent to solving A @ B @ B = e, so B is the square root of the reciprocal of A.

The geometry of elliptic curves has applications in advanced cryptography, where it offers superior security compared with ordinary RSA (Rivest-Shamir-Adleman). It’s very easy with repeated squaring to quickly compute the nth power (B = A @ A @ … @ A) of a point A on the curve. However, given A and B, it is very difficult to reverse-engineer the process to obtain n. This is known as the discrete logarithm problem. With some effort, it can be adapted into a cryptosystem similar to RSA, but in the setting of elliptic curves instead of modular arithmetic.

Elliptic curves were also the tools used by Andrew Wiles to prove (most of) the Tanayama-Shimura Conjecture and thus Fermat’s Last Theorem. The simplest proof of Poncelet’s porism also involves elliptic curves.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

12 Responses to Elliptic curve calculator

  1. David Stay says:

    When I tried out your calculator I found that for division you get 10a/b. For example 1/5=2

    • apgoucher says:

      Well spotted. For a real number x, the numbers {…, 0.1x, x, 10x, 100x, …} are all represented by the same point on the elliptic curve. It’s a consequence of the Weierstrass P-function being doubly periodic — everything wraps around.

  2. apgoucher says:

    Richard Guy (one of the early developers of combinatorial game theory) informs me that he had done something essentially equivalent about 60 years ago, entitled ‘a single scale nomogram’.

  3. Jason says:

    This is pretty cool! To find square roots, you look at tangent lines to other points; I don’t think the diagram explains this very well.

    • apgoucher says:

      Indeed. You start with your straightedge on a point x, and rotate it about x until it is tangent to the elliptic curve at a second point. This is either sqrt(x) or sqrt(10x). On a similar topic, the points of inflection of the curve correspond to 1, cbrt(10) and cbrt(100).

  4. Pingback: MODA: Diophantine equations | Complex Projective 4-Space

  5. Pingback: Cayley-Bacharach applications | Complex Projective 4-Space

  6. Pingback: Background Problem I | Complex Projective 4-Space

  7. Pingback: Noughts and Crosses | Complex Projective 4-Space

  8. Isaac Kuo says:

    I don’t understand the math of this elliptic curve, but now I want to make a spherical ball version, using a gnomonic projection. Imagine an orb Coke bottle, with this curve projected on it. Also, a great circle is marked.

    You fill the orb up to the great circle. Now, you can calculate by tilting the orb.

  9. Andrew Carlotti says:

    I tried doing 1.5*7, Adam, and your calculator didn’t work.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s