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

## Prime tests

Let 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 is a prime which does not divide , then mod ).

REMARK This theorem is a special case of a theorem of EULER, which asserts for relatively prime integers and , that mod , where the function gives the number of the relative prime positive integers less equal to .

FERMAT's theorem gives a very effective tool to filter out most of the composite numbers. If e.g. mod , then we know surely, that the number is composite.

> 2^118 mod 119;


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 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);


Unfortunately, the reverse of the theorem does not hold entirely. So if we get mod , then in spite of this is it possible for to be a composite number. Such number is called a pseudoprime (in base ). 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)


Moreover, additional pseudoprimes can be unveiled choosing another base instead of , such as .

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


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 . The Carmichael numbers have at least 3 different prime divisors, so one of their divisors is less than ([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]);


If a number passes through the filters and 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 mod , where ( is odd), and gcd. In this case is a divisor of . If is a prime number, then it divides exactly one of the factors (else it would divide the difference of the factors too), thus mod or mod . However, if is not prime, then we have a good chance, that some divisor of divides , and an another divides . Thus we get for the remainder mod , since does not divide any of the factors. We can continue in the same manner with . Eventually, we are able to filter out most of the pseudoprimes.

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



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


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 s. Let be a prime number, and let mod , where is an integer with . In this case mod . Since is prime, thus or , i.e. for mod we get or . Stepping back similarly we get eventually, that in the remainder sequence mod , mod , mod mod the last value must be , and before it we get . If the number is composite, then this probably does not hold. Thus the algorithm proceeds as follows: we choose a random with . We produce the remainder sequence as above. If this sequence ends with and , then the number is (likely) prime. If and then the number is (surely) not prime. We illustrate the operation of this method to unveil a Carmichael number.

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



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


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 the algorithm gives wrong answer with a probability at most ([8]). So choosing new random 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 . 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-7108Manuscript no.: ANM-000926-A