------------------------------------------------------------------------------ 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> ; Here 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 is a word (no spaces) indicating the name of the client program. is a version number. is a word indicating who is sending the distinguished point e.g., "anonymous". 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! ------------------------------------------------------------------------------