Underwood's Tests

Most Frobenius tests consider the power of the base $x$. Underwood considers the base $Sx+T$, in particular base $x+2$ and base $x+1$.

The main test for base $x+2$ is to find a minimal $a\ge 0$ such that $a^2-4$ over $n$ has a Jacobi symbol of $-1$ with $\gcd((a+4)(2a+5))$ $=$ $1$ and test $(x+2)^{n+1}$ $\equiv$ $2a+5$ $\pmod{n, x^2-ax+1}$.

Like the other probable prime tests left-to-right binary exponentiation is performed. If $sx+t$ is the intermediate value, the next term is given by $[s,t] \leftarrow [s(as+2t),$ $(t-s)(t+s)]$. This entails two major multiplications with two modular reductions. If there is a $1$ at the end of the left-to-right partial exponent then sundry small calculations need to be performed. This test has been verified for $n<2^{50}$.

A "hybrid" variation is to use base $x+2$ for $a$ equal to $0$ or $1$ and base $x+1$ otherwise,

A test similar to Baillie-PSW can be acheived by considering base $2x$: $(2x)^\frac{n+1}{2}$ $=$ $2$ $\times$ $JacobiSymbol(2(a+2),n)$ $\pmod{n, x^2-ax+1}$ where $a>2$ is minimal such that $JacobiSymbol(a^2-4,n)$ $=$ $-1$.

When testing a list it is more efficient to sieve, factor and run a base 2 fermat probable test first before running one of the above tests. Also, as the calculations require Fast Fourier computations for very large numbers, the aforementioned sundry calculations become significantly time-consuming, thus making the main test slower than a Baillie-PSW test.