Ein Element g der Ordnung q in Zp suchen |
15.05.2010, 19:54 | Kai____ | Auf diesen Beitrag antworten » | |||||
Ein Element g der Ordnung q in Zp suchen Folgender Ansatz; Ich habe: p,q als sichere Primzahlen (p = kq+1). Ich muss nun ein zufaelliges Element g \in Zp waehlen, welches die Ordnung q hat. Ich finde da leider keinen effizienten Algorithmus fuer, habt ihr da eine Idee? Gruesse, Kai |
|||||||
15.05.2010, 20:22 | Kai____ | Auf diesen Beitrag antworten » | |||||
RE: Ein Element g der Ordnung q in Zp suchen Sorry... mein Fehler... Hatte vergessen, dass modulares Potenzieren extrem effizient ist und man dementsprechend einfach mal ein paar Zahlen raet :-) Kann mit denn trotzdem wer sagen ob dieser probabilistische Algorithmus den Anforderungen genuegt? Waere echt super!
|
|||||||
15.05.2010, 20:31 | AD | Auf diesen Beitrag antworten » | |||||
In welchem Szenario effizient? Wenn du diese Zufallsauswahl z.B. sehr oft für ein- und dieselben (also festen) brauchst, dann kann sich u.U. eine (teilweise oder sogar ganze) Vorberechnung dieser Elemente der Ordnung lohnen. |
|||||||
15.05.2010, 22:44 | Kai____ | Auf diesen Beitrag antworten » | |||||
Ich brauche dieses Element nur ein einziges Mal, naemlich zur Erzeugung des Schluesselpaares; zu Bedenken ist, dass die Zahlen sehr gross werden koennen (>1024Bit) und die ganze Nacht auf das g zu warten ist nunmal auch nicht gerade das, was ich will. Der Algotrithmus scheint aber zu funktionieren und das relativ schnell... Also wenn ihn mal wer braucht :-) |
|||||||
16.05.2010, 15:39 | Kai____ | Auf diesen Beitrag antworten » | |||||
Nachtrag: Zu beachten ist, dass dieser Algorithmus NUR bei sicheren Primzahlen funktioniert. Nachzulesen in "Applied Cryptography" |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|