[seqfan] Crypto EllipticK & A000984

Brad Klee bradklee at gmail.com
Wed Jul 5 00:26:08 CEST 2017


Hi Seqfans,

Recently I found the following presentation "ECCHacks" from Bernstein and
Lange at Chaos Congress 2014:

https://media.ccc.de/v/31c3_-_6369_-_en_-_saal_1_-_201412272145_-_ecchacks_-_djb_-_tanja_lange

Very nice, and easy to understand! By discussing the small-d limit, also
the wall-clock limit, Bernstein and Lange hint an analogy between the
Edward's curve and integrable Hamiltonian oscillations along one dimension.
To expand upon this possible connection, it's useful to enumerate
"time-dependence" of the addition formula.

Let {x1,y1} be arbitrary along the genus one Edward's curve

x^2 + y^2 - (1 + d * x^2 * y^2) = 0

and {x2,y2} a small displacement from the fixed point. We add these points
together using the addition rule:

{x1,y1} + {x2,y2} |---> {
 -(y1*y2 - x1*x2) / (1 - d*x1*x2*y1*y2),
 (x1*y2 + y1*x2) / ( 1 + d*x1*x2*y1*y2 )
 }

Assuming that small displacement {x2,y2} sets a time-scale "dt", we can
apply physical calculus. In polar coordinates where tan(phi) = y/x, we
construct the integrand for the addition rule time-dependence:

dt = dphi  / sqrt( 1 - 4*d*x^2 ) with x = cos(phi) * sin(phi)

This is essentially the generating function for A000984. The extensive
encyclopedia entry, one of the "core", does not appear to include reference
to the Edward's curve.

In polar-coordinate formulation, integration is easy as the integrand
expands in a Fourier cosine series of the 2Pi-periodic phi. Integrating
over one complete period yields a function proportional to EllipticK[d] (
cf. A038534 ), yet again! Probably this is all obvious to the experts???
Personally, I did not expect to get EllipticK out with so little hassle.
Ultimately re-discovery of EllipticK draws a quantitative connection
between ciphers using Edward's Curve and physical systems such as the
simple pendulum.

Cheers,

Brad


More information about the SeqFan mailing list