Exploring Elliptic Curves in Digital Signatures

[Castilla]

Good morning to all.

By laboral reasons I am reading about digital signatures and "public key" cryptography. The most popular of the cryptographic methods related to digital signatures (RSA) is only an application of the "little Fermat theorem". This theorem belongs to "baby" number theory and it is in the scope of any amateur (myself, for example).

But there is another cryptographic method based on "elliptic curves" and the mathematics involved is no game at all.

Though I am not a formal student of mathematical analysis, I have learned some things reading by myself. I know more or less the basics of differential calculus on euclidean spaces. Also Riemann integration and the beginnings of Lebesgue integration (this on the real line only).

And why I post this here? Well, to ask if you know how much Analysis is needed to begin a serious study of elliptic curves.

Thanks for your answers.

 

[matt grime]

None, zip, doodah, diddly squat. (I only did that because writing zero gives a 4 letter reply and that is not allowed).

 

[Castilla]

I believed that elliptic curves had something to do (albeit little) with elliptic integrals...

 

[matt grime]

That has nothing to do with what is necessary to study them. They are also genus 1 riemann surfaces (over C), but as every genus 1 riemann surface is homeomorphic to any other genus 1 riemann surface there is no need to even consider the topological structure at all in some sense.

elliptic merely refers to some doubly periodic property (ie torus is a quotient of the complex plane by a lattice), and has no real bearing on whether or not you can start to study them in great depth. Read Cassell's book from the LMS, I don't think it really mentions analysis once. the important thing about elliptic curves is that they possesses an additive structure and that has bugger all to do with the analytic way of looking at them.

 

[Castilla]

Read Cassell's book from the LMS.

Which book is that?

 

[simul]

LMSST: 24 Lectures on Elliptic Curves (London Mathematical Society Student Texts) by J. W. S. Cassels

 

[Castilla]

Ok, thanks.

 

[thoms2543]

does anybody know where can i refer to for solving elliptic integral?

 

[mathwonk]

I not sure what you mean by solving them. These integrals became of interest long ago in the problem of comoutingn arclength of a lemniscate, and perhaps it was the bernoulli who noticed how hard they are to "rationalize". It turned out that rationalizing them would mean topologically mapping a sphere onto a torus by a branched cover which is impossible, so they must be studied by other means.

The first person to analyze their properties to some extent may have been Count Fagnano who learned how not to comopute arc length on a l;emniscate, but at elasy how to double it. I.e. he saw how to start from a given arc length, and not comopute it but find an arc of twice the length of the orioginal one. This is a harbinger of the addition property.

Then Euler saw how to generalize this and starting from two arc lengths, he showed how to find an arc whose length was their sum. All this is explained beautifully in the book Topics in Complex Analysis by C.L Siegel, the famous number theorist.

The book of Cassels is an outgrowth of a famous article he wrote decades ago on finding rational points on elliptic curves.

The addition law does have ana analytic incarnation, in that the Weierstrass P function maps the quotient group C/L where C is the complex numbers and L is a lattice subgroup, onto an elliptic curve in the plane.

Another version of the addition law is the fact that all lines in the plane meet a smooth cubic curve in triples of points which are equaivalent as divisors on the curve. This again because the addition law defioens a topological map from the simply connected projective space iof lines to the torus underlying the elliptic curve, which must be constant.

Tate gave some famous lectures on elliptic curves at Haverford colege severald ecades ago which have also become a book, and which require no analysis.

 

[mathwonk]

Intro to elliptic curves, from complex analysis standpoint:

816 4/03/98 Intro to Elliptic Curves

References: Serre, A course in arithmetic is a nice book to have. It has a chapter on modular forms, but is a little terse to read. Anthony Knapp, Elliptic Curves, Princeton Univ. Press, seems nice, and claims to cover the subject with only undergraduate background, and to discuss links between elliptic curves and fermat

 

[mathwonk]

Intro to elliptic curves

Intro to elliptic curves, from complex analysis standpoint:

816 4/03/98 Intro to Elliptic Curves

References: Serre, A course in arithmetic is a nice book to have. It has a chapter on modular forms, but is a little terse to read. Anthony Knapp, Elliptic Curves, Princeton Univ. Press, seems nice, and claims to cover the subject with only undergraduate background, and to discuss links between elliptic curves and fermat’s last theorem.
(you can order online at www//barnesandnoble.com)
Read: Cartan: III.5.5, pp. 97-99; V, 2.5, 153-157; VI, 5.1-5.3, 196-203.

Motivation: Solving polynomials f(x,y) = 0 especially over Z,Q. E.g. find all rational points on the circle x^2+y^2=1, equiv. find all integral solutions of the fermat equation x^2+y^2 = z^2. Idea: rationally parametrize the solutions, i.e. find rational functions x(t), y(t), in Q(t), such that x(t)^2+y(t)^2=1 for all t. Then for rational t we get rational solutions. Method of parametrization comes from geometry: find and choose one rational point on the circle like p = (0,1). Then draw all lines through this point and set up one one correspondence between the other intersection (x(t),y(t)) of the line with the point t where the line meets the real axis. then t = x/(1-y) and inverting gives x = 2t/(t^2+1), y = (t^2-1)/(t^2+1). Then t is rational iff x and y are, so this gives all rational points on the circle.


The same idea works for all curves of degree two, which have at least one rational point, i.e. from one rational point we can find all others this way.
The same idea rationalizes the familiar integral of (1-x^2)^(-1/2) . I.e. we want to make 1-x^2 a perfect square, so set x(t) = 2t/(t^2+1) as before. Then since y^2 = (1-x^2) if and only if x^2+y^2=1, setting y = (t^2-1)/(t^2+1) as before, gives a substitution that rationalizes the integral. I.e. we replace dx by (dx/dt)dt = 2(1-t^2)/(1+t^2)^2 dt, and y = (1-x^2)^(1/2) = (t^2-1)/(t^2+1), so the integral becomes -2dt/(1+t^2)
, which we can easily do by (complex) partial fractions. Of course we can also do it by trig, as we could have done the original integral. But the purpose of this exercise was to try to reduce to rational expressions if possible.
What if we could not figure out how to rationalize the integral? We could study the properties of the integral anyway. I.e. define a function f(x) = integral of (1-x^2)^(-1/2) from 0 to x, which makes sense for x near 0, where the integrand is continuous, and by the FTC gives a differentiable function with derivative 1/(1-x^2)1/2. If we invert this function, by the inverse function theorem, we get a function s(t) with derivative s’(t) = (1-s^2)^(1/2). I.e. we get the differential equation (s(t))^2 + (s’(t))^2 = 1. Hence we have a differentiable parametrization x(t) = s(t), y(t) = s’(t) for the circle, where we recognize of course the differential equation for the familiar sine and cosine functions.

Now we try cubic equations: e.g.. fermat equation x^3+y^3 = 1. These are called elliptic curves, so let the solution set be denoted E. This has a rational point too at (0,1). But what does the geometry tell us about the method of projection? This time a general line meets the cubic three times so we get a 2:1 projection onto the x axis, hence cannot invert the amp at least not rationally, although there is of course an analytic local inverse map. However analytic maps do not take rational points to rational points, so note that if we have not one but two rational points on our cubic then the third point is also rational. So what we do have is a binary operation on rational points. It turns out this defines a group law on the rational points, and of course since we also have a binary operation on all the points in the same way, we expect there is a group law on the complex and real points as well, which is true.

Now sometimes we meet a “degenerate” cubic which does not have the properties of general cubics, and does not deserve to be called an elliptic curve. E.g.. if we consider y^2 = x^2(x+1), there is a special point on it at the origin (0,0), such that all lines through this point meet the cubic further in at most one point. Just set x = au and y = bu and solve to get intersection points when u^2(b^2-a^2(au+1)) = 0, so that two of the solutions occur at t=0, and there is only one other at u = (a^2-b^2)/a^3. So, by inverting again, here we can parametrize the cubic using rational functions of some parameter t for the lines through the origin, like the slope t = b/a. Note also that if we were trying to rationalize the corresponding integral of [x^2(x+1)]^(-1/2) , it doesn’t look bad at all since we can immediately take out an x from the radical.

Now we claim in fact that it is impossible to parametrize a general cubic such as the fermat, by rational functions. Let’s try one similar to the last one but crucially different in one respect: y^2 = x(x^2+1). Do you see the essential difference between this one and y^2 = x^2(x+1)? Consider the implicit function theorem and apply it to the corresponding polynomials
y^2 - x(x^2+1), and y^2 - x^2(x+1). Notice that the first example satisfies the hypotheses of the IFT everywhere, while the second one has a point namely, (0,0) at which both partial derivatives vanish. This is the difference: the first one is a complex manifold everywhere and the second is not, but instead is “singular” at the one point (0,0). Such a point, at which the first non vanishing Taylor polynomial has degree two, is called a “double point”, and any (irreducible) cubic with a double point can be rationally parametrized. By the same method, any (irreducible) curve of degree n with a point of multiplicity n-1, such as y^(n-1) = x^(n-1)(x+1), can be rationally parametrized.

Definition: An “elliptic curve” is any non singular plane cubic curve. i.e. one for which the hypotheses of the IFT are true everywhere, including any points “at infinity” (which we will learn how to study later).

We claim that an elliptic curve can never be rationally parametrized. Note for this to be true, we must consider points at infinity in the definition of elliptic curve, as the following example shows:
If y = x^3 is our cubic, the corresponding polynomial f(x,y) = y-x^3 has y-partial derivative equal to ∂f/∂y = 1 which never vanishes, but the curve can be parametrized by projection on the x axis, as can any graph of any function of one variable. I.e. take x(t) = t, and y(t) = t^3. So at least this curve can be parametrized as we claim an elliptic curve cannot be. Note it is also trivially easy to find rational points on this curve by taking x rational. The secret is that to find the points at infinity, we “homogenize” the equation to get yz^2 = x^3, (note that setting z=1 would give back the original equation), then set the new variable z = 0, then solve for the only point with some coefficient not zero, i.e. (0,c,0), where c≠0. Then we dehomogenize by setting the non zero coefficient y=1, to get the equation z^2 = x^3, which has a point at (0,0). This is a double point which was “at infinity” for the original equation, but it caused the curve to be parametrizable.

Now let’s consider the example y^2 = x(x^2+1) = x^3+x. For simplicity let’s project on the x axis, taking (x,y) to x. This gives a 2:1 map of the curve on the x-axis with branch points at the roots of the polynomial x(x^2+1) = 0, so three branch points. But if we look also at infinity, by homogenizing to get
y^2z = x^3+xz^2, and then set z = 0, solving gives the one point (0,c,0) where c≠0. Thus there is a only one point at infinity, and so we have the full elliptic curve mapping 2:1 onto the completed x axis, i.e. onto the Riemann sphere P1, with 4 branch points. (I will show you how to calculate with these homogeneous coordinates later, but for now take my word for it that these homogeneous coordinate calculations do give this result.) We know such a double cover of the sphere is topologically a torus.

Now I claim that there is no rational parametrization of a curve whose complex points give a topological torus. If there were, then the rational parametrization functions can have complex values plugged into them too and become holomorphic functions on the Riemann sphere, mapping the sphere holomorphically onto our elliptic curve. But I claim that a holomorphic map of Riemann surfaces cannot raise the “genus” i.e. the number of handles of the target surface cannot exceed the number of handles of the domain surface. So a surface like the sphere with zero handles cannot map holomorphically onto a torus with one handle. To see this you must consider the topological Euler characteristic and the Euler formula V-E+F for computing it, and then use the local structure theorem for as holomorphic map. I.e. by the local structure theorem if we triangulate the target surface with very small triangles, and so as to include as vertices all branch points of the map, i.e. points with fewer than the usual number n of preimages, then the map has degree n, i.e. every point has n preimages except for some which have fewer. If we then triangulate the domain by using as triangles simply inverse images of triangles from the target, then we have n times as many triangles in the domain as in the target, n times as many edges, and at most n times as many vertices, and fewer if there are some branch points. By the Euler formula, if the number of handles in the target is t and the number of handles in the domain is d, and if V ,E, F are the numbers of vertices edges and faces in the target, then we have 2-2t = V-E+F. For the domain we have the corresponding formula, 2-2d = (nV) - (nE) + (nF-r) = n(2-2t) -r, where r is the missing number of vertices in the domain due to branching. If t =0 then surely d ≥ t. If t = 1, then 2-2t = 0, hence 2-2d < 0, so d ≥ 1 = t. If t>1, then 2-2t <0, hence 2-2d = n(2-2t)-r ≤ n(2-2t) < (2-2t), so d > t. I.e. the domain always has at least as many handles as the target, and more if the target has at least two.

Since we have parametrized rationally a degenerate cubic, it must not be topologically a torus, and in fact one can show the one above looks like a pinched torus, i.e. a sphere with two points identified.

Next we will show that every complex torus, i.e. every quotient of the complex plane by a lattice, is isomorphic to a non singular plane cubic curve. We will map it in by the familiar Weierstrass P-function and its derivative, which is obtained in the case of the curve y^2 = x(x^2+1), for example, by inverting the function defined by the “elliptic integral” = f(x). I.e. then (weierstrass)P(x) = f-1(x).

 

[mathwonk]

apparently the encoding methods based on elliptic curves use finite fields, and are based on the problem analogous to the difficulty of finding generators of the groups of units in finite fields.

look on the web.