------------------------------------------------------------------------------ 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> ; 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 1 + u^38 + u^89 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: 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! ------------------------------------------------------------------------------