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

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^3+a*x+b
in the field Z / p Z.  Here:

  a = 134463312896805761244606051
  b = 121489936031066440060440631
  p = 416363315556156604917983573


There are g = 416363315556124458285894983 points.  Under the usual
chord-and-tangent operation, they form a group.

Let point P be the base of the logarithm:
  P = (232349146313044524685417226 : 8425515734129553132973322 : 1)

Let Q be the point whose logarithm is to be found:
  Q = (268507436745473388067569197 : 51099634945595802171100073 : 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,
  multiply by 2^96, reduce mod p 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 := t mod 16
  if m < 15
    u += u_m
  else
    u *= 2
    v *= 2
  endif

end loop.


The format for distinguished points is a line:

ECCp-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 p
  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:

ECCp-89 s 0b5ba804fec5c14a8622c31 i 00000738dfab x 05ece20e1b794290579c333 y 04939fbc94f4cdaa508e111 z 1 u 02d17161405411089f8c7b1 v 13fdb988459307a914181cb RobsECDL 100 jcs@zoo.bt.co.uk ; BT Labs Team


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/ecdl2/ecdlp-89.c.gz

please let us know!

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