sobota, października 17, 2009

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:

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

Brak komentarzy:

Prześlij komentarz