kleiner Fermats Satz, große

[Daniel Thoma]

Hallo Andavos,

Mit longs kannst Du sehr viel größere Primzahlen so testen. Du musst nur ein Bisschen geschickter vorgehen.

Statt erst zu Potenzieren, und dann Modulo zu rechnen, kannst Du nach jeder Multiplikation modulo rechnen.
Es gilt: a^n % m = f(a, n, m) wobei:
f(a, 1, m) := a % m;
f(a, n, m) := (f(a, n - 1, m) * a) % m;

Beweis durch Induktion:
Für 1: a % m = f(a, 1, m) = a % m --> OK
Für n + 1; a^(n + 1) % m = (a^n * a) % m = ((a^n div m) * m * a + (a^n % m) * a) % m = ((a^n % m) * a) % m = (f(a, n, m) * a) % m

Damit hat man nun eine Möglichkeit die Zahlen < p^2 zu halten.

Die Potenzen kann man noch mit folgendem Trick schneller ausrechnen (Beispiel):

2 * 2 * 2 * 2 * 2 * 2 * 2 = (2 * 2 * 2) * ((2 * 2 * 2) * 2) = 8 * 8 * 2 = 128

Man verwendet Teilergebnisse also mehrmals.
Daraus kann man nun einen Algorithmus bauen (hier in Java):

public class Prim {

public static void main(String[] argv) {
                long p = Long.parseLong(argv[0]);
                long x = modpow(2, p - 1, p);
                if(x == 1) {
                        System.out.println(p + " ist eine Primzahl.");
                }
                else {
                        System.out.println(p + " ist keine Primzahl.");
                }
        }

public static long modpow(long b, long e, long m) {
                if(e == 1) {
                        return b % m;
                }
                else {
                        long r = modpow(b, e / 2, m);
                        r = (r * r) % m;
                        if(e % 2 == 0) {
                                return r;
                        }
                        else {
                                return (r * b) % m;
                        }
                }
        }
}

Grüße

Daniel