SAGE Implementierung von diskreten Logarithmus in Untergruppe der Gruppe von Einheiten

Question

Dies ist eine Frage im Zusammenhang mit this eins. Kurz gesagt, in ElGammal Kryptosystem mit zugrunde liegenden Gruppe der Gruppe von Einheiten Modulo eine Primzahl p Ich bin aufgefordert, eine Untergruppe von Index 2 zu finden, um diskrete Logarithmus Problem zu lösen, um das System zu brechen.

Offensichtlich ist die Gruppe der Einheiten modulo eine Primzahl zyklisch, wenn x ein Generator ist, erzeugt x^2 eine Untergruppe von Index 2. Nun, was ist ein guter Weg, das Problem des diskreten Logarithmus auf Salbei zu lösen? Wie würde ich das Ergebnis der Lösung des diskreten Logarithmusproblems in dieser Untergruppe verwenden, um es in der gesamten Gruppe zu lösen?

Answer 1

Sage weiß, wie diskrete Logarithmen in endlichen Körpern zu berechnen:

sage: K = GF(19) 
sage: z = K.primitive_element() 
sage: a = K.random_element() 
sage: b = a.log(z) 
sage: z^b == a 
True 

Sie diese Funktion verwenden kann, den diskreten Logarithmus in der Subgruppe des Index 2

sage: x = z^2 
sage: a = K.random_element()^2 
sage: a.log(x) 
6 

Dies ist nur ein Spielzeug zu lösen Beispiel, aber beachten Sie, dass dies nicht effizienter ist als das Lösen des diskreten Logarithmus in der vollständigen Gruppe ₉ *.

Es ist wahr, dass die Effizienz von generischen Algorithmen (z. B. Baby Schritt-Giant Schritt, Pollard Rho, ...) direkt auf die Größe der Untergruppe bezogen ist; Algorithmen, die zur Lösung von diskreten Logarithmen in endlichen Feldern (Zahlenfeldsieb, Funktionsfeldsieb) verwendet werden, sind jedoch größtenteils unempfindlich gegenüber der Größe der multiplikativen Untergruppe und im Allgemeinen viel effizienter als generische Algorithmen.