cr.yp.to update

diff -ru .old-crypto/2005-590.html cr.yp.to/2005-590.html
--- .old-crypto/2005-590.html	2005-03-30 21:31:20.000000000 -0500
+++ cr.yp.to/2005-590.html	2005-04-05 01:23:26.000000000 -0400
@@ -635,5 +635,57 @@
 is better than baby-step-giant-step.
 The Stein-Teske paper is a better introduction to the kangaroo method
 but says only a tiny bit about previous algorithms.
+<h2>4 April 2005</h2>
+Today I gave the following recursive definition of the Curve function.
+<p>
+Define p as the prime 2^255-19, and define A=257290.
+The input to Curve is a positive integer.
+The output is an element of {0,1,...,p-1,infty}.
+<p>
+Curve(1) is defined as 2.
+<p>
+If g = Curve(n)
+then Curve(2n) is defined as the quotient mod p
+of (g^2-1)^2 and 4g(g^2+Ag+1).
+This means infty when g = infty;
+it means infty when g(g^2+Ag+1) mod p = 0;
+otherwise it means the unique solution to
+(g^2-1)^2-4g(g^2+Ag+1) Curve(2n) mod p = 0.
+<p>
+If g = Curve(n) and h = Curve(n+1)
+then Curve(2n+1) is defined as the quotient mod p
+of (gh-1)^2 and (g-h)^2 Curve(1).
+This means infty when g = h (which actually can't happen);
+it means the unique solution to
+h^2-Curve(1) Curve(2n+1) mod p = 0
+if g = infty and h != infty;
+it means the unique solution to
+g^2-Curve(1) Curve(2n+1) mod p = 0
+if g != infty and h = infty;
+otherwise it means the unique solution to
+(gh-1)^2-(g-h)^2 Curve(1) Curve(2n+1) mod p = 0.
+<p>
+To compute Curve(nS) given n,Curve(S),
+use the fact that Curve(2nS) = (g^2-1)^2/4g(g^2+Ag+1) mod p
+where g = Curve(nS),
+and the magical fact that
+Curve((2n+1)S) = (gh-1)^2/(g-h)^2 Curve(S) mod p
+where g = Curve(nS) and h = Curve((n+1)S).
+<p>
+The traditional name for Curve(n)
+is ``the x coordinate of the nth multiple of (2,...)
+on the elliptic curve y^2=x^3+Ax^2+x
+over the field of p elements.''
+Some relevant sections of the Hankerson-Menezes-Vanstone book
+``Guide to elliptic curve cryptography'':
+<ul>
+<li>Section 2.1: Finite fields.
+<li>Section 3.1, through the end of 3.1.2:
+Definition of an elliptic curve
+and the elliptic-curve group law.
+<li>Algorithm 3.40: Computing x-coordinates of multiples of a point
+on the curve y^2+xy=x^3+Ax^2+b over a field of 2^m elements.
+The curve formulas are different but the idea is the same.
+</ul>
 </body>
 </html>