Robert J. Harley,
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
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:
Miguel Barreiro Paz
Dr. Sven Dietrich
Dr. Hiankiat Lee
Adrian En-Wei Sun
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
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
Our source code can be downloaded from:
We invite anyone interested in working on the next calculation to
point their Web browsers at:
.-. Robert.Harley@inria.fr .-.
/ \ .-. .-. / \
/ \ / \ .-. _ .-. / \ / \
/ \ / \ / \ / \ / \ / \ / \
/ \ / \ / `-' `-' \ / \ / \
\ / `-' `-' \ /
`-' Linux + 500MHz Alpha + 256MB SDRAM = heaven `-'