An improved random AKS-class primality proving algorithm

본문 미리보기

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 allow