CEL + AKS?

[bdodson]

Not sure whether this is the appropriate thread, but there's a new
"version of AKS" just announced on nmbrthry. Major new ingredients,
to say the least, including taking advantage of features of ecpp. They're
routinely proving primality of primes with 4096-bits in five days. A
preprint is at

[CEL08] J.-M. Couveignes, T. Ezome and R. Lercier. Elliptic periods and
primality proving, (2008), arXiv:0810.2853v3

in addition to the nmbrthry post. -bd

(having followed the link about not starting un-necessary new threads ...)

[CRGreathouse]

Jean-Marc Couveignes, Tony Ezome, and Reynald Lercier announced a new variant of the AKS primality-proving algorithm on NMBRTHRY today:

• A practical variant of the AKS primality test on the NMBRTHRY list archive
• Elliptic periods and primality proving on the arXiv

Their method expands on the work of Avanzi & Mihăilescu and Bernstein, keeping the essentially quartic time complexity but improving the practical runtime and memory requirements dramatically. The new version uses elliptic curves extensively.

They even implemented their algorithm with the FFTW and ZEN libraries, giving us real timing information for not-too-small primes!

I have included with their results my extremely nonscientific comparison with Marcel Martin's Primo, an elliptic curve primality-proving algorithm. (I did not test the same primes, use the same OS, same CPU architecture, or the same clock speed; these results are to be taken as an order of magnitude only!)

Bits	ECPP	CEL/AKS		Ratio
1024	13.41s	43320s		3230
2048 	367s	680400s		1854
4096	5857s	14245200s	2432

[philmoore]

Moderator's note: I think this is significant enough to warrant its own thread! Bruce's posting was prior to Charles, so it appears first in this thread, even though Charles Greathouse actually started the thread.

Personal note: Although I found AKS interesting, I had not expected that a practical variant of it would be found so soon! Having proven a 4934 digit number prime using Primo in four weeks, I can appreciate the speed-up that this new development brings.

Added in edit: Oops, just realized 4934 digits is not 4934 bits. I would guess that the new method does not get competitive with ECPP until around 750,000 bits, or so, around 225,000 digits, still too large to be of practical use, but even though the algorithm is not deterministic, bringing a heuristic O(ln^5 N) down to a heuristic O(ln^4 N) is a HUGE step! Please pardon the over-optimistic appraisal!

[bdodson]

Originally Posted by philmoore

... even though Charles Greathouse actually started the thread.

Nice post; I was hoping someone would track down the links. On bits
-vs- decimal digits, Maple reports

> evalf(log[2](10^300));
                                  996.5784285

> evalf(log[10](2^4096));
                                  1233.018862

The largest previous report (as far as I've seen), for record AKS prime
was a Dan Bernstein email of 300-digits (decimal). I don't recall seeing
even one specific 100-digit prime reported in print. By constrast, the new
method is routinely verifying 1000+ digit primes. Not in Franke's 15,000-digit
or 20,000-digit ecpp record range; but perhaps we might hope to see
10,000-digits CEL/AKS, with further continued development? -Bruce

[CRGreathouse]

Good call.

AKS-type primality proof for a 1025-bit integer


Bernstein took 47500s to verify the primality of a 1025-bit number, which is comparable to the time here (though on a slow machine: 800 MHz P3).

[alpertron]

Originally Posted by bdodson

They're
routinely proving primality of primes with 4096-bits in five days.

They were using 32 machines. The NMBRTHRY post indicates that they needed 164 days of CPU time in order to prove primality of the 4096-bit number.

[bdodson]

Originally Posted by alpertron

They were using 32 machines. The NMBRTHRY post indicates that they needed 164 days of CPU time in order to prove primality of the 4096-bit number.

I was mostly hoping that more people would have a look at Lercier's post.
The "five day" entry in the column for bits and row "Calendar time (32 CPUs)"
that I featured is just below the 164 days in the row "CPU time (1 CPU)"
you're noting. I'll grant that proving a number prime with the new(!) method
takes over five months on a single cpu. But a scan through Dan's Math Comp
paper ("quartic time", Jan 2007) doesn't appear to have a single specific
prime that he's applied the method to. I'm very happy to have the reference
to his nmbrthry post with the certificate for 2^1024 + 643 (c. 300-digits,
more-or-less?); but that's 2003, and I still don't know of another specific
calculation with the "first generation" of variations on AKS for a prime
at/above 200-digits. In a comparison of five years with five days, or even
six months (if you prefer), I'd still maintain that the 4096-bit verifications
are "relatively routine".

On the specific/explicit part, the arXiv just includes the nmbrthry post
verbatim; so we haven't yet seen 2-3 primes in print (if that's the standard).
Otherwise, these terms perhaps depend upon one's daily routine. I checked
this morning, 370 x86-64's running snfs, 1000+ pcs running ecm (8pm-8am,
only, xps and core2s), so "5 days, 32cpus" seems to me to fall within routine;
the quadcore cluster would make short work of the verfication (if it would
run under condor ...). -bd

[ewmayer]

Also note that to achieve even the current timings they had to give up the "deterministic" part of AKS, so unless they can recover the determinism or get speeds within at least reasonable sight of ECPP, this remains an exercise of academic interest - "don't try this for proving primality at home".

[bdodson]

Originally Posted by ewmayer

Also note that to achieve even the current timings they had to give up the "deterministic" part of AKS, so unless they can recover the determinism or get speeds within at least reasonable sight of ECPP, this remains an exercise of academic interest - "don't try this for proving primality at home".

The link in Dan's 2003 nmbrthry post goes to the 2007 Math Comp paper,
with a title that includes "essentially quartic random time". Only the initial
Lenstra and Pomerance degree 6 variants are "deterministic". If one wants
deterministic AKS, we're looking for primality of 83, not 3-digits, much less 4.
-bd