Welcome to our community

Be a part of something great, join today!

Commentary for "Primality Tests"

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
re: Commentary for "Primality Tests"

[JUSTIFY]Of course, the last two algorithms presented by Mathbalarka require the knowledge of factors of $n - 1$, which puts them in the "special purpose" category. I messed around with Pocklington's myself a few months ago, quite an interesting algorithm, and I didn't know group theory at the time I tried to find out how it worked (fun fun fun).

Of course the "gold standard" in terms of speed/accuracy is Miller-Rabin, for general-purpose primality testing (knowledge of the factorization of $n - 1$ allows one to certify primality rather easily, as noted by Mathbalarka). The AKS algorithm makes it possible to do so even without such knowledge, and is actually getting quite practical with the recent algorithmic improvements uncovered, but is still pretty unpopular.[/JUSTIFY]
 

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573
re: Commentary for "Primality Tests"

First things first, I want to thank MarkFL for creating a commentary thread for the topic I made.

Now, for Bacterius :

Yes, the last two algorithms are for special purposes but still are useful if Pocklington fails because of the bounds on the factors issues. Miller-Rabin isn't very handy for manual calculations because of the large congruences. And I doubt whether AKS can be done manually. However, currently the best algorithm for general-purpose primality test are ECPP and fastECPP. I even considered about adding the algorithms in my post since there are a few cases where it can be manually used!

Balarka
.