Paper 2016/362

An Empirical Study towards Refining the AKS Primality Testing Algorithm

Lalitha Kiran Nemana and V. Ch. Venkaiah

Abstract

The AKS (Agrawal-Kayal-Saxena) algorithm is the first ever deterministic polynomial-time primality-proving algorithm whose asymptotic run time complexity is $O(\log^{12+\epsilon} n)$, where $\epsilon > 0$. Despite this theoretical breakthrough, the algorithm serves no practical use in conventional cryptologic applications, as the existing probabilistic primality tests like ECPP in conjunction with conditional usage of sub-exponential time deterministic tests are found to have better practical running time. Later, the authors of AKS test improved the algorithm so that it runs in $O(\log^{10.5+\epsilon} n)$ time. A variant of AKS test was demonstrated by Carl Pomerance and H. W. Lenstra, which runs in almost half the number of operations required in AKS. This algorithm also suffers impracticality. Attempts were made to efficiently implement AKS algorithm, but in contrast with the slightest improvements in performance which target specific machine architectures, the limitations of the algorithm are found highlighted. In this paper we present our analysis and observations on AKS algorithm based on the empirical results and statistics of certain parameters which control the asymptotic running time of the algorithm. From this analysis we refine AKS so that it runs in $O(\log^{4+\epsilon} n)$ time.

Note: ~ character not recognized in the abstract.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
primality testingAKS algorithm
Contact author(s)
nemana lalithakiran @ gmail com
History
2019-03-22: last of 4 revisions
2016-04-11: received
See all versions
Short URL
https://ia.cr/2016/362
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/362,
      author = {Lalitha Kiran Nemana and V.  Ch.  Venkaiah},
      title = {An Empirical Study towards Refining the AKS Primality Testing Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2016/362},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/362}},
      url = {https://eprint.iacr.org/2016/362}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.