Die DSA-Primzahlen haben folgende Spezialeigenschaft, die wieder aus dem Standard FIPS-186-4 hervorgeht.
Aus den möglichen Parameterwahlen wird für die meisten Fälle das Paar L = 2048, N = 256 sinnvoll sein. D.h. Primzahl p mit 2048 Bits und Primzahl q mit 256 Bits, wobei q den Wert p-1 teilt.
Als Gleichung
p = q*t + 1
für t=(p-1)/q.
Für Ihre Implementierung können Sie eine Verbesserung des Fermat-Tests nehmen, die nicht ganz so aufwändig ist wie der Miller-Rabin-Test.
Hierbei potenziert man mit (p-1)/2 statt mit p-1 und muss daher das Ergebnis mit +1 und -1 vergleichen, anstatt nur mit 1. An den grünen und roten Pfeilen sehen Sie, wie die Bedingung programmiert werden muss.
Diesen Primzahltest benutzen wir gleich.
Sie können damit im Prinzip p und q wie oben beschrieben finden. Aber es dauert lange:
Warum ist dies nicht schnell genug? Der Primzahltest muss für sehr viele Kandidaten gemacht werden, die nicht prim sind.
Streiche vorher Werte von q, die nicht Primzahl sein können.
Diese Idee hat seine Ursprünge im Sieb von Erathostenes, das Primzahlen zwischen 1 und einer Obergrenze findet und Ihnen aus einer der Grundvorlesungen Informatik 1+2 bekannt sein dürfte. Dieses Sieb kann angepasst werden, um Primzahlen zwischen einer Untergrenze Q und einer Obergrenze Q' zu finden.
Es ist im unteren Teil der Folie grafisch dargestellt.
Wie bei Erathostenes startet man mit der kleinsten Primzahl 2 und schaut, welche q im Intervall [Q,Q'] durch 2 teilbar sind. Um dies mit einem Array A[.] mit Indizes ab 0, also aus dem Intervall [0,Q'-Q] zu bewerkstelligen, schreibt man die Einträge als Q+x mit x aus dem Intervall [0,Q'-Q]. Man initialisiert A[x]=1 überall (Q+x vermutlich Primzahl). Wie bei Erathostenes, setzt man A[x]=0 (Q+x keine Primzahl), wenn
Q+x=0 mod 2, also für die Indizes x mit x=-Q mod 2.
Für weitere kleine Primzahlteiler h = 3, 5, 7, ... tut man dasselbe bis zu einer Obergrenze, die man mit Laufzeittests seiner Implementierung experimentell festlegen kann. Ab einer Stelle Z.B. h=53, dann sind nur noch Kandidaten übrig, deren kleinster Teiler mindestens 59 ist, also testet man nur noch jede 59-te Zahl vergeblich.
Die entsprechende Bedingung ist dafür natürlich
Q+x=0 mod h, also für die Indizes x mit x=-Q mod h wird A[x]=0 gesetzt.
enthält den Algorithmus
jetzt kann man für die gefundenen q, entweder die "simple Idee" von oben anwenden, oder (wenn Sie eine programmiertechnische Herausforderung suchen), auch p mit einem Sieb finden.
ein Sieb für p (nicht auf der Folie, nicht zwingend erforderlich)
wählen Sie T wie oben zufällig, Implementieren Sie ein Sieb für die richtigen t's zwischen T und einer Obergrenze T'
bereiten Sie nun ein Array B[.] vor, nun aber suchen Sie für die Liste kleiner Primzahlen r diejenigen t mit
q*(T+x)+1 = 0 mod r => x=-1/q - T mod r
und dann für diese x wieder B[x]=0 setzen.
Die Stellen, an denen B[x] = 1 entsprechen nun möglichen Primzahlen p=q*(T+x)+1. Nur für diese p wird dann ein Primzahltest nötig.