Sharpening “Primes is in P” for a large family of numbers

Abstract:

We present algorithms that are deterministic primality tests for a large family of integers, namely, integers $n \equiv 1\pmod 4$ for which an integer $a$ is given such that the Jacobi symbol $(\frac {a}{n})= -1$, and integers $n \equiv {-1} \pmod 4$ for which an integer $a$ is given such that $(\frac {a}{n})= (\frac {1-a}{n})=-1$. The algorithms we present run in $2^{-\min (k,[2 \log \log n])} \tilde {O}((\log n)^6)$ time, where $k = \nu _2(n-1)$ is the exact power of $2$ dividing $n-1$ when $n \equiv 1\pmod 4$ and $k = \nu _2(n+1)$ if $n \equiv \ -1\pmod 4$. The complexity of our algorithms improves up to $\tilde {O}((\log n)^4)$ when $k \geq [2 \log \log n]$. We also give tests for a more general family of numbers and study their complexity.