Ein Element g der Ordnung q in Zp suchen

Neue Frage »

Kai____ Auf diesen Beitrag antworten »
Ein Element g der Ordnung q in Zp suchen
Hallo zusammen,

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
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! smile

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
/* pq[0] = p pq[1] = q mit p = 2q+1 */
BigInteger[] pq = PrimeHelper.pkq1(1000, 2, 10, new SecureRandom());
		boolean gFound = false;
		BigInteger g = null;
		while(!gFound) {
			SecureRandom sr = new SecureRandom();
			int random = sr.nextInt(pq[0].bitLength());
			BigInteger toTest = new BigInteger(random, new SecureRandom());
			BigInteger is1 = toTest.modPow(pq[1], pq[0]);
			if(is1.equals(BigInteger.ONE)) {
                                g = toTest;
				gFound = true;
				System.out.println(g);
			}
		}
                .... //Generie Schluesselpaar
AD Auf diesen Beitrag antworten »

Zitat:
Original von Kai____
Ich finde da leider keinen effizienten Algorithmus fuer

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. verwirrt
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 :-)
Kai____ Auf diesen Beitrag antworten »

Nachtrag:

Zu beachten ist, dass dieser Algorithmus NUR bei sicheren Primzahlen funktioniert. Nachzulesen in "Applied Cryptography"
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »