If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Schnelle modulare Exponentialrechnung

Wie kann man A^B mod C schnell berechnen, wenn B eine 2er-Potenz ist?

Modulare Multiplikationsregeln verwenden:
d.h. A ^ 2 mod C = (A * A) mod C = ((ein mod C) * (ein mod C)) mod C
Wir können dies verwenden, um 7 ^ 256 mod 13 schnell zu berechnen
7 ^ 1 mod 13 = 7
7 ^ 2 mod 13 = (7 ^ 1 * 7 ^ 1) mod 13 = (7 ^ 1 mod * 13 * 7 ^ 1 mod 13) mod 13
Wir setzen unser vorheriger Ergebnis für 7 ^ 1 mod 13 in diese Gleichung ein.
7 ^ 2 mod 13 = (7 * 7) mod 13 = 49 mod 13 = 10
7 ^ 2 mod 13 = 10
7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13
Wir setzen unser vorheriger Ergebnis für 7 ^ 2 mod 13 in diese Gleichung ein.
7 ^ 4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
7 ^ 4 mod 13 = 9
7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13
Wir setzen unser vorheriger Ergebnis für 7 ^ 4 mod 13 in diese Gleichung ein.
7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3
Wir fahren in dieser Weise fort und setzen vorherige Ergebnisse in unsere Gleichungen ein.
... ...nach 5 Wiederholungen erzielten wir:
7 ^ 256 mod 13 = (7 ^ 128 * 7 ^ 128) mod 13 = (7 ^ 128 mod 13 * 7 ^ 128 mod 13) mod 13
7 ^ 256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7 ^ 256 mod 13 = 9
Dies ergibt eine schnelle Methode zur Berechnung von A ^ B mod C sofern B eine Zweierpotenz ist.
Jedoch brauchen wir auch eine Methode für schnelle modulare Exponenzierung wenn B keine Zweierpotenz ist.

Wie kann A^B mod C für jedes B schneller berechnet werden?

Schritt 1: Teile B in 2er-Potenzen, in dem du sie als Binärzahlen schreibst

Beginne bei der am weitesten rechts stehenden Ziffer, lass k = 0 und für jede Ziffer:
  • Wenn die Ziffer 1 ist, brauchen wir einen Teil für 2 ^ k, sonst nicht
  • Füge 1 zu k hinzu und verschiebe nach links in die nächste Ziffer

Schritt 2: Berechne mod C der Potenzen von 2 ≤ B

5 ^ 1 mod 19 = 5
5 ^ 2 mod 19 = (5 ^ 1 * 5 ^ 1) mod 19 = (5 ^ 1 mod 19 * 5 ^ 1 mod 19) mod 19
5 ^ 2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5 ^ 2 mod 19 = 6
5 ^ 4 mod 19 = (5 ^ 2 * 5 ^ 2) mod 19 = (5 ^ 2 mod 19 * 5 ^ 2 mod 19) mod 19
5 ^ 4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5 ^ 4 mod 19 = 17
5 ^ 8 mod 19 = (5 ^ 4 * 5 ^ 4) mod 19 = (5 ^ 4 mod 19 * 5 ^ 4 mod 19) mod 19
5 ^ 8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5 ^ 8 mod 19 = 4
5 ^ 16 mod 19 = (5 ^ 8 * 5 ^ 8) mod 19 = (5 ^ 8 mod 19 * 5 ^ 8 mod 19) mod 19
5 ^ 16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5 ^ 16 mod 19 = 16
5 ^ 32 mod 19 = (5 ^ 16 * 5 ^ 16) mod 19 = (5 ^ 16 mod 19 * 5 ^ 16 mod 19) mod 19
5 ^ 32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5 ^ 32 mod 19 = 9
5 ^ 64 mod 19 = (5 ^ 32 * 5 ^ 32) mod 19 = (5 ^ 32 mod 19 * 5 ^ 32 mod 19) mod 19
5 ^ 64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5 ^ 64 mod 19 = 5

Schritt 3: Verwende die Eigenschaften der modularen Multiplikation, um die berechneten mod C-Werte zu kombinieren

5 ^ 117 mod 19 = (5 ^ 1 * 5 ^ 4 * 5 ^ 16 * 5 ^ * 32 * 5 ^ 64) mod 19
5 ^ 117 mod 19 = (5 ^ 1 mod 19 * 5 ^ 4 mod 19 * 5 ^ 16 mod 19 * 5 ^ 32 mod 19 * 5 ^ 64 mod 19) mod 19
5 ^ 117 mod 19 = (5 * 17 * 16 * 9 * 5) mod 19
5 ^ 117 mod 19 = 61200 mod 19 = 1
5 ^ 117 mod 19 = 1

Anmerkung:

Es gibt weitere Optimierungstechniken, aber nicht im Anwendungsbereich dieses Artikels. Es sei darauf hingewiesen, dass wenn wir modulare Exponentiation in der Kryptographie durchführen es nicht ungewöhnlich ist, dass wir Exponenten für B verwenden die mehr als 1000 Bits haben.

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.