HEJ, HU ISSN 1418-7108 Manuscript no.: ANM-000926-A

Prime tests

Let $n$ be an odd number after the separation of the small factors. First we have to decide, if this number is prime or not.

A test based on Fermat's little theorem Already FERMAT has proved the following very important theorem:

THEOREM 7. FERMAT 's little theorem If $p$ is a prime which does not divide $a$, then $a^{p-1} \equiv 1 ($mod $p$).

REMARK This theorem is a special case of a theorem of EULER, which asserts for relatively prime integers $a$ and $m$, that $a^{\phi(m)} \equiv 1 ($mod $p)$, where the function $\phi(n)$ gives the number of the relative prime positive integers less equal to $n$.

FERMAT's theorem gives a very effective tool to filter out most of the composite numbers. If e.g. $2^{n-1} \equiv \hspace{-0.9em}/\hspace{0.4em}1 ($mod $n)$, then we know surely, that the number $n$ is composite.

  > 2^118 mod 119;

$$30$$

Though the computing of these powers seems to be difficult, there are very efficient and fast algorithms for this ([1], [8]). In Maple we can use the more efficient modp and power functions instead of the traditional power operator. Thus, we can prove immediately, that the $5$th Fermat number is not prime.

  > 3^(2^32) mod (2^32+1);
  Error, integer too large in context
  > modp(power(3,2^32),2^32+1);

$$3029026160$$

Unfortunately, the reverse of the theorem does not hold entirely. So if we get $2^{n-1} \equiv 1 ($mod $n)$, then in spite of this is it possible for $n$ to be a composite number. Such number $n$ is called a pseudoprime (in base $2$). The pseudoprimes are fairly rare, analysing the chance of their occurence compared to the primes we get at most a few per thousand.

  > pseudo:=proc(n)
  > local i,s;
  >   s:=NULL;
  >   for i from 3 by 2 to n do
  >     if not(isprime(i)) and (2^(i-1) mod i)=1 then s:=s,i
  >     fi
  >   od;
  >   RETURN(s)
  > end:

  > s1:=pseudo(3001)

$$s1 := 341, \,561, \,645, \,1105, \,1387, \,1729, \,1905, \,2047, \,2465 , \,2701, \,2821$$

Moreover, additional pseudoprimes can be unveiled choosing another base instead of $2$, such as $3, 5, 7, \dots$.

  > 3^1386 mod 1387, 1387=ifactor(1387);

$$875, \,1387=(\,{\rm }19)\,(\,{\rm }73)$$

There are however such extreme numbers (called Carmichael numbers), which are pseudoprimes in all bases, which are relative prime to all of their divisors. These numbers are very rare, the chance of choosing such a (not very small) number is less than approximately one to a million. The first such number is $561$. The Carmichael numbers have at least 3 different prime divisors, so one of their divisors is less than $\sqrt[3]{n}$ ([8]). We can search the Carmichael numbers with the following small program, the input parameter of which is a sequence of pseudoprimes.

  > carmic:=proc(s)
  > local s2,i,n,j,carm;
  >   s2:=NULL;
  >   for i from 1 to nops([s]) do
  >     carm:=true: n:=trunc(sqrt(s[i])):
  >     for j from 3 by 2 to n do
  >       if modp(power(j,n-1),n)<>1 and (n mod j)>0 then
  >       carm:=false fi
  >     od;
  >     if carm then s2:=s2,s[i] fi
  >   od;
  >   RETURN(s2)
  > end;

  > carmic([s1]);

$$561, \,1387, \,1729, \,1905, \,2821$$

If a number $n$ passes through the filters $2, 3, 5$ and $7$ then it is recommended to stop this method. There are some other methods to unveil such composite numbers.

A strong pseudoprime test Let us assume, that $a^{n-1}$ mod $n = 1$, where $n = 2 i -1$ ($n$ is odd), and gcd$(a,n) = 1$. In this case $n$ is a divisor of $a^{2i}-1 = (a^i -1) \cdot (a^i + 1)$. If $n$ is a prime number, then it divides exactly one of the factors (else it would divide the difference of the factors too), thus $a^i$ mod $n = 1$ or $a^i$ mod $n = -1$. However, if $n$ is not prime, then we have a good chance, that some divisor of $n$ divides $a^i -1$, and an another divides $a^i + 1$. Thus we get for the remainder $a^i$ mod $n \ne \vert 1\vert$, since $n$ does not divide any of the factors. We can continue in the same manner with $i = 2 j$. Eventually, we are able to filter out most of the pseudoprimes.

  > n:=1387:
  > 2^`1386` - 1 = (2^`693`-1)*(2^`693`+1);

$$2^{{\it 1386}} - 1=(2^{{\it 693}} - 1)\,(2^{{\it 693}} + 1)$$

  > modp(power(2,693),n);

$$512$$

The Miller-Rabin test The following random method is very likely to be the best tool for primality testing. It was composed and analysed by G. L. MILLER and M. O. RABIN in the late $70$s. Let $n = 1 + 2^k j$ be a prime number, and let $x^j$ mod $n \ne 1$, where $x$ is an integer with $1 < x < n$. In this case $x^{2^k j}$ mod $n = 1$. Since $n$ is prime, thus $n \vert (x^{2^{k-1} j} -1)$ or $n \vert (x^{2^{k-1} j} +1)$, i.e. for $x^{2^{k-1} j}$ mod $n$ we get $1$ or $-1$. Stepping back similarly we get eventually, that in the remainder sequence $r_1 = x^j$ mod $n$, $r_2 = x^{2j}$ mod $n$, $r_3 = x^{4j}$ mod $n, \dots, r_i = x^{2^k j}$ mod $n$ the last value must be $1$, and before it we get $n-1$. If the number $n$ is composite, then this probably does not hold. Thus the algorithm proceeds as follows: we choose a random $x$ with $1 < x < n$. We produce the remainder sequence as above. If this sequence ends with $r_{i-1} = n-1$ and $r_i = 1$, then the number is (likely) prime. If $r_i = 1$ and $r_{i-1} \ne n-1$ then the number is (surely) not prime. We illustrate the operation of this method to unveil a Carmichael number.

  > n:=1729:
  > ifactor(n-1);

$$(\,{\rm }2)^{6}\,(\,{\rm }3)^{3}$$

  > j:=3^3:
  > seq(2^(2^i*j) mod n,i=0..6);

$$645, \,1065, \,1, \,1, \,1, \,1, \,1$$

If the algorithm says, that a number is not prime, then this is surely true, and if the answer is prime, then this is not yet certain. M. O. RABIN has proved, that for arbitrary $n$ the algorithm gives wrong answer with a probability at most $1/4$ ([8]). So choosing new random $x$ bases, after e.g. 20 executions, the probability, that the answer is still prime and the number is in spite of this composite, is less than $(1/4)^{20}$. Thus, in practice we can say, that this answer is correct (the exact proof of the prime property is discussed in a subsequent subsection). The significance of this method is, that we get a reliable answer in relatively short time for very large numbers (containing several hundred digits), too. The isprime function in Maple uses this method too ([3]), for such numbers, which seem to be primes with methods described earlier.

HEJ, HU ISSN 1418-7108 Manuscript no.: ANM-000926-A