4 The Algorithm

Input: integer n > 1

 1. if (n is of the form a^b, b>1) output COMPOSITE; // n ist das Ergebnis einer Exponierung
 2. r = 2;
 3. while(r<n) {
 4.  if (gcd(n,r) <>(nicht gleich) 1) output COMPOSITE; // gcd = größter gemeinsamer Teiler
 5.  if (r is prime)
 6.    let q be the largest prime factor of r
 7.    if (q >= (4 Sqrt(r) log n)) and (n((r-1)/q) <>(nicht deckungsgleich(kongruent)) 1(mod r))
 8.      break;
 9.  r = r + 1;
10. }
11. for a = 1 to (2 Sqrt(r) log n)
12. if ( ((x-a)^n) <>(nicht deckungsgleich(kongruent)) (((x^n)-a)(mod (x^r)-1, n)) ) output COMPOSITE;
13. output PRIME;

Theorem 4.1. The algorithm above returns PRIME if and only if n is prime.