Paper 2024/121
An acceleration of the AKS prime identification algorithm
, Barcombe ServicesAbstract
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 made, in the last stage of AKS, is to check a modular equation not for a long sequence of values but for a single one. Another change is to reduce, arbitrarily, the size of the parameter $r$ giving the degree of the polynomial used for the last stage.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- AKS primality testingsingle–valueCarmichael numbersbinomial theoremaccelerationalgorithm
- Contact author(s)
- zen323167 @ zen co uk
- History
- 2024-01-29: approved
- 2024-01-27: received
- See all versions
- Short URL
- https://ia.cr/2024/121
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2024/121,
author = {Stephen Meredith Williams},
title = {An acceleration of the {AKS} prime identification algorithm},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/121},
year = {2024},
url = {https://eprint.iacr.org/2024/121}
}
