is there any deterministic versions of fermat test except this one?

Question

fermat test says :

if $a^{N-1} \equiv 1 \pmod N$, then N is probably prime number, but according to pocklington primality test if:

$3^{N-1} \equiv 1 \pmod N $, then N is proven prime, where $N=2p+1$, and p is prime, proof :

if $N=2p+1$ then gcd$(3^{\frac{N-1}{p}} -1,N)=1$, but $3^{N-1} \equiv 1 \pmod N $, then $N$ is prime by pocklington primality test.

but my question is, is there any deterministic versions of fermat test except this one ?

Answer 1

Comment on your question/proof, $p$ must be prime, not just probable prime for the test to work!

Are there similar tests?

The Proth Test works for numbers $n=h2^k+1$ where $h < 2^k$. Find an integer $(a | n)=-1$ (Jacobi symbol), and $n$ is prime if and only if:

$a^{(n-1)/2}=-1\pmod n$

There is a similar test if $n=hq^k+1$ where $h < q^k$ and $q$ is prime:

$a^{(n-1)}=1\pmod n$

$\gcd(a^{(n-1)/q}-1,n)=1$

Answer 2

I wrote a short note, Industrial Grade Primes with a Money-Back Guarantee (Crux Mathematicorum 34/3 (2008): 165-169), in which I show that if $p$ and $q$ are odd primes such that $(p-2)/2 < q < 2(p+1)$, then $n = 2pq + 1$ is prime if and only if Fermat's Little Theorem (for $n$) holds.

As I comment in that paper, this result is not practical for generating primes because you need 2 primes to generate one new one, but I have never seen a similar theorem that exhibits a class of integers that is provably prime if and only if Fermat's Little Theorem holds.