Modulararithmetik

Die Zeitbehandlung auf dieser Uhr verwendet das arithmetische Modulo 12. Das Hinzufügen von 4 Stunden bis 9 Uhr ergibt 1 Uhr, da 13 zu 1 Modulo 12 übereinstimmt.

Im Mathematik, Modulararithmetik ist ein System von Arithmetik zum Ganzzahlen, wo Zahlen "umgehen", wenn sie einen bestimmten Wert erreichen, genannt die Modul. Der moderne Ansatz zur modularen Arithmetik wurde von entwickelt von Carl Friedrich Gauß in seinem Buch DISTQUISATORES ARITHMETHAE, veröffentlicht im Jahr 1801.

Eine vertraute Verwendung modularer Arithmetik ist in der 12-stündige Uhr, in dem der Tag in zwei 12-Stunden-Zeiträume unterteilt ist. Wenn die Zeit jetzt 7:00 Uhr ist, dann wird es 8 Stunden später 3:00 Uhr sein. Einfache Addition würde dazu führen 7 + 8 = 15, aber Uhren "umwickeln" alle 12 Stunden. Da die Stundenzahl bei der 12 -köpfigen Null annimmt, ist dies Arithmetik Modulo 12. In Bezug auf die folgende Definition ist 15 kongruent bis 3 Modulo 12, also "15:00" auf a 24-Stunden-Uhr wird auf einer 12-Stunden-Uhr "3:00" angezeigt.

Kongruenz

Gegeben an ganze Zahl n > 1, genannt Modul, zwei ganze Zahlen a und b sollen sein kongruent Modulo n, wenn n ist ein Divisor von ihrem Unterschied (das heißt, wenn es eine Ganzzahl gibt k so dass ab = Kn).

Kongruenzmodulo n ist ein Kongruenzbeziehung, was bedeutet, dass es ein ist Äquivalenzbeziehung das ist mit den Operationen von kompatibel Zusatz, Subtraktion, und Multiplikation. Kongruenzmodulo n wird bezeichnet:

Die Klammern bedeuten das (Mod n) gilt für die gesamte Gleichung, nicht nur auf der rechten Seite (hier, hier, b). Diese Notation darf nicht mit der Notation verwechselt werden b Mod n (ohne Klammern), was sich auf die bezieht Modulo -Betrieb. In der Tat, b Mod n bezeichnet die einzigartige Ganzzahl a so dass 0 ≤ a < n und (Das heißt, der Rest von wenn geteilt durch ).

Die Kongruenzbeziehung kann als umgeschrieben werden als

explizit seine Beziehung zu zeigen mit Euklidische Division. Allerdings die b Hier muss nicht der Rest der Teilung von sein a durch n. Stattdessen was die Aussage ab (Mod n) Behauptet ist das a und b haben den gleichen Rest, wenn er durch geteilt durch n. Das ist,

wo 0 ≤ r < n ist der übliche Rest. Wenn wir diese beiden Ausdrücke subtrahieren, wiederherstellen wir die vorherige Beziehung:

indem man es einstellt k = pq.

Beispiele

In Modul 12 kann man behaupten:

Weil 38 - 14 = 24, was ein Vielfaches von 12 ist. Eine andere Möglichkeit, dies auszudrücken, besteht darin, dass sowohl 38 als auch 14 den gleichen Rest 2 haben, wenn es durch 12 geteilt wird.

Die Definition der Kongruenz gilt auch für negative Werte. Zum Beispiel:

Eigenschaften

Die Kongruenzbeziehung erfüllt alle Bedingungen eines Äquivalenzbeziehung:

  • Reflexivität: aa (Mod n)
  • Symmetrie: ab (Mod n) wenn ba (Mod n) für alle a, b, und n.
  • Transitivität: if ab (Mod n) und bc (Mod n), dann ac (Mod n)

Wenn a1b1 (Mod n) und a2b2 (Mod n), oder wenn ab (Mod n), dann:[1]

  • a + kb + k (Mod n) für jede ganze Zahl k (Kompatibilität mit Übersetzung)
  • k ak b (Mod n) für jede ganze Zahl k (Kompatibilität mit Skalierung)
  • k ak b (Mod Kn) für jede ganze Zahl k
  • a1 + a2b1 + b2 (Mod n) (Kompatibilität mit Addition)
  • a1a2b1b2 (Mod n) (Kompatibilität mit Subtraktion)
  • a1 a2b1 b2 (Mod n) (Kompatibilität mit Multiplikation)
  • akbk (Mod n) für jede nicht negative Ganzzahl k (Kompatibilität mit Exponentiation)
  • p(a) ≡ p(b) (Mod n)für jeden Polynom p(x) mit Ganzzahlkoeffizienten (Kompatibilität mit der polynomialen Bewertung)

Wenn ab (Mod n)dann ist es im Allgemeinen falsch, dass kakb (Mod n). Das Folgende ist jedoch wahr:

Zur Stornierung gemeinsamer Begriffe haben wir die folgenden Regeln:

  • Wenn a + kb + k (Mod n), wo k ist dann eine ganze Zahl ab (Mod n)
  • Wenn k ak b (Mod n) und k ist coprime mit n, dann ab (Mod n)
  • Wenn k ak b (Mod Kn) und K ≠ 0, dann ab (Mod n)

Das Modulare multiplikative Inverse wird durch die folgenden Regeln definiert:

  • Existenz: Es gibt eine Ganzzahl, die bezeichnet wird a–1 so dass aa–1 ≡ 1 (mod n) dann und nur dann, wenn a ist coprime mit n. Diese ganze Zahl a–1 wird als a genannt Modulare multiplikative Inverse von a Modulo n.
  • Wenn ab (Mod n) und a–1 existiert dann a–1b–1 (Mod n) (Kompatibilität mit multiplikativem Inversen und wenn, wenn a = b, Einzigartigkeitsmodulo n)
  • Wenn a xb (Mod n) und a ist coprime zu nund dann ist die Lösung für diese lineare Kongruenz gegeben durch xa–1b (Mod n)

Das multiplikative Inverse xa–1 (Mod n) kann durch Lösung effizient berechnet werden Bézouts Gleichung zum -Verwendung der Erweiterter euklidischer Algorithmus.

Insbesondere wenn, wenn p ist dann eine Primzahl a ist coprime mit p für jeden a so dass 0 << a < p; Somit gibt es für alle ein multiplikatives Inverse a Das ist nicht mit Null -Modulo kongruent p.

Einige der fortgeschritteneren Eigenschaften von Kongruenzbeziehungen sind die folgenden:

  • Fermats kleiner Theorem: Wenn p ist erstklassig und teilt sich nicht a, dann a p – 1 ≡ 1 (mod p).
  • Eulers Theorem: Wenn a und n sind dann Coprime a φ(n) ≡ 1 (mod n), wo φ ist Eulers Totient -Funktion
  • Eine einfache Folge von Fermats kleinem Satz ist, dass wenn p ist dann Prime, dann a–1a p - 2 (Mod p) ist die multiplikative Umkehrung von 0 << a < p. Allgemeiner aus Eulers Theorem, wenn a und n sind dann Coprime a–1a φ(n) - 1 (Mod n).
  • Eine weitere einfache Folge ist, dass wenn ab (Mod φ(n)), wo φ ist dann Eulers Totient -Funktion, dann kakb (Mod n) bereitgestellt k ist Coprime mit n.
  • Wilsons Theorem: p ist erst und nur wenn und nur wenn (p - 1)! ≡ −1 (Mod p).
  • Chinesischer Rest -Theorem: Für jeden a, b und Coprime m, nEs gibt eine einzigartige x (Mod mn) so dass xa (Mod m) und xb (Mod n). In der Tat, xB mn–1 m + einm–1 n (Mod mn) wo mn–1 ist die Umkehrung von m Modulo n und nm–1 ist die Umkehrung von n Modulo m.
  • Lagrange's Theorem: Die Kongruenz f (x) ≡ 0 (mod p), wo p ist Prime und f (x) = a0 xn + ... + an ist ein Polynom mit ganzzahligen Koeffizienten so, dass a0 ≠ 0 (Mod p), hat höchstens n Wurzeln.
  • Primitive Wurzelmodulo n: Eine Zahl g ist ein primitives Wurzelmodulo n Wenn für jede Ganzzahl a Coprime zu n, Es gibt eine Ganzzahl k so dass gka (Mod n). Ein primitives Wurzelmodulo n existiert, wenn und nur wenn n ist gleich 2, 4, pk oder 2pk, wo p ist eine seltsame Primzahl und k ist eine positive Ganzzahl. Wenn ein primitives Wurzelmodulo n existiert, dann gibt es genau φ(φ(n)) Solche primitiven Wurzeln, wo φ ist die Totient -Funktion des Euler.
  • Quadratische Rückstände: Eine Ganzzahl a ist ein quadratischer Rückstandsmodulo n, wenn es eine Ganzzahl gibt x so dass x2a (Mod n). Eulers Kriterium behauptet das, wenn p ist eine seltsame Prime und a ist kein Vielfaches von p, dann a ist ein quadratischer Rückstandsmodulo p dann und nur dann, wenn

Kongruenzkurse

Wie jede Kongruenz -Beziehung, Kongruenzmodulo n ist ein Äquivalenzbeziehung, und die Äquivalenzklasse der Ganzzahl a, bezeichnet durch an, ist das Set {..., a - 2n, an, a, a + n, a + 2n, ...}. Dieses Set, bestehend aus allen Ganzzahlen kongruent zu aModulon, heißt das Kongruenzklasse, Rückstandsklasse, oder einfach Rückstand der Ganzzahl a Modulon. Wenn der Modul n ist aus dem Kontext bekannt, dass Rückstände auch bezeichnet werden können [a].

Rückstände

Jedes Rückstandsklassenmodulo n kann von einem seiner Mitglieder dargestellt werden, obwohl wir normalerweise jede Restklasse durch die kleinste nichtnegative Ganzzahl repräsentieren, die zu dieser Klasse gehört[2] (Da dies der richtige Rest ist, der sich aus der Teilung ergibt). Zwei Mitglieder verschiedener Rückstandsklassen Modulo n sind Inkongruentmodulo n. Darüber hinaus gehört jede Ganzzahl zu einem und nur einem Rückstandsklassenmodulo n.[3]

Die Menge der Ganzzahlen {0, 1, 2, ...,, n - 1} wird genannt Modulo des geringsten Rückstandssystems n. Jeder Satz von n Ganzzahlen, von denen keine zwei kongruenten Modulo sind n, heißt a Komplettes Rückstandssystemmodulo n.

Das am wenigsten Rückstandssystem ist ein vollständiges Rückstandssystem, und ein vollständiges Rückstandssystem ist einfach ein Satz, der genau einen enthält Vertreter jedes Rückstandsklassenmodulo n.[4] Zum Beispiel. Das geringste Rückstandssystemmodulo 4 ist {0, 1, 2, 3}. Einige andere vollständige Rückstandssysteme Modulo 4 umfassen:

  • {1, 2, 3, 4}
  • {13, 14, 15, 16}
  • {–2, –1, 0, 1}
  • {–13, 4, 17, 18}
  • {–5, 0, 6, 21}
  • {27, 32, 37, 42}

Einige Sätze, die sind nicht Komplette Rückstandssysteme Modulo 4 sind:

  • {–5, 0, 6, 22}, da 6 bis 22 Modulo 4 übereinstimmt.
  • {5, 15}, da ein komplettes Rückstandssystemmodulo 4 genau 4 inkongruente Rückstände haben muss.

Reduzierte Rückstände

Angesichts der Eulers Totient -Funktion φ (n), jeder Satz von φ (n) Ganzzahlen, die sind relativ primär zu n und gegen Modul gegenseitig inkongruent n wird als a genannt Reduziertes Rückstandssystemmodulo n.[5] Der Satz {5,15} von oben ist beispielsweise eine Instanz eines reduzierten Rückstandssystemmodulos 4.

Ganzzahlen Modulo n

Der Satz von allen Kongruenzkurse der Ganzzahlen für einen Modul n wird genannt Ring of Ganzzahlen Modulo n,[6] und wird bezeichnet , , oder .[7] Die Notation wird jedoch nicht empfohlen, da es mit dem Satz von verwechselt werden kann n-Adic Ganzzahlen. Das Ring ist grundlegend für verschiedene Zweige der Mathematik (siehe § Anträge unter).

Der Satz ist definiert für n > 0 als:

(Wann n = 0, ist nicht ein leeres Set; Vielmehr ist es isomorph zu , seit a0 = {{a}.)

Wir definieren Addition, Subtraktion und Multiplikation auf Nach den folgenden Regeln:

Die Überprüfung, dass dies eine ordnungsgemäße Definition ist, verwendet die zuvor angegebenen Eigenschaften.

Auf diese Weise, wird zu einer Gewinnring. Zum Beispiel im Ring , wir haben

wie in der Arithmetik für die 24-Stunden-Uhr.

Wir verwenden die Notation Weil das das ist Quotientenring von bis zum Ideal , ein Satz, der alle Ganzzahlen enthält, die teilbar ist durch n, wo ist der Singleton -Set {0}. Daher ist ein aufstellen Wenn ist ein Maximales Ideal (d.h. wann n ist Prime).

Dies kann auch aus der Gruppe konstruiert werden Allein unter dem Addition Operation. Die Rückstandsklasse an ist die Gruppe Coset von a in dem Quotientsgruppe , a zyklische Gruppe.[8]

Anstatt den Sonderfall auszuschließen n = 0Es ist nützlicher, einzubeziehen (Was, wie bereits erwähnt, isomorph für den Ring ist von Ganzzahlen). Tatsächlich ist diese Aufnahme nützlich, wenn Sie die diskutieren charakteristisch von a Ring.

Der Ring der Ganzzahlen Modulo n ist ein endliches Feld dann und nur dann, wenn n ist Prime (Dies stellt sicher, dass jedes Element ungleich Null a hat multiplikativer Inverse). Wenn ist ein Primärleistung mit k > 1, es gibt ein einzigartiges (bis zum Isomorphismus) Finite -Feld mit n Elemente, aber das ist nicht , was kein Feld ist, weil es hat Null-Divisoren.

Das multiplikative Untergruppe von Ganzzahlen Modulo n wird bezeichnet durch . Dies besteht aus (wo a ist Coprime zu n), die genau die Klassen mit einem multiplikativen Inversen sind. Dies bildet einen kommutativen Gruppe unter Multiplikation mit Bestellung .

Anwendungen

In theoretischer Mathematik ist die modulare Arithmetik eine der Grundlagen von Zahlentheoriefast jeden Aspekt seiner Studie berühren und es wird auch in großem Umfang verwendet Gruppentheorie, Ringtheorie, Knotentheorie, und Zusammenfassung Algebra. In angewandter Mathematik wird es in verwendet Computeralgebra, Kryptographie, Informatik, Chemie und die visuell und Musical Künste.

Eine sehr praktische Anwendung ist die Berechnung der Prüfsummen innerhalb der Seriennummer -Kennungen. Zum Beispiel, Internationale Standardbuchnummer (ISBN) verwendet Modulo 11 (für 10 Ziffern ISBN) oder Modulo 10 (für 13 -stellige ISBN) Arithmetik zur Fehlererkennung. Ebenfalls, Internationale Bankkontonummern (IBANS) Verwenden Sie beispielsweise Modulo 97 Arithmetic, um Benutzereingabefehler in Bankkontonummern zu erkennen. In der Chemie die letzte Ziffer der CAS -Registrierungsnummer (Eine eindeutige Identifizierungszahl für jede chemische Verbindung) ist a Prüfziffer, die berechnet wird, indem die letzte Ziffer der ersten beiden Teile der CAS -Registrierungsnummernzeit 1, der vorherigen Zifferzeit 2, der vorherigen Zifferzeiten 3 usw., berechnet wird.

In der Kryptographie untermauert modulare Arithmetik direkt Öffentlicher Schlüssel Systeme wie RSA und Diffie -Hellmanund bietet endliche Felder das zugrunde liegt Elliptische Kurvenund wird in einer Vielzahl von verwendet Symmetrische Schlüsselalgorithmen einschließlich fortgeschrittener Verschlüsselungsstandard (AES), Internationaler Datenverschlüsselungsalgorithmus (Idee) und RC4. RSA- und Diffie -Hellman -Verwendung Modulare Exponentiation.

In Computeralgebra wird modulare Arithmetik üblicherweise verwendet, um die Größe der Ganzzahlkoeffizienten in Zwischenberechnungen und Daten zu begrenzen. Es wird in verwendet Polynomfaktorisierung, ein Problem, für das alle bekannten effizienten Algorithmen modulare Arithmetik verwenden. Es wird von den effizientesten Implementierungen von verwendet Polynom größter gemeinsamer Divisor, genau Lineare Algebra und Gröbner -Basis Algorithmen über die Ganzzahlen und die rationalen Zahlen. Wie veröffentlicht Fidonet in den 1980er Jahren und archiviert bei Rosetta -CodeDie modulare Arithmetik wurde verwendet, um zu widerlegen Eulers Befugnissumme Vermutung auf einen Sinclair Ql Mikrocomputer Verwenden Sie nur ein Viertel der von a verwendeten Ganzzahl-Präzision CDC 6600 Supercomputer zwei Jahrzehnte zuvor über a zu widerlegen Brute Force -Suche.[9]

In der Informatik wird häufig modulare Arithmetik angewendet Bitgewise Operations und andere Operationen mit fester Breite, zyklisch Datenstrukturen. Das Modulo -Betrieb, wie in vielen implementiert Programmiersprachen und Taschenrechner, ist eine Anwendung der modularen Arithmetik, die häufig in diesem Zusammenhang verwendet wird. Der logische Operator Xor Summen 2 Bits, Modulo 2.

In der Musik wird das Arithmetikmodulo 12 zur Berücksichtigung des Systems von verwendet zwölf Tones gleiches Temperament, wo Oktave und Enharmonic Äquivalenz tritt auf (dh Stellplätze in einem Verhältnis von 1: 2 oder 2: 1 sind gleichwertig und c-Scharf wird als dasselbe angesehen wie D-eben).

Die Methode von Nines ausstrecken Bietet eine kurze Überprüfung der von Hand durchgeführten dezimalen arithmetischen Berechnungen. Es basiert auf modularem arithmetischen Modulo 9 und speziell auf der entscheidenden Eigenschaft, dass 10 ≡ 1 (Mod 9).

Das arithmetische Modulo 7 wird in Algorithmen verwendet, die den Wochentag für ein bestimmtes Datum bestimmen. Im Speziellen, Zellers Kongruenz und die Doomsday -Algorithmus Nutzen Sie die Modulo-7-Arithmetik stark.

Allgemeiner hat die modulare Arithmetik auch Anwendung in Disziplinen wie z. Gesetz (z.B., Aufteilung), Wirtschaft (z.B., Spieltheorie) und andere Bereiche der Sozialwissenschaften, wo proportional Die Teilung und Zuordnung von Ressourcen spielt einen zentralen Teil der Analyse.

Rechenkomplexität

Da die modulare Arithmetik über eine so große Auswahl an Anwendungen verfügt, ist es wichtig zu wissen, wie schwierig es ist, ein System der Kongruenzen zu lösen. Ein lineares System der Kongruenzen kann gelöst werden Polynomzeit mit einer Form von Gaußsche Eliminierung, für Details siehe Linearkongruenz Theorem. Algorithmen, wie z. Montgomery Reduktionexistieren auch, um einfache arithmetische Operationen wie Multiplikation und zuzulassen Exponentiationsmodulon, effizient mit großen Zahlen durchgeführt werden.

Einige Operationen wie das Finden eines Diskreter Logarithmus oder ein Quadratische Kongruenz scheinen so schwer zu sein wie Ganzzahlfaktorisierung und sind daher ein Ausgangspunkt für Kryptografische Algorithmen und Verschlüsselung. Diese Probleme könnten sein NP-Intermediate.

Das Lösen eines Systems nichtlinearer modularer arithmetischer Gleichungen ist NP-Complete.[10]

Beispielimplementierungen

Im Folgenden sind drei einigermaßen schnelle C -Funktionen aufgeführt, zwei für die modulare Multiplikation und eine zur modularen Exponentiation von nicht signierten Ganzzahlen, die nicht größer als 63 Bit sind, ohne Überlauf der transienten Operationen.

Eine algorithmische Methode zum Berechnen :[11]

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {   wenn (!((a | b) & (0xffffffffffull << 32))) Rückkehr a * b % m;   uint64_t d = 0, MP2 = m >> 1;   int i;   wenn (a > = m) a %= m;   wenn (b > = m) b %= m;   zum (i = 0; i < 64; ++i) {   d = (d > MP2) ? (d << 1) - m : d << 1;   wenn (a & 0x80000000000000ull) d += b;   wenn (d > = m) d -= m;   a <<= 1;   }   Rückkehr d; } 

Auf Computerarchitekturen, wo ein erweiterte Präzision Format mit mindestens 64 Bit Mantissa ist verfügbar (wie die langes Doppel Art der meisten x86 C -Compiler), die folgende Routine ist[Klarstellung erforderlich], durch die Verwendung des Tricks, der durch Hardware, Schwimmpunkt Die Multiplikation führt zu den bedeutendsten Bits des Produkts, das aufbewahrt wird, während die ganzzahlige Multiplikation zu den am wenigsten signifikanten Bits führt:

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {   lang doppelt x;   uint64_t c;   INT64_T r;   wenn (a > = m) a %= m;   wenn (b > = m) b %= m;   x = a;   c = x * b / m;   r = (INT64_T) (a * b - c * m) % (INT64_T)m;   Rückkehr r < 0 ? r + m : r; } 

Im Folgenden finden Sie eine C -Funktion zur Durchführung modularer Exponentiation, die das verwendet mul_mod oben implementierte Funktion.

Eine algorithmische Methode zum Berechnen :

uint64_t pow_mod(uint64_t a, uint64_t b, uint64_t m) {   uint64_t r = m == 1 ? 0 : 1;   während (b > 0) {   wenn (b & 1) r = mul_mod(r, a, m);   b = b >> 1;   a = mul_mod(a, a, m);   }   Rückkehr r; } 

Für alle oberen Routinen zur Arbeit, jedoch, m darf 63 Bit nicht überschreiten.

Siehe auch

Anmerkungen

  1. ^ Sandor Lehoczky; Richard Rusczky. David Patrick (Hrsg.). Die Kunst der Problemlösung. Vol. 1 (7 ed.). p. 44. ISBN 0977304566.
  2. ^ Weisstein, Eric W. "Modulararithmetik". mathworld.wolfram.com. Abgerufen 2020-08-12.
  3. ^ Pettofrezzo & Byrkit (1970, p. 90)
  4. ^ Long (1972, p. 78)
  5. ^ Long (1972, p. 85)
  6. ^ Es ist ein Ring, Wie nachfolgend dargestellt.
  7. ^ "2.3: Ganzzahlen Modulo n". Mathematiklibretenexte. 2013-11-16. Abgerufen 2020-08-12.
  8. ^ Sengadir T., Diskrete Mathematik und Kombinatorik, p. 293, at Google Bücher
  9. ^ "Eulers Summe von Mächten Vermutung". Rosettacode.org. Abgerufen 2020-11-11.
  10. ^ Garey, M. R.; Johnson, D. S. (1979). Computer und Intaktabilität, ein Leitfaden zur Theorie der NP-Vervollständigung. W. H. Freeman. ISBN 0716710447.
  11. ^ Dieser Code verwendet die buchstäbliche Notation für nicht signierte lange hexadezimale Zahlen, die mit enden Ull. Siehe auch Abschnitt 6.4.4 der Sprachspezifikation N1570.

Verweise

Externe Links