Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**danaj****Member**- Registered: 2014-03-03
- Posts: 29

A year ago, bobbym wrote:

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.

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,743

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.**

**Online**

**danaj****Member**- Registered: 2014-03-03
- Posts: 29

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.

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,743

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.**

**Online**

Pages: **1**