------------------------------------------------------------------------------

This is a precise, slightly technical description of what our
pseudo-random iteration is, of which points are considered distinguished,
and of the format for sending them in.

It is intended that with this information, others can write client programs
compatible with ours and work with us.  Working together makes sense for
"birthday paradox" algorithms since the number of pairs grows as the square
of the work done.  Rather than two groups doing a^2 and b^2 pairs
respectively, it's much better to work together and get (a+b)^2 pairs.

  Rob
  (Robert.Harley@inria.fr)

------------------------------------------------------------------------------

Consider the points (x:y:1) with y^2+x*y = x^3+1 in the field
(Z/(2))[t] / (t^97+t^6+1), and the point "at infinity" (0:1:0).

Let g = 2^95-94562993267977. There are 4*g points.  Under the usual
chord-and-tangent operation, they form a group.  We will work in the
subgroup of order g.

We are given two points P and Q and want to find the discrete logarithm of
Q to the base P i.e., the integer l modulo g such that Q = [l]P, where this
notation indicates repeating the chord-and-tangent operation l times.

For the ECC2K-95 problem:
  P = (0x08A84FB02034F7771DC940097 : 0x1D2F10A471D48A720F18F6339 : 1)
  Q = (0x0E0BC08AC5818F303E2B05E90 : 0x134C028FC3393124D673E6F8E : 1)

The coefficients are encoded as hex integers by "setting t to 2".


Start by taking random u and v with 0 <= u,v < g, such that R = [u]P+[v]Q
is finite.  Then do:

main loop:

  Let R = [u]P+[v]Q, get its x-coordinate, write it in the basis
  { (t+1)^(2^k) | 0 <= k < 97 } over Z/2Z and count the non-zero
  coefficients, giving m.

  If m is 20 then R is "distinguished" so output it, quit the loop and
  start from scratch.

  Multiply u and v by 2, 6, 88, 90 or 92 modulo g, according to m = 0,
  1, 2, 3 or 4 modulo 5.

end loop.


The format for distinguished points is a single line:

ECC2K-95|i|<12>|u|<25>|v|<25>|x|<25>|y|<25>|<client>|<version>|<user>|<team>|<machine>|<hardware>|<OS>|<comment>

Here <n> indicates a hexadecimal number of n hex digits, padded with zeroes
if necessary.  The values are:

  i: the number of iterations performed for this point,
  u, v: the multipliers reduced mod g,
  x, y: coordinates of R reduced mod t^97+t^6+1

Furthermore <client> indicates the name of the client program, <version>
indicates its version and so on.  None of these fields should contain the |
character.

Here is a sample line:

ECC2K-95|i|000003CAA36C|u|0429A7359C073562CF5BFB90D|v|037CEBBAE69347D2DA96508F5|x|18117939C5998990AD2DE3B26|y|19404AC36113516C438303E30|RobsECDL|Alpha 110|Robert Harley|INRIA|corton|alpha|Linux|500 MHz 21164a

Such lines should be sent by email to:
  ecdl@pauillac.inria.fr

or, if that fails, to:
  robert@vlsi.cs.caltech.edu


If you find any disagreements between this description and the
sample implementation at:
  http://pauillac.inria.fr/~harley/ecdl5/Alpha_111/source/ecdl2K-95.c
  http://pauillac.inria.fr/~harley/ecdl5/Alpha_111/source/ecdl2K-95.c.gz

please let me know!

------------------------------------------------------------------------------
Notes:

* Of course when the initial R is chosen at random it is overwhelmingly
  likely to be finite.  By checking that it really is we can ignore the
  z coordinate since it will always be 1:

  loop:
    u := random.
    v := random.
    R := [u]P+[v]Q.
  while R is infinite.

* For efficiency avoid computing R every main loop iteration, but do it
  incrementally something like:

  f := 1.
  i := 0.
  main loop:
    If R is distinguished set u,v := f*u,f*v, output i,u,v,x,y and restart.
    Multiply f by 2, 6, 88, 90 or 92 modulo g and update R accordingly.
    i := i+1.
  end loop.

* Those weird coefficients are chosen because 6 = -w^5-w, 88 = w^13-w^3,
  90 = w^13+w and 92 = w^13-w^2 where w = (-1+sqrt(-7))/2.  Multiplication
  by w is the Frobenius endomorphism which can be computed quickly by
  squaring the x and y coordinates.  This choice is quite ad-hoc but roughly
  doubles the iteration speed compared to choosing, say, 2, 3, 5, 7 and 11.
  (In general the multipliers could be any integers of Q(sqrt(-7)), but
  choose them multiplicatively independent up to sign and powers of w).

* Instead of actually multiplying f by 2,..,92 you can just keep track of
  the powers of 2,..,92 that it contains.  Furthermore since sign and powers
  of w don't affect the pseudo-random iteration, you can use 6 ~= w^4+1,
  88 ~= -w^10+1 etc. to reduce the number of squarings.  Then when a
  distinguished point is found, compute f, update u,v := f*u,f*v, get
  the true value of R := [u]P+[v]Q, output i,u,v,x,y and restart.

* You can use any basis you like for the arithmetic; the sample
  implementation uses the polynomial basis { t^k | 0 <= k < 97 } throughout.
  But for checking distinguishedness you must use the { (t+1)^(2^k) } one
  (in general any normal basis would do).

* If this algorithm seems a little complicated, it is because instead of
  iterating on points, we are "really" iterating on orbits of points under
  the involution [-1] and the Frobenius endomorphism [w].  The iterations
  take about 150% as long as when iterating directly on points but there are
  sqrt(2*97) fewer iterations needed so overall it's a big win.

  In general we could consider using extra automorphisms on curves with
  j-invariant 0 or 1728, using complex multiplication, etc.  I suggest
  reading Chapters III and V of Joseph Silverman's book for ideas.

* I would like to point out that this algorithm is not based on the two
  recent papers by Wiener and Zuccherato on one hand and Gallant, Lambert
  and Vanstone on the other.  This is independent work designed, implemented
  and tested on thousands of small examples prior to those being released.
  Any resemblance between our three independent discoveries of similar
  algorithms is probably due to the fact that they become blindingly obvious
  after staring at the problem for several months =8-)

* I would like to thank Ari Singer for not believing me back in February
  when I said that clustering the points gave no practical improvement for
  ECCp-97.  I was right but he forced me to think about the matter more!
  I would also like to thank Rob Zuccherato for sending his and
  Michael Wiener's paper, "Faster Attacks on Elliptic Curve Cryptosystems".

* It seems that there is no asymptotic improvement to be had for ECDL's
  over GF(2^n), with curves over GF(2), as n grows.  An elliptic curve
  operation takes time O(n^(1+epsilon)) when using a polynomial basis but
  changing basis or working directly in a normal basis takes O(n^2).
  Thus asymptotically we lose a factor O(n^(1/2-epsilon)) :-(

  For "small" cases there may be a constant-factor speedup in practice.
  The sample implementation for ECC2K-95 gains a factor of 10 or so compared
  to some test code for ECC2-97.

* Fire up those Alphas!

------------------------------------------------------------------------------