Elliptic Curve Discrete Logarithms


Web sites:

Europe:
http://pauillac.inria.fr/~harley/ecdl3/
United States mirror (with some lag):
ftp://ftp.mac-guru.com/pub/ecdl3/


Latest updates:

(click reload or you might not see them)

Feb. 7th:
Success at 16:21! We were a bit lucky in that we had done 71% as much work as expected. The submission to Certicom is here.

I'd like to take this opportunity to thank everyone who participated. We've set a record for the hardest ECDL problem solved so far!

If you would like to run the next problem, you can head over to this directory.

Feb. 5th:
We're roughly half done!

So far the highest rate is 241 K iters/sec on 600 MHz workstations using 100% C with one asm macro for 'umulh', compiled with a recent version of Digital's cc and "-O5 -tune ev56 -inline all".

Using gcc on the default code (with f2Mul.s) gets up to 205 K.

The 32-bit client tops out at 55 K iters/sec on 233 MHz StrongARM Network Computers running NetBSD using these ASM functions: f2Mul.arm.s, quotient.arm.s.

Using gcc on the default ecdl32bit.c code, the max is 38 K on a 300 MHz Pentium II PC running Linux, followed by 34 K on some kind of Sparc running SunOS, followed by 30 K on the NCs and on a 233 MHz Pentium II. Then there are a bunch of x86 machines, Sparcs, an SGI MIPS running Irix, a HP PA running NextStep and last of all are two 8 MHz ARMs with RISC OS doing 1350 iters/sec...

Jan. 22nd:
Made plots of our progress as an X bitmap (193K or 3K gzipped) or a postscript file (6K or 1K gzipped).

Jan. 16th:
For ECC2-89, we're looking for people running Alphas OR Linux, not necessarily Alpha Linux =:-)

There's a new 32-bit client:
ecdl32bit.c (27K) or ecdl32bit.c.gz (8K gzipped).

The 64-bit client for Alphas has some cosmetic changes but you don't need to upgrade:
ecdl2-89.c (24K) and f2Mul.s (4K)
or:
ecdl2-89.c.gz (8K gzipped) and f2Mul.s.gz (1K gzipped).

Jan. 12th:
Put up a list of our names and some stats counting distinguished points:
counter of points so far,
daily.rate since the start,
hourly.rate for the last 24 hours.

We need about 25000 points! This is slightly less than for ECCp-89 but the iterations are about twice as difficult to compute.

Put up a description of what our pseudo-random iteration is, of which points are considered distinguished, and of the format for reporting them. Our intention is that with this information, others can write client programs and work with us.

Did initial testing.


Calling all Alpha users and Linux users!

Roar! We've got some awesome machines and are capable of solving big problems if a large enough percentage of us are mobilised.

You may be aware that the first THREE problems in the Certicom ECC challenge have been broken by a team of us using Alphas running Linux, Digital Unix, VMS and NetBSD.

You can read about the contest at:

http://www.certicom.com/chal/contents.htm

and our submissions for ECCp-79, ECC2-79 and ECCp-89.

Now we're moving on to ECC2-89 which will require about 1500 days CPU time at 500Mhz. We're hoping to keep the elapsed time down to a few weeks...

So why don't you grab the source code, compile it, and leave it running in the background?

See you soon,
-- Rob.

PS: Constructive comments on the code are very welcome.


How to contribute on 32-bit Linux:

* Get your hands on a 32-bit Linux machine.

* Download ecdl32bit.c (or ecdl32bit.c.gz).

* Decompress if you got the gzipped version:
gunzip ecdl32bit.c.gz

* Compile with something like:
gcc -O4 ecdl32bit.c -o ecdl -DFROM=me@here

replacing "me@here" with your email address (unless you prefer to remain anonymous) and appending one of the following flags:

If your machine is permanently connected to the Net:
-DMAIL_TO=ecdl@pauillac.inria.fr

If it is connected but email to INRIA bounces, try this instead:
-DMAIL_TO=robert@vlsi.cs.caltech.edu

If it is not connected, or email won't get through, use batch mode:
-DBATCH

In batch mode, you should send the output "by hand" via email to one of the addresses, ideally from a machine with ptr and mx DNS records.

* Run:
unlimit cputime
nohup nice ./ecdl > log &

That's it!

NB: You can also use "-DNO_ASM". On Sparc v8 and on i686 it is slower. On Sparc v7 it is faster. On others I don't know! You can check the speed by compiling with "-DTEST" for TEST mode instead of MAIL_TO or BATCH modes. Then it quickly produces some (useless) output along with info on iterations per second. This also allows you to compare compilers, optimisation flags etc.


How to contribute on Alpha:

* Get your hands on an Alpha running Linux, Digital Unix or NetBSD.

* Download ecdl2-89.c and f2Mul.s (or ecdl2-89.c.gz and f2Mul.s.gz).

* Decompress them if you got the gzipped ones:
gunzip ecdl2-89.c.gz gunzip f2Mul.s.gz

* Compile with something like:
gcc -O4 ecdl2-89.c f2Mul.s -o ecdl -DFROM=me@here
or:
cc -O5 -tune host -std1 ecdl2-89.c f2Mul.s -o ecdl -DFROM=me@here

replacing "me@here" with your email address (unless you prefer to remain anonymous) and appending one of the following flags:

If your machine is permanently connected to the Net:
-DMAIL_TO=ecdl@pauillac.inria.fr

If it is connected but email to INRIA bounces, try this instead:
-DMAIL_TO=robert@vlsi.cs.caltech.edu

If it is not connected, or email won't get through, use batch mode:
-DBATCH

In batch mode, you should send the output "by hand" via email to one of the addresses, ideally from a machine with ptr and mx DNS records.

* Run:
unlimit cputime
nohup nice ./ecdl > log &

That's it!

NB: if you compile on Digital Unix with -non_shared and run on Linux then use batch mode, since otherwise the compiled program will look for /sbin/sh whereas Linux has /bin/sh instead.

NB: You can do without the "f2Mul.s" file if you use "-DNO_ASM" but it's usually a bit slower. You can check the speed by compiling with "-DTEST" for TEST mode instead of MAIL_TO or BATCH modes. Then it quickly produces some (useless) output along with info on iterations per second. This also allows you to compare compilers, optimisation flags etc.


Note about batch mode

Both the MAIL_TO and BATCH modes output two lines like this:

ECC2-89 s 04d2359ed7e56f1b739f597 [...etc...] v 0aa8ccf269234fc902a2a69 RobsECDL2-89 102 me@here ;
Total iterations = 5505855375 at 170882/sec

to stdout (i.e., the log file) every few hours. The MAIL_TO mode also does popen("/usr/lib/sendmail ...") to report the line back to base.

In batch mode, you have to do a bit of work transferring the lines manually. That could be by dialling in, or by carrying a floppy disc over to a Net-connected machine or whatever.

You should send the output once per day or every couple of days, by email to ecdl@nospam.pauillac.inria.fr, from a machine with ptr and mx DNS records. If that bounces use robert@nospam.vlsi.cs.caltech.edu instead. Note that the mail is processed automatically. To contact a human (me, actually :) use Robert.Harley@nospam.inria.fr. Remove the "nospam." of course!

It can't hurt to do this even in MAIL_TO mode, or to send things twice. In doubt, err on the safe side!

Merci beaucoup,
Rob.


Further notes:

* The code uses CPU time but almost no other resources, so if you run it 'nice' you'll hardly notice it except when shows up in 'ps'.

* If you run into any problems, please let me know so we can fix them. It's quite possible that I've done something stupid and if you don't tell me I'll never find out!

* If the MAIL_TO mode fails to open a pipe to sendmail, it outputs "Warning: couldn't pipe to sendmail, send by hand!" to the log file. If closing the pipe returns status other than EX_OK, it outputs "Warning: sendmail returned status xxx". If these happen a lot, you should switch to batch mode.

* The TEST mode outputs test results quickly so you can see the iterations per second. Also, it sets the "random seed" to a fixed value so if you optimise the code, you can check that you get the correct output:

>gcc -O4 ecdl2-89.c f2Mul.s -o ecdl -DFROM=me@here -DTEST
>./ecdl
RobsECDL, 64-bit version, TEST mode.
From: me@here.
Computing iterations...
TEST2-89 s 000000000000000499602d2 i 0000000101fe x 0ad898f000007cec16e96c9 y 0ff208d57ef7126cdd6a691 z 1 u 088492a27689736097dfb19 v 0838098817eda6b5349e462 RobsECDL2-89 102 me@here ;
Total iterations = 66046 at 170786/sec
[...etc...]

The long hex numbers in the line starting "TEST2-89" should be the same as the ones given here. If you find a way of getting 10% speedup or more please let us know!