Math Is Fun Forum

danaj

Member

Registered: 2014-03-03

Posts: 29

AKS performance

A year ago, bobbym wrote:

They are right about AKS, it takes about an hour to prove the primality of a 1000 digit number on an old desktop.

Can you point me to the software you're using?  This is much faster than any AKS implementation I am aware of.  It's millions of times faster than stated performance numbers in papers about AKS implementations, e.g.

  - Crandall and Papadopoulos (2003) "A 30-decimal-digit prime this took, [...], about a day to be resolved."

  - Rotella (2005), "An Efficient Implementation of [AKS]" takes a minute for 4 digit numbers, and ends with "[...]the AKS algorithm, while it is elegant and relatively simple, should be viewed as an algorithmic curiosity rather than an algorithm to be used for actual primality proving."

  - Salembier and Southerington (2006) show a time of 30 minutes for a 15 digit number.

  - Brent (2010) estimates 840 years for a 308 digit prime using a version with some improvements.

My code/machine is running about 200 times faster than Brent's numbers, and I come up with en estimate of about 4200 years for a 1000 digit number.  APR-CL and ECPP are about 2-5 minutes (single threaded) for 1k digits on the same computer.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: AKS performance

I think this is the relevant link.

http://www.mathisfunforum.com/viewtopic … 60#p303360

Looks like an obvious mistake, the guy I was quoting wrote "up to 1000 digits" when he obviously meant "up to 1000." Big difference. I had an implementation of it but did not run it so I did not catch that error. I would say although it is a theoretical breakthrough it is far too slow for any practical use, you are correct.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

danaj

Member

Registered: 2014-03-03

Posts: 29

Re: AKS performance

Sorry for not including the link.  It was here as well:  http://www.mathisfunforum.com/viewtopic … 75#p273775.

Re implementation, Darn -- I was hoping to find something new!  Thanks for looking.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: AKS performance

Hi;

Sorry for the confusion.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.