Paper 2024/121 Original: eprint.iacr.org/2024/121 ↗
An acceleration of the AKS prime identification algorithm
Abstract
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.
- History
- 2024-01-27: last updated
- 2024-01-27: published
- Short URL
- https://ia.cr/2024/121
- License
- https://creativecommons.org/licenses/by-nc/4.0/
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}
}