Sharpening ``Primes is in P'' for a large family of numbers

We present algorithms that are deterministic primality tests for a large family of integers, namely, integers $n \equiv 1\pmod4$ 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\pmod4$. 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.