------------------------------------------------------------------------------ This message is copyright (c) Robert J. Harley, 1998. If you wish to quote more than one sentence, please quote the whole thing. To: certicom-ecc-challenge@certicom.com Robert J. Harley, Sèvres, France, 7th of February, 1998. Dear Mr. Gallant, The solution to Certicom's ECC2-89 problem is the residue class of 41871609686648820507900581 modulo 309485009821357445894232317. The calculation was carried out in 26 days by a group of 70 people in 17 countries. 95% of the work was done on Alpha workstations running Linux and Digital Unix and the remaining 5% was done on various 32-bit machines. The fastest, naturally, were 600 MHz Alpha systems doing 241 K elliptic curve operations per second each. The fastest 32-bit systems were 233 MHz StrongARM NCs running NetBSD at 55 K each. Several other systems contributed too including a bunch of Pentium and Pentium Pro machines with Linux, a few Sparcs with SunOS, a 150 MHz SGI MIPS with Irix, an old 80 Mhz HP PA with NextStep and a Cyrix 486 DX2. Last and definitely least were my trusty old 8 MHz ARM 2's running RISC OS (hey, they seemed fast ten years ago :). The people involved were: Wayne Baisley Miguel Barreiro Paz Uri Blumenthal Spider Boardman Alvin Brattli Bill Broadley Andries Brouwer Zach Brown Bruce Dawson Dr. Sven Dietrich Einar Doerum Dragisa Duric Martin Edu Gwyn Evans Douglas Frank Megan Gentry Rick Gorton Thomas Gschwind Oleg Gusev Mikolaj Habryn Robert Harley David Hauan Mike Iglesias Chatchai Jantaraprim Travis Johnson Martin Kahlert Asim Kepkep Rohit Khare Mika Kortelainen Andreas Krall Edward Lee Dr. Hiankiat Lee Leon Lessing Greg Lindahl Brian Lund Preda Mihailescu Francois Morain Pete Murray Jon Nathan Burkhard Neidecker-Lutz Wieger Opmeer Vance Petree Guillaume Pierre Martin Radford Jon Reeves Brian Romansky Geordy Rostad Tim Rowley Andrew Sapozhnikov Aaron Sawyer Mike Schloss Al Simons Mikko Siren Chris Smith Mark Smith Murray Stokely Adrian En-Wei Sun Peter Sward Marko Vendelin Paul Verwer Bill Viggers Bart-Jan Vrielink Dan Weeks Michael Wins Tom Woodburn Gregory Woodbury and the British Telecom team, some students of the Ecole Centrale de Lille and a person who prefers to remain anonymous. The method we used was a "birthday paradox" algorithm iterating from a random initial point (one per machine) with a pseudo-random function (the same on all machines) until a collision was detected at 16:21 today. A total of 18161819582507 iterations i.e., over 18000 billion, were performed finding 17543 "distinguished" points. Two of the points, found by Guillaume Pierre of INRIA and Bill Broadley of U.C.Davis, were in fact equal allowing us to compute the final answer. Since an ECC2-89 iteration took close to twice as long as an ECCp-89 iteration, this was the most difficult calculation we have done so far. Participants at INRIA found 3653 points using machines belonging to the following projects: Air, Algo, Codes, Coq, Cristal, Méval, Para, Sor and Sosso. Those at Digital found 4591 points, and others found 9299. Our source code can be downloaded from: http://pauillac.inria.fr/~harley/ecdl3/ We invite anyone interested in working on the next calculation to point their Web browsers at: http://pauillac.inria.fr/~harley/ecdl4/ Bye, Rob. .-. Robert.Harley@inria.fr .-. / \ .-. .-. / \ / \ / \ .-. _ .-. / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / `-' `-' \ / \ / \ \ / `-' `-' \ / `-' Linux + 500MHz Alpha + 256MB SDRAM = heaven `-' ------------------------------------------------------------------------------