Effizient Primitivwurzeln für Verschlüsselungen mit ca. 2^160 Gruppenelementen berechnen?

Question

ich möchte für das Diffie-Hellman Verfahren wissen, wie man denn Primitivwurzeln für Gruppen mit

bis zu 2^160 Gruppenelementen findet. Bisher bin ich leider größtenteils auf Brute-Force Methoden gestoßen,

die aber bei so vielen Gruppenelementen viel zu lange brauchen.
Geht es schneller?

Answer 1

Es gibt keine schöne Formel oder Verfahren zum Finden von Primitivwurzeln. Aber Brute-Force tut es auch und es im Allgemeinen auch nicht wirklich langsam, denn es gibt genügend Primitivwurzeln zum Drüberstolpern.

Comments

Bei 2^160 Gruppenelementen muss man dann also im average case mit Brute Force
2^159-1 Multiplikationen durchführen um definitiv zu wissen ob es eine Primitivwurzel ist?

Da braucht selbst der Tianhe-1A mit 2.5 Billiarden Multiplikationen pro Sekunde ca 1.8*10^25 Jahre..?

Geht es vielleicht über die Gruppenordnung des Elements und der Ordnung der Gruppe?

---

Keine Ahnung wie du auf diese Zahlen kommst. Eine einfache Standardmethode ist folgende: Sei n die Gruppenordnung mit Primfaktorzerlegung $$n=p_1^{e_1} \cdot \ldots \cdot p_r^{e_r}$$. Ist $$ x^\frac{n}{p_i} \neq 1$$ für alle i so ist x eine Primtivwurzel

---

Ist die Gruppe von der Form $$(\mathbb z/m\mathbb Z)^\times$$ so kann man die zu betrachtenden Moduln zusätzlich mit dem chin. Restsatz verringern.

---

Zunächst einmal bedanke ich mich für deine hilfreiche Antwort! Das ist natürlich dann ein "relativ" effizientes Verfahren, obwohl ich eine extrem lange Zahl in Primfaktoren zerlegen muss.

Was ist denn, wenn n eine Primzahl ist? Dann wären demnach theoretisch nur Elemente der Restklasse 1+nZ keine Primitivwurzeln und man könnte sie sogar direkt bestimmen. Das funktioniert aber nicht bei
n=5^1=p_1 und x=4:

x^1 = 4

x^2 = 16 mod 5 = 1
x^3 = 64 mod 5 =4

...

Obwohl x^{n/p} = x^1 = 4 != 1 gilt..

Habe ich irgendwo einen Denkfehler?

---

Die Aussage "Dann wären demnach theoretisch nur Elemente der Restklasse 1+nZ keine Primitivwurzeln und man könnte sie sogar direkt bestimmen." ist schlicht falsch. $$(\mathbb Z /m \mathbb Z)^\times$$ hat genau $$\varphi(\varphi(m))$$ Primitivwurzeln. Bzgl. "relativ: Niemand hat beahauptet alles würde schnell und einfach gehen. Die Kryptographie, insb. die asymmetrische, baut ja grade darauf, dass bestimmtes gerade nur sehr langsam geht. Und beim Standard-DH hat man m prim, d.h. man braucht überhaupt keine Primfaktorzerlegung machen. Oder willst du auf was anderes raus? (Die Größenordnung würd auf ECC passen..)

---

Ich bin ein wenig verwirrt, deine Definition war doch die folgende:

 

"Sei n die Gruppenordnung mit Primfaktorzerlegung 

n=p₁^e₁*p₂^e₂*...*p_p^e_p

Falls x^{n/p_i} ≠ 1 für alle i≤p so ist x eine Primitivwurzel"

 

Sei also n=5 , d.h. p₁=5

Es gilt 4^{5/5} = 4 ≠ 1

 

Aber 4 ist keine Primitivwurzel.

 

---

$$(\mathbb Z/5 \mathbb Z)^\times §§ hat 4 Elemente nicht 5. Der letzte Satz in meinem letzten Kommentar ist Unsinn, bitte gedanklich streichen; leider kann ich nicht mehr editieren.

---

Haha achso ja stimmt! Dann ist alles klar, danke !