Algorithmen Vorschläge zum erstellt am
WS '97/98 Script (05./06. Feb. 1998) 08. Feb. 1998
 
Script

Sondierung mit einem generierenden Element des Körpers Fp

Sei p eine Primzahl und g < p, dann ist g ein Generator mod p, wenn für alle b von 1 bis p-1 ein a existiert, so daß g hoch a kongruent b (mod p).
Zum Beispiel ist 2 ein Generator mod 11:
 
b a 2a Rechenhilfe
1 10 1024 93*11=1023
2 1 2
3 8 256 23*11=253
4 2 4
5 4 16
6 9 512 46*11=506
7 7 128 11*11=121
8 3 8
9 6 64 5*11=55
10 5 32 2*11=22

Es ist einfach zu testen, ob g Generator ist, wenn man die Primfaktorzerlegung von p-1 kennt. Seien q1 , q1 , ..., qn die verschiedenen Primfaktoren von p-1, dann berechnet man g(p-1)/q mod p für alle q = qi. Erhält man 1 für ein qi, dann ist g kein Generator. Sind alle Werte von 1 verschieden, dann ist g ein Generator.
(Frei übersetzt aus: Bruce Schneier, "Applied Cryptographiy" 2nd Edition)

Source: GeFpHashing.java


Joachim Wagner
Osnabrück, den 08. Februar 1998