kleiner Fermats Satz, große

[Henryk Plötz]

Moin,

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

Wobei man Potenzen von 2 natürlich nicht über die Multiplikation sondern über Bitoperationen ausrechnet: pow(2,x) == 1 << x

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.");
                }
        }

Vorsicht! So kann man nicht auf Primzahlen testen. Das Programm würde behaupten dass 561 (die erste Carmichael-Zahl) eine Primzahl ist, obwohl 561 = 3·11·17.