Paper 2026/051

An Improved Randomized 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}$ in our randomized AKS algorithm, which tests $(x-s)^{n^j} \equiv x^{n^j} - s \pmod{x^e-r}$ for $1 \le j \le d$, where $s \in S \subset \mathbb Z_n$ and $d$ denotes the multiplicative order of $n$ modulo $e$. It is based on Bernstein's result but 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 allows us to select a smaller $e$ when $d>1$: the improvement ratio is between $d$ and $d^2$ for $0 < |S| < \sqrt d$, and between $d^2$ and $d^3$ for $|S| \ge \sqrt d$. Because $d \in (\log n)^{O(1)}$, the condition $|S| \ge \sqrt{d}$ can be satisfied deliberately. As a result, we reduce both the theoretical time and space complexities by factors in the range $[d^2, d^3)$ compared with Bernstein's algorithm.