International Association
for Cryptologic Research

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 average asymptotic 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 running time of the algorithm. From this analysis we also present a variant of AKS whose running time is $O(\log^{4+\epsilon} n)$.