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