Primalilty tests

by iarnab_kundu, Jan 13, 2014, 4:31 PM

There are numerous primality tests that are eminently efficient. One of them is the recent Agrawal–Kayal–Saxena primality test. But our main focus is on one of the most ancient test, a.k.a Pseudoprimality testing.

Algorithm- Take a positive integer $n>1$ . Take another positive integer $a$ . Compute $a^p\pmod{p}$ . If the remnant value is $a\pmod{p}$ we say it's prime. Otherwise not.

Take an integer $n$ . Take $a=2$ . We know that by Fermat's Little Theorem, $a^{p}\equiv a\pmod{p}$ , if $p$ is an odd prime. Is the converse true? Let's check for some values. $n=3,4,5,6,7,8,9$ it's true. So it seems true. Right?
Bazinga! It turns that it fails for $n=341$ .
Let's take another $a$ , let it equal $3$ . Again we see there is a number passing through a loophole.
These numbers like $341$ which contradict the algorithm for $a=2$ are now called as pseudoprime base $-2$ . Similarly there exists numbers pseudoprime base $-a$ .

Now the question arises, are there finitely many of them? Unfortunately there are infinitely many so for any base $-a$ . As a matter of fact if $p$ is a psedoprime base $-a$ then $a^{p-1}\equiv 1\pmod{p}$ .

If we see the pseudoprime tables then we would notice that there are not much intersection in between. So can we check for a large number of bases and if that they turn out to be "prime" for each case then that implies that the number is prime? Again there are Carmichael numbers which are pseudoprimes in any base.
Thus this algorithm is obliterated.

Let's try to improve this one.
Algorithm- Take a positive integer $n>1$ . Take another positive integer $a$ . Compute $a^{p-1}\pmod{p}$ . If the remnant value is not $1\pmod{p}$ we declare that its composite. Otherwise run the loop for all $1<a<p$ . If all these bases say that they are prime. Then it is!

Indeed if its not a prime then there is a factor of it. This factor exponentiated would render it a composite. But this test is a sheer waste of time.

Let's turn our heads towards Miller-Rabin randomized primality test.

Take an odd positive integer $n=2^tu+1>1$ and a base $-a$ .
Definition- The integer $a$ is called "witness" if
$\bullet$ either there exists $t\ge s\ge 1$ such that $a^{2^su}\equiv 1\pmod{n}$ but $a^{2^{s-1}u}\not\equiv -1\pmod{n}$
$\bullet$ or $a^{n-1}\not\equiv 1\pmod{n}$ .

Now the test.
Algorithm- Take an integer $n$ as usual. Take a random number $1\le a\le n-1$ . If $a$ is a witness, terminate the process and print that $n$ is a composite number. Otherwise iterate the loop $s$ times.

It is easy to note that if we get by the test the number is composite then it is surely a composite. But unfortunately this code sometimes says a number is prime but it is not so!
It is claimed that there are atleast $n/2$ integers $a$ such that $a$ is a witness. Hence the probability that the test prints a prime is atmost $2^{-s}$ .
It can be shown by probabilistic arguments that the odds that the tests returns a prime and it indeed is a prime is atleast $\dfrac{1}{1+2^{-s}(\ln n-1)}$ .

Hence iterating the loop $s=7$ times and for any integer $n$ in $64$ -bits, is the test is positive then we may be $99.99999$ % sure that it is indeed a prime. And so we establish an efficient algorithm.
I shall elaborate on the efficacy of the code in a later blog post, and shall prove that the well above $1-2^{-s}$ .

For the C++ implementation of the algorithm. Check this one. http://paste.ubuntu.com/6760800/
(It works for numbers less that $10^9$ )

References- Algorithms by Cormen, Leiserson, Rivest and Stein

This post has been edited 4 times. Last edited by iarnab_kundu, Jan 16, 2014, 7:47 AM

Cracking the Nut Open

Primalilty tests

by iarnab_kundu, Jan 13, 2014, 4:31 PM

0 Comments