In der Mathematik ist die modulare Arithmetik ein Rechensystem für ganze Zahlen, mit deren Hilfe sie sich "umdrehen", wenn sie einen bestimmten Wert erreichen - den Modul (oder den Plural davon). Der moderne Zugang zu dieser Art von Wissenschaft wurde von Carl Friedrich Gauß in seinen 1801 veröffentlichten Disquisitiones Arithmeticae entwickelt. Informatiker verwenden diese Methode sehr gerne, da sie sehr interessant ist und gewisse neue Möglichkeiten bei Operationen mit Zahlen eröffnet.
Essenz
Weil die Stundenzahl nach Erreichen von 12 wieder beginnt, ist sie arithmetisch modulo 12. Nach der Definition unten entspricht 12 nicht nur 12, sondern auch 0, man kann also die Zeit auch "" nennen" 12:00". "0:00". Schließlich ist 12 dasselbe wie 0 modulo 12.
Modulare Arithmetik kann mathematisch verarbeitet werden, indem eine kongruente Beziehung zu ganzen Zahlen eingeführt wird, die mit Operationen auf ganzen Zahlen kompatibel istZahlen: Addition, Subtraktion und Multiplikation. Für eine positive ganze Zahl n werden zwei Zahlen a und b als kongruent modulo n bezeichnet, wenn ihre Differenz a - b ein Vielfaches von n ist (das heißt, wenn es eine ganze Zahl k gibt, so dass a - b=kn).
Abzüge
In der theoretischen Mathematik ist die modulare Arithmetik eine der Grundlagen der Zahlentheorie, die fast alle Aspekte ihres Studiums betrifft, und wird auch häufig in der Theorie von Gruppen, Ringen, Knoten und abstrakter Algebra verwendet. Im Bereich der angewandten Mathematik wird es in Computeralgebra, Kryptografie, Informatik, Chemie, bildender Kunst und Musik verwendet.
Übung
Eine sehr praktische Anwendung ist die Berechnung von Prüfsummen in Seriennummernkennungen. Beispielsweise verwenden einige allgemeine Buchstandards die Arithmetik Modulo 11 (falls vor dem 1. Januar 2007 veröffentlicht) oder Modulo 10 (falls sie vor oder nach dem 1. Januar 2007 veröffentlicht wurden). Ähnlich zum Beispiel bei International Bank Account Numbers (IBANs). Dies verwendet Modulo-97-Arithmetik, um Benutzereingabefehler in Bankkontonummern zu erkennen.
In der Chemie ist die letzte Ziffer der CAS-Registrierungsnummer (die eindeutige Identifikationsnummer für jede chemische Verbindung) die Prüfziffer. Sie wird berechnet, indem die letzte Ziffer der ersten beiden Teile der CAS-Registrierungsnummer mit 1 multipliziert wird, die vorherige Ziffer 2 mal, die vorherige Ziffer 3 mal usw., alles zusammengezählt und die Summe modulo 10. berechnet wird
Was ist Kryptografie? Die Sache ist diees hat eine sehr starke Verbindung mit dem diskutierten Thema. In der Kryptografie liegen die Gesetze der modularen Arithmetik direkt Public-Key-Systemen wie RSA und Diffie-Hellman zugrunde. Hier liefert es die endlichen Felder, die elliptischen Kurven zugrunde liegen. Wird in verschiedenen symmetrischen Schlüsselalgorithmen verwendet, einschließlich Advanced Encryption Standard (AES), International Data Encryption Algorithm und RC4.
Bewerbung
Diese Methode wird in Bereichen verwendet, in denen Sie Zahlen lesen müssen. Es wurde von Mathematikern entwickelt und wird von allen genutzt, insbesondere von Informatikern. Dies ist in Büchern wie Modular Arithmetic for Dummies gut dokumentiert. Eine Reihe von Experten empfiehlt jedoch, solche Literatur nicht ernst zu nehmen.
In der Informatik wird modulare Arithmetik oft in bitweisen und anderen Operationen mit kreisförmigen Datenstrukturen fester Breite verwendet. Analysten lieben es, es zu verwenden. Die Modulo-Operation ist in vielen Programmiersprachen und Taschenrechnern implementiert. In diesem Fall ist es ein Beispiel einer solchen Anwendung. Auch Modulo-Vergleich, Division mit Rest und andere Tricks kommen beim Programmieren zum Einsatz.
In der Musik wird die Arithmetik Modulo 12 verwendet, wenn ein System gleicher Stimmung von zwölf Tönen betrachtet wird, in dem die Oktave und die Enharmonik äquivalent sind. Mit anderen Worten, die Tasten im Verhältnis 1-2 oder 2-1 sind gleichwertig. In der Musik und anderen Geisteswissenschaften spielt Arithmetik eine ziemlich große Rolle, aber in LehrbüchernInformatiker schreiben normalerweise nicht darüber.
Methode zum Reduzieren von Neunen
Die 9er-Konvertierungsmethode bietet eine schnelle Überprüfung manueller dezimaler arithmetischer Berechnungen. Es basiert auf der modularen Arithmetik modulo 9 und insbesondere auf der entscheidenden Eigenschaft 10 10 1.
es gibt noch andere Beispiele. Arithmetik Modulo 7 wird in Algorithmen verwendet, die den Wochentag für ein bestimmtes Datum bestimmen. Insbesondere Zellers Kongruenz und der Doomsday-Algorithmus machen starken Gebrauch von Arithmetik Modulo 7.
Andere Anwendungen
Zur modularen Arithmetik in der Kryptographie wurde bereits gesagt. In diesem Bereich ist sie einfach unersetzlich. Ganz allgemein findet modulare Arithmetik auch Anwendung in Disziplinen wie Recht, Wirtschaft (wie Spieltheorie) und anderen Bereichen der Sozialwissenschaften. Also dort, wo die anteilige Aufteilung und Verteilung von Ressourcen eine große Rolle spielt.
Weil modulare Arithmetik so vielseitig einsetzbar ist, ist es wichtig zu wissen, wie schwierig es ist, ein Vergleichssystem zu lösen. Ein lineares Kongruenzsystem kann in Polynomialzeit in Form der Gaußschen Elimination gelöst werden. Dies wird durch den linearen Kongruenzsatz näher beschrieben. Es gibt auch Algorithmen wie die Montgomery-Reduktion, mit denen einfache arithmetische Operationen effizient ausgeführt werden können. Zum Beispiel Multiplikation und Potenzierung modulo n für große Zahlen. Dies ist sehr wichtig zu wissen, um zu verstehen, wasKryptographie. Schließlich funktioniert es nur mit ähnlichen Operationen.
Kongruenz
Einige Operationen, wie das Finden des diskreten Logarithmus oder der quadratischen Kongruenz, scheinen so komplex zu sein wie die ganzzahlige Faktorisierung und sind daher der Ausgangspunkt für kryptographische Algorithmen und Verschlüsselung. Diese Probleme können NP-intermediär sein.
Beispiele
Die folgenden sind drei ziemlich schnelle C-Funktionen - zwei zum Durchführen einer modularen Multiplikation und eine zum Erhöhen auf modulare Zahlen für vorzeichenlose Ganzzahlen bis zu 63 Bit, ohne vorübergehenden Überlauf.
Kurz nach der Entdeckung der ganzen Zahlen (1, 2, 3, 4, 5…) wird deutlich, dass sie in zwei Gruppen eingeteilt werden:
- Gerade: durch 2 teilbar (0, 2, 4, 6..).
- Ungerade: nicht durch 2 teilbar (1, 3, 5, 7…).
Warum ist diese Unterscheidung wichtig? Dies ist der Beginn der Abstraktion. Wir bemerken die Eigenschaften der Zahl (z. B. gerade oder ungerade) und nicht nur die Zahl selbst ("37").
Dies ermöglicht es uns, die Mathematik auf einer tieferen Ebene zu erforschen und Beziehungen zwischen Zahlentypen statt bestimmten zu finden.
Eigenschaften einer Zahl
Eine "Drei" zu sein ist nur eine weitere Eigenschaft einer Zahl. Vielleicht nicht so unmittelbar nützlich wie gerade/ungerade, aber es ist da. Wir können Regeln erstellen wie „dreizehn x drei Adern=dreizehn“und so weiter. Aber es ist verrückt. Wir können nicht ständig neue Wörter bilden.
Die Modulo-Operation (abgekürzt mod oder "%" in vielen Programmiersprachen) ist der Rest, wennAufteilung. Beispiel: „5 mod 3=2“, was bedeutet, dass 2 der Rest ist, wenn Sie 5 durch 3 dividieren.
Bei der Umwandlung alltäglicher Begriffe in Mathematik ist eine „gerade Zahl“dort, wo sie „0 mod 2“ist, was bedeutet, dass der Rest 0 ist, wenn sie durch 2 geteilt wird. Eine ungerade Zahl ist „1 mod 2“(hat einen Rest von 1).
Gerade und ungerade Zahlen
Was ist gerade x gerade x ungerade x ungerade? Nun, es ist 0 x 0 x 1 x 1=0. Tatsächlich können Sie sehen, ob eine gerade Zahl irgendwo multipliziert wird, wo das Gesamtergebnis Null ist.
Der Trick bei der modularen Mathematik besteht darin, dass wir sie bereits zum Speichern der Zeit verwendet haben - manchmal auch als "Uhrenarithmetik" bezeichnet.
Zum Beispiel: 7:00 Uhr (am/pm - spielt keine Rolle). Wo wird der Stundenzeiger in 7 Stunden stehen?
Modulationen
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 ist der Rest, wenn 14 durch 12 geteilt wird. Gleichung 14 mod 12=2 mod 12 bedeutet 14 Stunden und 2 Stunden sehen aus dasselbe auf einer 12-Stunden-Uhr. Sie sind kongruent, angezeigt durch ein dreifaches Gleichheitszeichen: 14 ≡ 2 mod 12.
Noch ein Beispiel: Es ist 8:00 Uhr. Wo wird die große Hand in 25 Stunden sein?
Anstatt 25 zu 8 zu addieren, können Sie verstehen, dass 25 Stunden nur "1 Tag + 1 Stunde" sind. Die Antwort ist einfach. Die Uhr endet also 1 Stunde im Voraus – um 9:00 Uhr.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Du hast intuitiv 25 in 1 umgewandelt und dies hinzugefügt bis 8.
Wenn wir die Uhr als Analogie verwenden, können wir herausfinden, ob diedie Regeln der modularen Arithmetik, und sie funktionieren.
Addition/Subtraktion
Nehmen wir an, zwei Zeiten sehen auf unserer Uhr gleich aus ("2:00" und "14:00"). Wenn wir beiden die gleichen x Stunden hinzufügen, was passiert? Nun, sie ändern sich für den gleichen Betrag auf der Uhr! 2:00 + 5 Stunden ≡ 14:00 + 5 Stunden - beide zeigen 7:00 an.
Warum? Wir können einfach 5 zu den 2 Resten addieren, die beide haben, und sie rücken auf die gleiche Weise vor. Bei allen kongruenten Zahlen (2 und 14) haben Addition und Subtraktion das gleiche Ergebnis.
Es ist schwieriger zu wissen, ob die Multiplikation gleich bleibt. Wenn 14 ≡ 2 (mod 12), können wir beide Zahlen multiplizieren und dasselbe Ergebnis erh alten? Mal sehen, was passiert, wenn wir mit 3 multiplizieren.
Nun, 2:003 × 6:00. Aber was ist 14:003?
Erinnere dich, 14=12 + 2. Also können wir
sagen
143=(12 + 2)3=(123) + (23)
Der erste Teil (123) kann ignoriert werden! Der Überlauf von 12 Stunden, der 14 trägt, wiederholt sich einfach mehrmals. Aber wen kümmert's? Wir ignorieren den Überlauf sowieso.
Multiplikation
Beim Multiplizieren zählt nur der Rest, also die gleichen 2 Stunden für 14:00 und 2:00. Intuitiv sehe ich so, dass die Multiplikation die Beziehung zur modularen Mathematik nicht ändert (Sie können beide Seiten einer modularen Beziehung multiplizieren und das gleiche Ergebnis erh alten).
Wir tun es intuitiv, aber es ist schön, ihm einen Namen zu geben. Sie haben einen Flug, der um 15 Uhr ankommt. Er14 Stunden verzögert. Wann wird es landen?
14 ≡ 2 mod 12. Stell es dir also als 2 Uhr vor, also landet das Flugzeug um 5 Uhr morgens. Die Lösung ist einfach: 3 + 2=5 Uhr morgens. Dies ist etwas komplizierter als die einfache Modulo-Operation, aber das Prinzip ist dasselbe.
