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 `-'
------------------------------------------------------------------------------