FGI Übungsaufgabe 10.1.c
2007-01-14 18:05
ferhat
Hi
Ich habe ein Problem mit FGI einer Aufgabe, leider komme ich nicht mehr weiter.
Die Aufgaben Stellung sieht wie folgt aus
Durch ungünstige Werte kann ein RSA-Schlüssel gebrochen werden. Beweisen Sie, dass p oder q gleich ggt((a^(r/2) − 1) mod n, n), falls a^r = 1 mod n für eine gerade natürliche Zahl r > 0 gilt! (Hinweis: Wenden Sie die 3. binomische Formel auf a^r − 1 = 0 an!)
Ich hatte als Ansatz, dass a^r eine Zahl sein muss die in der Primfaktorzerlegung mindestes 2^1 enthalten muss, leider komme ich auch mit dem Hinweis auch nicht leider weiter.
Kann mir jemand helfen, ansätze geben ??
Danke
Ich habe ein Problem mit FGI einer Aufgabe, leider komme ich nicht mehr weiter.
Die Aufgaben Stellung sieht wie folgt aus
Durch ungünstige Werte kann ein RSA-Schlüssel gebrochen werden. Beweisen Sie, dass p oder q gleich ggt((a^(r/2) − 1) mod n, n), falls a^r = 1 mod n für eine gerade natürliche Zahl r > 0 gilt! (Hinweis: Wenden Sie die 3. binomische Formel auf a^r − 1 = 0 an!)
Ich hatte als Ansatz, dass a^r eine Zahl sein muss die in der Primfaktorzerlegung mindestes 2^1 enthalten muss, leider komme ich auch mit dem Hinweis auch nicht leider weiter.
Kann mir jemand helfen, ansätze geben ??
Danke