Can you calculate the running time of the algorithm given below ?
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 .
GUI application that implements this algorithm can be found here .
My thoughts . Since this algorithm is similar to the Fermat primality test its running time should be somewhere around $O(k \times \log^3 n)$ where $k$ is the number of times we test a random values of $a$ and $b$ , and $n$ is the value we want to test for primality .