Wie man einen exponentiellen Turm auswertet modulo a prime

Question

Ich möchte einen schnellen Algorithmus finden, um einen Ausdruck wie den folgenden zu bewerten, wobei P prim ist.

A^B^C^D^E mod P 

Beispiel:

(9^(3^(15^(3^15)))) mod 65537 = 16134 

Das Problem ist, die Zwischenergebnisse viel zu groß wachsen zu behandeln.

Answer 1

Grundsätzlich ist das Problem reduziert sich auf Rechen a^T mod m für gegebene a, m und einer Laufzeit T die ridiulously riesig. Wir sind jedoch in der Lage, T mod n mit einem gegebenen Modul n viel schneller als T zu bewerten. Also fragen wir: "Gibt es eine ganze Zahl n, so dass a^(T mod n) mod m = a^T mod m?"

Nun, wenn a und m sind coprime, wir wissen, dass n = phi(m) unsere Bedingung erfüllt nach Euler's theorem:

a^T        (mod m) 
= a^((T mod phi(m)) + k * phi(m)) (mod m) (for some k) 
= a^(T mod phi(m)) * a^(k * phi(m)) (mod m) 
= a^(T mod phi(m)) * (a^phi(m))^k (mod m) 
= a^(T mod phi(m)) * 1^k   (mod m) 
= a^(T mod phi(m))     (mod m) 

Wenn wir phi(m) berechnen kann (was zum Beispiel zu tun, in O(m^(1/2)) einfach ist, oder wenn wir das wissen, Primfaktorzerlegung von m), haben wir das Problem auf die Berechnung T mod phi(m) und eine einfache modular exponentiation reduziert.

Was ist, wenn a und m nicht koprimieren? Die Situation ist nicht so angenehm wie zuvor, da es möglicherweise keinen gültigen n mit der Eigenschaft a^T mod m = a^(T mod n) mod m für alle T gibt. Wir können jedoch zeigen, dass die Sequenz a^k mod m für einen Zyklus nach irgendeinem Punkt eingibt, dh es gibt x und C mit x, C < m, so dass a^y = a^(y + C) für alle y >= x.

Beispiel: Für a = 2, m = 12 erhalten wir die Sequenz 2^0, 2^1, ... = 1, 2, 4, 8, 4, 8, ... (mod 12). Wir können den Zyklus mit den Parametern x = 2 und C = 2 sehen.

Wir können die Zykluslänge über Brute-Force finden, indem Sie die Sequenzelemente Berechnung a^0, a^1, ..., bis wir zwei Indizes X < Y mit a^X = a^Y finden. Jetzt setzen wir x = X und C = Y - X. Dies ergibt einen Algorithmus mit O(m) Exponentiationen pro Rekursion.

Was, wenn wir es besser machen wollen? Danke an Jyrki Lahtonen von Math Exchange für die Bereitstellung the essentials for the following algorithm!

Lassen Sie uns die Sequenz d_k = gcd(a^k, m) bewerten, bis wir eine x mit d_x = d_{x+1} finden. Dies wird höchstens log(m) GCD-Berechnungen erfordern, da x durch den höchsten Exponenten in der Primfaktorzerlegung von m begrenzt ist. Lassen Sie C = phi(m/d_x). We can now prove thata^{k + C} = a^k für alle k >= x, so haben wir die Zyklusparameter in O(m^(1/2)) Zeit gefunden.

Nehmen wir an, wir haben x und C gefunden und möchten jetzt a^T mod m berechnen. Wenn T < x, ist die Aufgabe mit einfachen modularen Exponentiation trivial durchzuführen. Ansonsten haben wir T >= x und kann somit den Einsatz des Zyklus machen:

a^T          (mod m) 
= a^(x + ((T - x) mod C))     (mod m) 
= a^(x + (-x mod C) + (T mod C) + k*C) (mod m)  (for some k) 
= a^(x + (-x mod C) + k*C) * a^(T mod C) (mod m) 
= a^(x + (-x mod C)) * a^(T mod C)  (mod m) 

Auch hier haben wir das Problem auf ein Teilproblem der gleichen Form reduziert („berechnen T mod C“) und zwei einfache Diskrete Exponentialfunktion.

Da der Modulus in jeder Iteration um mindestens 1 reduziert wird, erhalten wir für die Laufzeit dieses Algorithmus eine ziemlich schwache Grenze von O(P^(1/2) * min (P, n)), wobei n die Höhe des Stacks ist. In der Praxis sollten wir viel besser werden, da erwartet wird, dass die Moduli exponentiell abnehmen. Natürlich ist dieses Argument ein wenig hand-wellig, vielleicht kann eine mathematisch geneigtere Person es verbessern.

Es gibt ein paar Grenzfälle zu berücksichtigen, dass tatsächlich Ihr Leben ein bisschen leichter machen: Sie können sofort stoppen, wenn m = 1 (das Ergebnis ist in diesem Fall 0) oder wenn a ein Vielfaches von m (das Ergebnis 0 als gut in diesem Fall).

EDIT: Es kann gezeigt werden, dass x = C = phi(m) gültig ist, um eine schnelle und schmutzige Lösung wir die Formel

a^T = a^(phi(m) + T mod phi(m)) (mod m) 

für T >= phi(m) oder sogar T >= log_2(m) verwenden können.