Hauptinhalt
Kurs: Informatik > Lerneinheit 2
Lektion 5: Modulare Arithmetik- Was ist modulare Arithmetik?
- Modulo-Operator
- Modulo-Challenge
- Kongruenz Modul
- Kongruenzrelation
- Gleichwertigkeitsbeziehungen
- Das Quotientenrest-Theorem
- Modulare Addition und Subtraktion
- Modulare Addition
- Herausforderung zum Modulusoperator (Addition und Subtraktion)
- Modulare Multiplikation
- Modulare Multiplikation
- Modulare Exponentialrechnung
- Schnelle modulare Exponentialrechnung
- Schnelle modulare Exponentialrechnung
- Modulare Kehrzahlen
- Der euklidische Algorithmus
© 2024 Khan AcademyNutzungsbedingungenDatenschutzerklärungCookie-Meldung
Modulare Exponentialrechnung
Endlich, lass uns nun die Potenzeigenschaft erkunden:
A^B mod C = ( (A mod C)^B ) mod C
Oft wollen wir dies berechnen: A ^ B mod C für große Werte von B.
Leider wird A ^ B sehr groß, selbst für kleine Werte für B.
Leider wird A ^ B sehr groß, selbst für kleine Werte für B.
Zum Beispiel:
2^90 = 1.237.940.039.290.000.000.000.000.000
7^256 = 2.213.595.400.050.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 83.794.038.078.300.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 721.264.246.243.000.000.000.000.000
Diese riesigen Werte führen dazu, dass unsere Rechner und Computer, Überlauffehler zurückgegeben.
Selbst wenn dies nicht täten, dauert es eine sehr lange Zeit, die mod dieser riesigen Zahlen direkt zu finden.
Selbst wenn dies nicht täten, dauert es eine sehr lange Zeit, die mod dieser riesigen Zahlen direkt zu finden.
Was können wir tun, um die Größe der beteiligten Terme zu verringern Sie und unsere Berechnungen schneller machen?
Angenommen, wir möchten 2 ^ 90 mod 13 berechnen, aber wir haben einen Rechner, die keine größeren Zahlen als 2 ^ 50 handhaben kann.
Hier ist eine einfache teile und herrsche-Strategie:
kleinere Teile
Exponentenregeln
2^90 = 2^50 * 2^40
mod C
jeden Teil
2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3
2^40 mod 13 = 1099511627776 mod 13 = 3
Multiplikation-Eigenschaften
die Teile zusammen zu fügen
2^90 mod 13 = (2^50 * 2^40) mod 13
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12
Wie können wir A ^ B mod C schnell berechnen, wenn B eine 2er-Potenz ist?
Wie könnten wir 7 ^ 256 mod 13 berechnen, wenn wir einen Rechner verwenden, der keine Zahlen handhaben kann, die größer sind als 7 ^ 10?
Wir könnten 7 ^ 256 aufteilen in 25 Teile von 7 ^ 10 und einen Teil von 7 ^ 6, aber die wäre nicht sehr effizient.
Es gibt einen besseren Weg....
Willst du an der Diskussion teilnehmen?
Noch keine Beiträge.