ECCp-89 solved!

Robert Harley (
Mon, 12 Jan 1998 18:47:24 +0100 (MET)

We've found the discrete logarithm for ECCp-89!

If you've got an Alpha and would like to work with us on the next one,
ECC2-89, point your Web browser at:


This message is copyright (c) Robert J. Harley, 1998.
If you wish to quote more than one sentence, please quote the whole thing.


Robert J. Harley,
Rocquencourt, France,
12th of January, 1998.

Dear Mr. Gallant,

Please note that this submission, like the previous two, carries a
copyright notice. If you wish to quote it on your Web pages, or
anywhere else, you may not strip off the copyright notice nor replace
it with "Copyright Certicom Corp." or any similar notice.

The solution to your ECCp-89 problem is the residue class of
333373190151749761757285479 modulo 416363315556124458285894983. The
calculation was carried out in 24 days by a group of 57 people using
Alpha workstations running Linux, Digital Unix, VMS and NetBSD:

Chris Adams
Scott Appleton
Wayne Baisley
Spider Boardman
Alvin Brattli
Bill Broadley
Andries Brouwer
Zach Brown
Dragisa Duric
Martin Edu
Adrian Escott
Douglas Frank
Rick Gorton
Oleg Gusev
Robert Harley
David Hauan
Dave Hill
Richard Holmes
Chatchai Jantaraprim
Olav Kongas
Mika Kortelainen
Edward Lee
Greg Lindahl
Brian Lund
Rob Millner
Francois Morain
Pete Murray
Jon Nathan
Burkhard Neidecker-Lutz
Dennis Opacki
Wieger Opmeer
Miguel Barreiro Paz
Vance Petree
Guillaume Pierre
Martin Radford
Jon Reeves
Tim Rowley
John Sager
Michael Sandfort
Mike Schloss
Alex Selkirk
Al Simons
Aaron Spink
Murray Stokely
Adrian En-Wei Sun
Peter Sward
Greg Thomas
Dimitris Tsapakidis
Jeff Uphoff
Marko Vendelin
Carlos Vidal
Bart-Jan Vrielink
Tom Woodburn
Berndt Josef Wulf
Marinos Yannikos
Paul Young

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 15:33
today. A total of 24249418904337 iterations were performed, finding
36345 "distinguished" points and one collision. The British Telecom
team found 11333 of the points, people from Digital found 7853, people
from INRIA found 4680 and individuals in more than a dozen countries
found 12479. Our source code can be downloaded from:

.-. .-.
/ \ .-. .-. / \
/ \ / \ .-. _ .-. / \ / \
/ \ / \ / \ / \ / \ / \ / \
/ \ / \ / `-' `-' \ / \ / \
\ / `-' `-' \ /
`-' Linux + 500MHz Alpha + 256MB SDRAM = heaven `-'