Paper 2026/051

An improved random AKS-class primality proving algorithm

Abstract

We present an improved AKS condition $\binom {e \cdot |S|+ de - 1}{de - 1} \ge n^{\lceil \sqrt{d e/3} \rceil}$ for the random AKS algorithm, where $|S|$ is the number of congruences to be tested, $e$ the degree of the modulo polynomial $x^e-r$ and $d$ the multiplicative order of $n$ modulo $e$. It is based on Bernstein's result and better than his condition $\binom {e \cdot |S|+ e - 1}{e - 1} > n^{\lceil \sqrt{d^2 e/3} \rceil}$ when $d>1$; this improved condition enables us to choose a smaller $e$: theoretically by a factor $> d$ ($d \in (\log n)^{O(1)}$) and numerically $\ge d^2$ and $< d^3$ for most practical cases; and thus improves time and space complexities.