Inspired by Theorem 5 in this paper I have created the following algorithm:
Let us define polynomials $P_n^{(b)}(x)$ as follows :
$$P_n^{(b)}(x)=\left(\frac{1}{2}\right)\cdot\left(\left(x-\sqrt{x^2+b}\right)^n+\left(x+\sqrt{x^2+b}\right)^n\right)$$
Test in pseudocode :
Inputs: $n$ : a value to test for primality , $n>3$ ; $k$: a parameter that determines the number of times to test for primality
Output: composite if $n$ is composite, otherwise probably prime
Repeat $k$ times :
$\phantom{5}$ Pick $b$ randomly in the range $[-100,100]$
$\phantom{5}$ Pick $a$ randomly in the range $[2 , n − 2]$
$\phantom{5}$ If $P_n^{(b)}(a) \not\equiv a \pmod n$ , then return composite
If composite is never returned: return probably prime
You can run this test here.
Unlike in Fermat primality test Carmichael numbers do not always pass this test. As a matter a fact, I don't know if any of them passes this test.
Question:
What is the probability of an arbitrary composite number passing this test? Is it possible to estimate its value?
EDIT
The Android app that implements this test with $k=3$ can be found on Google Play.
Python script that implements this test can be found here.
This isn't a full solution, but I attempted to analyze the problem by brute force by estimating the number of values of $a$ and $b$ which verify $n$ is composite. One lesson I can find from this: increasing the span of $b$ seems to do little to change this proportion, at least for low values of $n$.
This graph seems to vary quite dramatically. For any $n=2^p$, there are no false positives; on the other extreme, for $n=105$ and $n=231$ I would note that there are an abnormally high proportion of false positives (approximately 17% and 15% respectively for $b\in\{-100,\ldots,100\}$). These numbers specifically tell me little (perhaps another will recognize some importance in them), but the existence of such variance in false positives suggests to me that the probability you wish to estimate varies in more than just the magnitude of $n$.
One very crude way of estimating the likelihood of falsely identifying a composite as prime would be to consider the average of this proportion; under this, we find that this average runs about 0.013 for $n$ up to 300; and shrinks slowly from there to about 0.009 for $n$ between 800 and 1000; if we may safely assume this trend continues, then I would expect the probability of a false positive to be less than $0.009^k$ for large values of $n$, as a very generous upper bound.
My apologies for the crude approach to this problem; I hope that despite this, it proves to yield some insight towards a more complete solution.