# Running time of the probabilistic primality test

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 .

I can get an algorithm with running time $O\left(k\cdot\ln(n)\cdot M(n)\right)$.

Here $M(n)$ is the complexity of multiplication. If multiplication is left as the regular "school" multiplication, then $M(n) = \ln(n)^2$, and we attain a complexity of $O\left(k\cdot\ln(n)^3\right)$ as you remarked in your post. However, note that for $n$ large enough you may want to implement multiplication via some other method, for example by using the Schönhage and Strassen algorithm to attain a nultiplication complexity of $M(n) = \ln(n)\ln\left(\ln(n)\right)\ln(\ln(\ln(n)))$, thus the total running time becomes only $O\left(k\cdot\ln(n)^2\ln(\ln(n))\ln(\ln(\ln(n)))\right)$

The algorithm is (as you already remark) essentially the same as the Fermat primality test. In the Fermat test, one must compute $a^{n-1}\mod n$, this can be efficiently done using $O(ln(n))$ multiplication operations by using exponentiation via squaring. Since each multiplication operation deal with numbers up to the size of $n$ (since we are working modulo $n$), then each multiplication will take about $O(M(n))$ operations, so it takes $O\left(\ln(n)\cdot M(n)\right)$ operation to compute $a^{n-1}\mod n$ for a single $a$. Since we have to compute $k$ different values of $a$, then the total complexity rises to $O(k\cdot\ln(n)\cdot M(n))$.

This translates almost directly to your proposed algorithm with one caveat - we have to modify the modular exponentiation algorithm to efficiently compute $P_n^{(b)}(a)$ in $O(\ln(n))$ steps. The problem comes from the fact that exponentiating $x-\sqrt{x^2+b}$ is tricky, since it might not be a whole number (and using floating point arithmetic will lead to precision issues for large $n$).

S instead we will represent the numbers of the form $A+B\sqrt{x^2+b}$, where $A,B$ are whole numbers, by the pair $(A, B)$. Notice that we may define addition on the pairs as $(A,B)+(C,D)=(A+C, B+D)$, since $A+B\sqrt{x^2+b}+C+D\sqrt{x^2+b} = (A+C)+(B+D)\sqrt{x^2+b}$.

Similarly, we can define multiplication as $(A,B)\cdot(C,D) = (AC+BD\cdot(x^2+b), AD+BC)$ (you can verify this as an exercise).

Now we can calculate $\left(x\pm \sqrt{x^2+b}\right)^n$ by applying binary exponentiation techniques to the pair $(x,\pm 1)$ in $O(\ln(n))$ multiplications, since each $(A,B)$ pair multiplication requires a constant amount of regular integer multiplications. Afterwards, to gain $P_n^{(b)}(a) \mod n$ all we have to do is sum the two resulting pairs, divide them by $2$ (just divide each component) and we are done.

To speed this up (by a constant factor) one may notice that if $(x, -1)^n = (A,B)$, then $(x, 1)^n = (A, -B)$ (it can be verified by using the binomial expansion, for example), so actually $P_n^{(b)}(a) = \frac{1}{2}\left((A,B)+(A,-B)\right) = (A, 0) = A$, so we only need to carry out the binary exponentiation for $(x, 1)^n$ and take the first component.

Notice also, that $(A, B) \mod n = (A\mod n, B\mod n)$ (well, this is a vit of a stretch, since $\sqrt{x^2+b}$ is kind of ambiguous when we are talking modulo some integer, but one can inductively prove, that the algorithm will return the same result no matter if we take only one modulo at the very end, or compute modulos every step). So in essence this means that we will never have to multiply numbers greater than $n$, so we have multiplication complexity of $M(n)$ as required.

So putting this all together we gain a complexity bound of $O\left(k\cdot\ln(n)\cdot M(n)\right)$ as claimed.

Note: A lot of work presented here is in a very rough state and in no means constiutes a formal proof of complexity, however I tried to outline many of the key concepts one might need to use when looking at this problem and trying to establish complexity.