Hallo zusammen,

ich muss für einen Algorithmus  g = (a^M) - 1 mod N  ausrechnen um danach ggT(g, N) != 0 zu checken. Das Problem bei der ganzen Sache ist, dass M sehr groß ist. Da ich aber die Primfaktorzerlegung von M kenne möchte ich folgendes rechnen:

Für jeden Primfaktor q_i von M berechne ich: g = (a^q_i) - 1 mod N und checke ggT(g, N) != 0. Falls dies gilt stoppe ich und habe mein Ergebniss. Falls nicht mache ich mit den nächsten Primfaktor weiter bis ich alle ausprobiert habe.

Da ich im Internet nicht genauere Informationen zu diesen Gedanken finden kann wollte ich fragen ob das mathematisch richtig ist.