Viele kryptographische Algorithmen benötigen große Primzahlen, zum Beispiel das RSA-Verfahren, oder das ElGamal-Verfahren. Auch die meisten kryptographischen Protokolle wie der Schlüsseltausch nach Diffie-Hellman oder nach Hughes oder Shamirs No-Key-Algorithmus brauchen große Primzahlen, um sicher zu sein.
Die große Bedeutung von Primzahlen in der Kryptographie liegt an der Tatsache, daß es schwierig und zeitaufwendig ist herauszufinden, ob eine Zahl eine Primzahl ist, d.h. ob es andere Zahlen außer 1 gibt, und die Primfaktoren einer Zahl herauszufinden.
Sind zum Beispiel p und q zwei große Primzahlen und werden sie
multipliziert
(
Das Problem besteht nun darin, schnell viele große Primzahlen zu ermitteln, weil bei jeder Transaktion mit einem kryptographischen Protokoll neue Primzahlen gebraucht werden.
Es gibt eine einzige sichere Methode, Primzahlen zu erkennen, nämlich entsprechend der Definition sicherzustellen, daß die Zahl durch keine andere Zahl als 1 teilbar ist. Dazu muß man die vermutete Primzahl durch jede ganze Zahl zwischen 1 und ihrer Wurzel teilen. Wenn sich bei nur einer von diesen Zahlen bei der Division kein Rest ergibt, dann ist die Zahl keine Primzahl.
Leider ist die Ausführungzeit dieses Algorithmus' exponentiell zur Stellenzahl der eingegebenen Zahl.
Es gibt drei Arten der Ausführungszeiten von Algorithmen: Ausführungszeit proportional, polynomial und exponentiell zu der Größe des Eingabedatums.
Ist n die Größe der Eingabedaten und k eine Konstante, so ist die
Ausführungszeit bei Algorithmen mit proportionalem Verhalten gleich k*n,
bei polynomialem Verhalten
Hier als Beispiel eine kleine Tabelle mit den Ausführungszeiten von drei Algorithmen, jeweils einer mit proportionalem, polynomialem und exponentiellem Zeitverhalten:
Die Algorithmen benötigen
| Größe | |||
|---|---|---|---|
| astronomisch |
Dieses Beispiel zeigt, daß Algorithmen mit exponentieller Ausführungszeit außer für sehr kleine Werte praktisch undurchführbar sind. Da wir mit großen Primzahlen rechnen wollen, scheidet dieser direkte Algorithmus also aus.
Beispiel: prim.c
#include <stdio.h>;
#include <math.h>;
/* Funktion prim teilt die übergebene Zahl durch jede ganze Zahl von 2
bis zu der Wurzel der eingegebenen Zahl. Ist der Rest irgendwann 0, so wird 0
zurückgegeben, sonst 1 */
int prim(long p)
{
long teiler=2,rest;
do
{
rest=p%teiler;
if (rest==0)
return (0);
teiler++;
} while (teiler<sqrt(p));
return (1);
}
void main(void)
{
long zahl;
printf("\nGeben Sie eine Zahl ein !\n");
scanf("%ld",& zahl);
if (prim(zahl))
printf("\n%ld ist eine Primzahl\n",zahl);
else
printf("\n%ld ist keine Primzahl\n",zahl);
}
Die einzige realistische Möglichkeit, Zahlen auf Primzahleigenschaften zu testen, sind probabilistische Primzahltests. Bei probabilistischen Tests ist das Ergebnis mit einer bestimmten, bekannten Wahrscheinlichkeit richtig.
Es gibt 3 geläufige probabilistische Primzahltests:
Der Test wurde von Robert Solovay und Volker Strassen entwickelt. Ihr Algorithmus benutzt das Jacobi-Symbol, um zu testen, ob eine Zahl prim ist.
Dieser Test wurde unabhängig von Lehmann entwickelt. Er überprüft mittels modularem Potenzieren, ob eine Zahl prim ist.
Der Algorithmus, der am häufigsten zum Einsatz kommt, weil er so einfach ist, wurde von Michael Rabin entwickelt und geht zum Teil auf Ideen von Gary Miller zurück.