An acceleration of the AKS prime identification algorithm

ePrint Report: An acceleration of the AKS prime identification algorithm

Stephen Meredith Williams

In its standard form, the AKS prime identification algorithm is deterministic and polynomial time but too slow to be of practical use. By dropping its deterministic attribute, it can be accelerated to an extent that it is practically useful, though still much slower than the widely used Miller-Rabin-Selfridge-Monier (MRSM) algorithm based on the Fermat Little Theorem or the Solovay-Strassen algorithm based on the Euler Criterion. The change …

algorithm can eprint report identification prime report slow standard williams