Thread: Fast ECPP
View Single Post
Old 2007-06-25, 13:27   #6
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

26·113 Posts

Originally Posted by T.Rex View Post
WHy not ? Good idea. I'd like to spend CPU power to prove the primality of a number of about 12700 digits. Based on the few papers I quickly read about FastECPP, it would take about one year ... I've sent emails to some authors of FastECPP, waiting for answers.
Based on the complexity of APR-CL, it seems it would take about 3.10^10 operations. But I miss details.
So, is there a free version of APR-CL (or APRT-CL) I could download, compile and use ? I googled and found nuts. Reading some pages, it seems some versions can handle a limited number of digits. A parallelized version would be nice ...
So, I would really appreciate your help,
I coded APR-CL (in Fortran no less!) many years ago. (about 20).
It was written in a dialect of Fortran (for an Alliant FX-80) for which
a compiler no longer exists. Furthermore, the code would be slow by
current standards, even if run on modern computers because it does not
incorporate many improvements that have been found since then. (by
Bosma, Mihailescu, et. al.). Indeed, the code is backed up on an
EXABYTE tape (this was before CD's !!) and I do not have access to an
EXABYTE reader [does anyone anymore?] Finally, quite a bit of work
would be needed to accomodate 12K digits. The code was written to
handle < 1K digits.

Preda has a public version that he has made available in the past. You
might try asking him for his code. Henri Cohen might be another source.

You could also ask Francois for ECPP code.

I thought you wanted help with the theory......I don't have any code to give

Another option: assume GRH and apply Bach's Theorem to Miller-Rabin.
This would yield an embarassingly parallel algorithm that requires no datacomm between processors..........
R.D. Silverman is offline   Reply With Quote