Java i liczby pierwsze, odsłona druga

Dużo osób trafia na mojego bloga szukając czegoś o liczbach pierwszych i Java'ie.

Pisałem tu już kiedyś o użyciu klasy BigInteger z JDK w celu testowania czy liczba jest pierwsza.
Dziś będzie o prostszym teście, choć o wiele mniej dokładnym ;-)

Kod przedstawia się tak:

public class PrimeTest {
 private static int modExp(int a, int b, int n) {
  int d=1;
  for (int i=31; i>=0; i--) {
   int v = 1<<(i);
   d=(d*d)%n;
   if ((v & b)==v) {
    d=(d*a)%n;
   }
  }
  return d;
 }

 public static boolean test(int a) {
  int v = modExp(2,a-1,a);
  return (v==1);
 }
}

A wszystko opiera się na wykorzystaniu małego twierdzenia Fermata, które mówi, że każda liczba pierwsza p spełnia równanie:

a^p-1≅1 (mod p)

jeżeli tylko a jest liczbą całkowitą i nie jest podzielne przez p.

Okazuje się, że stwierdzenie odwrotne, jest prawie zawsze prawdziwe. Czyli, że prawie zawsze gdy liczba spełnia ten warunek to jest pierwsza :-) [w tym miejscu chciałoby się zakrzyknąć TADAM! ;-)]
Np. dla liczb od 2 do 1000, nasz test wskaże błędnie liczby 341, 561 i 645 [także przy 2 się pomyli, bo powie, że 2 nie jest pierwsze].
Ale dodanie testowania też dla innych a niż 2, zmniejsza szansę wyniku false positive.

 public static boolean test(int i) {
  boolean b = true;
  for (int a=1; a<=((i<5)?i:5)-1; a++) {
   int v = modExp(a,i-1,i);
   if (a!=i) {
    b&=(v==1);
    if (!b) break;
   }
  }
  return b;
 }

Zresztą sama metoda test(int) dla przypadku z testowanie tylko względem 2 może zostać zastąpiona przez taką:

 public static boolean test(int i) {
  return (Math.pow(2, i-1)%i)==1;
 }

Ta z pierwszego listingu bazuje na algorytmie obliczania potęgi modulo, który to algorytm jak i zresztą ten test poznałem dzięki książce "Wprowadzenie do algorytmów" [świetna książka, nie czyta się jej może tak lekko jak Pratchetta czy Dawkinsa, ale jest nieźle napisana].

Teraz pytanie "Po co to?".
Żeby wiedzieć :-)


Podobne posty^beta
Go, a łatwość czytania kodu
Czy to jeszcze dynamic programming? ;-)
Zdradliwa Java i 8 królowych ;-)
Czemu od 30 godzin nie piję Coli - Eksperyment ;-)
Lubię bity, czyli jak dodawać, odejmować, mnożyć i dzielić na bitach ;-)