Wie kann WolframAlpha Zahlen so schnell potenzieren?

Question

Ich frage mich, wie RSA-Algorithmus mit solchen großen Zahlen und tried one example in WolframAlpha beschäftigt. Wie können sie mit solchen verrückten Zahlen umgehen?

EDIT: Nur um es noch bizarre, one more example

Answer 1

Es gibt einen einfachen Algorithmus exponentiation by squaring genannt, die dazu verwendet werden kann, ein ^b mod c sehr effizient zu berechnen. Es basiert auf der Beobachtung, dass

a ^2k mod c = (a k ) mod c

a ^{2k + 1} mod c = a & middot; (A ^k) mod c

Vor diesem Hintergrund können Sie eine ^b mod c mit diesem rekursiven Ansatz berechnen:

function raiseModPower(a, b, c): 
    if b == 0 return 1 
    let d = raiseModPower(a, floor(b/2), c) 
    if b mod 2 = 1: 
     return d * d * a mod c 
    else 
     return d * d mod c 

Dies gilt nur O (log b) Multiplikationen , von denen jede nicht mehr Ziffern als O (log c) haben kann, also ist es wirklich schnell. Dies ist, wie RSA-Implementierungen Dinge zu Mächten erheben. Sie können dies als iterativ neu schreiben, wenn Sie möchten, obwohl ich denke, dass die rekursive Präsentation wirklich sauber ist.

Sobald Sie diesen Algorithmus haben, können Sie Standardtechniken zum Multiplizieren von Zahlen mit beliebiger Genauigkeit verwenden, um die Berechnung durchzuführen. Da nur O (log b) Iterationen der Multiplikation erforderlich sind (im Gegensatz zu z. B. b Iterationen), ist es verrückt schnell. Sie werden nie tatsächlich ein ^b berechnen und dann es um c, die auch die Anzahl der Stellen niedrig und macht es noch schneller.

Hoffe, das hilft!