Sergey Khashin, Department of Mathematics, Ivanovo State University

Counterexamples for Frobenius primality test

The most powerful elementary probabilistic method for primality test is the Frobenius test. Frobenius pseudoprimes are the natural numbers for which this test fails. There are several slightly different definitions of Frobenius pseudoprimes (FPP), which are almost equivalent. We are using the following one.

Definition Frobenius pseudoprime (FPP) is a composite odd integer $n$ such that it is not a perfect square provided $ z^n \equiv \overline{z} \mod n$, where $z=1+\sqrt{c}$ and $c$ is the smallest odd prime number with the Jacobi symbol $J(c/n)=-1$.

Theorem 1(multiple factors). Let $n=p^sq$ is FPP where $p$ is prime and $s>1$. Then ${z^p = \overline{z} \mod p^2}$.

Experiment 1. There are no exist such prime $p<2^{32}$.

Theorem 2. Let $n=pq$ be FPP where $J(c/p)=+1$. Then $z_1^q \equiv z_2$, $z_2^q \equiv z_1 \mod p$, where $z_{1,2} = 1 \pm d \mod p$ and $d^2 = c \mod p$.

Experiment 2. For each $c$ there exists a short list ($<20$) of such primes $p$.

Experiment 3. There exist no FPP less than $2^{60}$.