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

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

Our intention is that with this information, others can write client
programs 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 (INRIA), John, Adrian, Dimitris, Alex (British Telecom)

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

Consider the points (0 : 1 : 0) and (x : y : 1) with
y^2 + x*y = x^3 + a*x^2 + b in the field (Z/2Z)[u] / (Z/2Z)[1 + u^38 + u^89].
Here:

  a = 0x095AA3E660B75E77315E94E
  b = 0x1AC2701C6C54021D1BF0A72

(the coefficients are encoded as hex integers by "setting u to 2").

Let g = 2^88 + 12377169451261. There are 2*g points.  Under the
usual chord-and-tangent operation, they form a group.  We will work in
the subgroup of squares which has order g.

Let point P be the base of the logarithm:
  P = (0x1675C1BC9BD234852E8123C : 0x0426B727619B0E93561C6A3 : 1)

Let Q be the point whose logarithm is to be found:
  Q = (0x1BE721F8E3B6DBEE40DCE98 : 0x04DD88A4BDAD73E0B32EBB3 : 1)

For 0 <= k < 15, fix u_k = 3141592653^(k+1) mod 2^32.

Start by taking random v with 0 <= v < g and setting u := 0.

Then loop:

  Let R = [u] P + [v] Q in the group of points, get its x-coordinate,
  reduce mod 1 + u^38 + u^89 and encode as an integer, giving t.

  If bits 34..63 of t are all zero, R is "distinguished" so output it,
  quit the loop and start from scratch.

  m := bits 60..63 of t
  if m < 15
    u += u_m
  else
    u *= 2
    v *= 2
  endif

end loop.


The format for distinguished points is a line:

ECC2-89 s <23> i <12> x <23> y <23> z <1> u <23> v <23> <CLIENT> <VERSION> <FROM> ;<FREEFORM>

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

  s, the initial random value of v
  i, the number of iterations performed for this point
  x, y and z, the coordinates reduced mod 1 + u^38 + u^89
  u and v reduced mod g

Furthermore <CLIENT> is a word (no spaces) indicating the name of the
client program.  <VERSION> is a version number.  <FROM> is a word
indicating who is sending the distinguished point e.g., "anonymous".
<FREEFORM> is anything you like.

Here is a sample line:

ECC2-89 s 04d2359ed7e56f1b739f597 i 000002cab704 x 01bf929000000012ad2e875 y 16b3037663fd84f4df83081 z 1 u 0e6acd388987b6e26dfc33e v 0aa8ccf269234fc902a2a69 RobsECDL2-89 100 Robert.Harley@inria.fr ;


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
implementation at:
  http://pauillac.inria.fr/~harley/ecdl3/ecdl2-89.c.gz

please let us know!

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