NTP

16. Fermaov test primalnosti

Mala Fermaova teorema:
Ako je p prost broj i a prirodan broj takava da je nzd(a,p) = 1
(tj. brojevi a i p su uzajamno prosti), onda je
a^(p-1) mod p = 1

Primer:
p = 13, a = 3
3^1 = 3
3^2 mod 13 = 3*3 mod 13 = 9
3^3 mod 13 = 9*3 mod 13 = 1
3^4 mod 13 = 1*3 mod 13 = 3
3^5 mod 13 = 3*3 mod 13 = 9
3^6 mod 13 = 9*3 mod 13 = 1
3^7 mod 13 = 1*3 mod 13 = 3
3^8 mod 13 = 3*3 mod 13 = 9
3^9 mod 13 = 9*3 mod 13 = 1
3^10 mod 13 = 1*3 mod 13 = 3
3^11 mod 13 = 3*3 mod 13 = 9
3^12 mod 13 = 9^3 mod 13 = 1
3^12 mod 13 = 3^(3*4) = (3^3 mod 13)^4 mod 13
a = 5
1 5
2 12
3 8
4 1
5
6
7
8
9
10
11
12

Fermaov test se radi na sledeci nacin:
1. Bira se (pseudo)slucajan prirodni broj a (a >= 2, a <= p-2)
2. Ako je nzd(a,p) > 1, onda je p slozen, tj, nije prost (return false)
3. Racunamo b = a^(p-1) mod p
4. ako je b != 1, onda broj p nije prost, u suprotnom (tj. ako je b = 1) vraca se true (return)

boolean FermaovTest(int n) {
  a = Random(2, n-2); // ova funkcija vraca (pseudo)slucjan broj izmedju 2 i n-2
  if (nzd(a,n) != 1) return false;
  b = powMod(a, p-1, p); // ova funkcija racuna a^(p-1) mod p, koristeci brzo
stepenovanje
  if (b != 1) return false; else return true;
}