1 Suppose we have the following probable prime test for an integer $n$:
Choose any integers $a$ and $b$ such that
Jacobi$(a,n)=-1$ and $\gcd(b,n)=1$
[2] If $(x+b)^n = -x+b \mod (n,x^2-a)$, then $n$ is a probable prime, otherwise, $n$ is composite.
If $n$ is composite, the congruence cannot hold for too many $b$'s:
From a field theory perspective, $x+b$ is an element in the field $F(n^2)[x]/[x^2-a]$ which has order $n^2-1$ when $n$ is prime. It can be seen that
[3] $(x+b)^{n^2-1} = 1 \mod (n,x^2-a)$
from which we have analogues of Carmichael numbers (order 2 Carmichael numbers precisely).
So $(x+b)^n = -x+b \mod (n,x^2-a)$ implies that $(x+b)^{n^2-1} = 1 \mod (n,x^2-a)$, but the converse is not true:
$(x+3)^{2047^2-1} = 1 \mod (2047,x^2+1)$
$(x+3)^{2047} ≠ -x+3 \mod (2047,x^2+1)$
In a nutshell, this proves that there are no analogues of Carmichael numbers for this test. It also shows that the set of binomials for which [2] is true is a proper subset of the binomials for which [3] is true. Therefore I ask:
- What is the maximum probability of error if the test is done $k$ different times using different $x+b$ binomials? In other words, for any composite number $n$, what are the maximum number of binomials $x+b$ that $n$ will pass the test (for any $a$ with Jacobi$(a,n)=-1$)?
(This question is analogous to how the Miller-Rabin declares a composite number prime with probability no more than $1/4^k$ for $k$ different rounds of the test)
I have also generated a list of "pseudoprimes" to this test.