Modulare multiplikative Inverse - Modular multiplicative inverse

In der Mathematik , insbesondere auf dem Gebiet der Zahlentheorie , ist eine modulare multiplikative Inverse einer ganzen Zahl a eine ganze Zahl x, so dass das Produkt ax in Bezug auf den Modul m zu 1 kongruent ist . In der Standardnotation der modularen Arithmetik wird diese Kongruenz geschrieben als

${\ displaystyle axe \ equiv 1 {\ pmod {m}},}$

Dies ist die Kurzform des Schreibens der Aussage, dass m die Menge ax - 1 (gleichmäßig) teilt , oder anders ausgedrückt, der Rest nach dem Teilen von ax durch die ganze Zahl m ist 1. Wenn a ein inverses Modulo m hat, gibt es ein unendlich viele Lösungen dieser Kongruenz, die in Bezug auf diesen Modul eine Kongruenzklasse bilden . Ferner , die eine beliebige ganze Zahl kongruent ist ein (dh in einem ‚Kongruenzklasse s) wird jedes Element von x ‘ s Kongruenzklasse als modulare multiplikative Inverse. Unter Verwendung der Notation von , um die Kongruenzklasse anzugeben, die w enthält , kann dies ausgedrückt werden, indem gesagt wird, dass die modulomultiplikative Inverse der Kongruenzklasse die Kongruenzklasse ist, so dass: ${\ displaystyle {\ overline {w}}}$${\ displaystyle {\ overline {a}}}$${\ displaystyle {\ overline {x}}}$

${\ displaystyle {\ overline {a}} \ cdot _ {m} {\ overline {x}} = {\ overline {1}},}$

wobei das Symbol die Multiplikation der Äquivalenzklassen modulo m bezeichnet . Auf diese Weise geschrieben ist die Analogie zum üblichen Konzept einer multiplikativen Inversen in der Menge der rationalen oder reellen Zahlen klar dargestellt, wobei die Zahlen durch Kongruenzklassen ersetzt und die binäre Operation entsprechend geändert werden. ${\ displaystyle \ cdot _ {m}}$

Wie bei der analogen Operation an den reellen Zahlen besteht eine grundlegende Verwendung dieser Operation darin, wenn möglich lineare Kongruenzen der Form zu lösen.

${\ displaystyle axe \ equiv b {\ pmod {m}}.}$

Das Finden modularer multiplikativer Inversen hat auch praktische Anwendungen auf dem Gebiet der Kryptographie , dh der Kryptographie mit öffentlichem Schlüssel und des RSA-Algorithmus. Ein Vorteil für die Computerimplementierung dieser Anwendungen besteht darin, dass es einen sehr schnellen Algorithmus gibt (den erweiterten euklidischen Algorithmus ), der zur Berechnung modularer multiplikativer Inversen verwendet werden kann.

Modulararithmetik

Für eine gegebene positive ganze Zahl m werden zwei ganze Zahlen a und b als kongruentes Modulo m bezeichnet, wenn m ihre Differenz teilt. Diese binäre Beziehung wird bezeichnet mit:

${\ displaystyle a \ equiv b {\ pmod {m}}.}$

Dies ist eine Äquivalenzbeziehung für die Menge der ganzen Zahlen ℤ , und die Äquivalenzklassen werden als Kongruenzklassen modulo m oder Restklassen modulo m bezeichnet . Lassen Sie die Kongruenz - Klasse bezeichnen die ganze Zahl enthält ein , dann ${\ displaystyle {\ overline {a}}}$

${\ displaystyle {\ overline {a}} = \ {b \ in \ mathbb {Z} \ mid a \ equiv b {\ pmod {m}} \}.}$

Eine lineare Kongruenz ist eine modulare Kongruenz der Form

${\ displaystyle axe \ equiv b {\ pmod {m}}.}$

Im Gegensatz zu linearen Gleichungen über den Realwerten können lineare Kongruenzen null, eine oder mehrere Lösungen haben. Wenn x eine Lösung einer linearen Kongruenz ist, dann ist jedes Element in auch eine Lösung. Wenn wir also von der Anzahl der Lösungen einer linearen Kongruenz sprechen, beziehen wir uns auf die Anzahl der verschiedenen Kongruenzklassen, die Lösungen enthalten. ${\ displaystyle {\ overline {x}}}$

Wenn d der größte gemeinsame Teiler von a und m ist, dann hat die lineare Kongruenz ax ≡ b (mod m ) genau dann Lösungen, wenn d b teilt . Wenn d b teilt , gibt es genau d Lösungen.

Eine modulare multiplikative Inverse einer ganzen Zahl a in Bezug auf den Modul m ist eine Lösung der linearen Kongruenz

${\ displaystyle axe \ equiv 1 {\ pmod {m}}.}$

Das vorherige Ergebnis besagt, dass eine Lösung genau dann existiert, wenn gcd ( a , m ) = 1 ist, dh a und m müssen relativ prim sein (dh Koprime). Wenn diese Bedingung erfüllt ist, gibt es außerdem genau eine Lösung, dh wenn sie existiert, ist eine modulare multiplikative Inverse eindeutig.

Wenn ax ≡ 1 (mod m ) eine Lösung hat, wird dies oft so bezeichnet -

${\ displaystyle x \ equiv a ^ {- 1} {\ pmod {m}},}$

Dies ist jedoch ein Missbrauch der Notation, da eine modulare multiplikative Inverse eine ganze Zahl ist und a ⁻¹ keine ganze Zahl ist, wenn a eine andere ganze Zahl als 1 oder ^-1 ist . Die Notation wäre richtig, wenn a als Token interpretiert wird, das für die steht Kongruenzklasse , da die multiplikative Umkehrung einer Kongruenzklasse eine Kongruenzklasse mit der im nächsten Abschnitt definierten Multiplikation ist. ${\ displaystyle {\ overline {a}}}$

Ganzzahlen modulo m

Die Kongruenzrelation modulo m unterteilt die Menge der ganzen Zahlen in m Kongruenzklassen. Additions- und Multiplikationsoperationen können für diese m Objekte folgendermaßen definiert werden: Um zwei Kongruenzklassen entweder zu addieren oder zu multiplizieren, wählen Sie zuerst einen Repräsentanten (auf irgendeine Weise) aus jeder Klasse aus und führen Sie dann die übliche Operation für ganze Zahlen für die beiden Repräsentanten aus und schließlich die Kongruenzklasse nehmen, in der das Ergebnis der ganzzahligen Operation als Ergebnis der Operation für die Kongruenzklassen liegt. In Symbolen mit und für die Operationen für Kongruenzklassen sind diese Definitionen ${\ displaystyle + _ {m}}$${\ displaystyle \ cdot _ {m}}$

${\ displaystyle {\ overline {a}} + _ {m} {\ overline {b}} = {\ overline {a + b}}}$

und

${\ displaystyle {\ overline {a}} \ cdot _ {m} {\ overline {b}} = {\ overline {ab}}.}$

Diese Operationen sind genau definiert , was bedeutet, dass das Endergebnis nicht von der Auswahl der Vertreter abhängt, die getroffen wurden, um das Ergebnis zu erhalten.

Die m- Kongruenzklassen mit diesen beiden definierten Operationen bilden einen Ring , der als Ring der ganzen Zahlen modulo m bezeichnet wird . Es werden verschiedene Notationen für diese algebraischen Objekte verwendet, meistens oder , aber einige elementare Texte und Anwendungsbereiche verwenden eine vereinfachte Notation, wenn eine Verwechslung mit anderen algebraischen Objekten unwahrscheinlich ist. ${\ displaystyle \ mathbb {Z} / m \ mathbb {Z}}$${\ displaystyle \ mathbb {Z} / m}$${\ displaystyle \ mathbb {Z} _ {m}}$

Die Kongruenzklassen der ganzen Zahlen modulo m waren traditionell als Restklassen modulo m bekannt , was die Tatsache widerspiegelt, dass alle Elemente einer Kongruenzklasse den gleichen Rest (dh "Rest") haben, wenn sie durch m geteilt werden . Jeder Satz von m ganzen Zahlen, die so ausgewählt sind, dass jede aus einer anderen Kongruenzklasse Modulo m stammt, wird als vollständiges System von Restmodulo m bezeichnet . Der Divisionsalgorithmus zeigt , dass die Menge der ganzen Zahlen, {0, 1, 2, ..., m - 1} ein vollständiges System von Rückständen bilden modulo m , bekannt als die am wenigsten Restsystem modulo m . Bei der Arbeit mit arithmetischen Problemen ist es manchmal bequemer, mit einem vollständigen System von Resten zu arbeiten und die Sprache der Kongruenzen zu verwenden, während zu anderen Zeiten der Standpunkt der Kongruenzklassen des Rings nützlicher ist. ${\ displaystyle \ mathbb {Z} / m \ mathbb {Z}}$

Multiplikative Gruppe von ganzen Zahlen modulo m

Nicht jedes Element eines vollständigen Restsystems modulo m hat eine modulare multiplikative Inverse, zum Beispiel Null nie. Nach dem Entfernen der Elemente eines vollständigen Restsystems, die nicht relativ prim zu m sind , wird das, was übrig bleibt, als reduziertes Restsystem bezeichnet , dessen Elemente alle modulare multiplikative Inversen aufweisen. Die Anzahl der Elemente in einem System mit reduzierten Resten ist , wobei die Euler-Totientenfunktion ist , dh die Anzahl der positiven ganzen Zahlen kleiner als m , die relativ prim zu m sind . ${\ displaystyle \ phi (m)}$${\ displaystyle \ phi}$

In einem allgemeinen Ring mit Einheit hat nicht jedes Element eine multiplikative Inverse, und diejenigen, die dies tun, werden Einheiten genannt . Da das Produkt zweier Einheiten eine Einheit ist, bilden die Einheiten eines Rings eine Gruppe , die Gruppe der Einheiten des Rings, und werden häufig mit R ^{× bezeichnet,} wenn R der Name des Rings ist. Die Einheitsgruppe des Ringes der ganzen Zahlen modulo m wird als multiplikative Gruppe der ganzen Zahlen modulo m bezeichnet und ist isomorph zu einem System mit reduzierten Resten. Insbesondere hat es Reihenfolge (Größe) , . ${\ displaystyle \ phi (m)}$

In dem Fall, dass m eine Primzahl ist , sagen wir p , dann ist und alle Nicht-Null-Elemente von multiplikative Inversen haben, ist also ein endliches Feld . In diesem Fall bildet die multiplikative Gruppe von ganzen Zahlen modulo p eine zyklische Gruppe der Ordnung p - 1 . ${\ displaystyle \ phi (p) = p-1}$${\ displaystyle \ mathbb {Z} / p \ mathbb {Z}}$${\ displaystyle \ mathbb {Z} / p \ mathbb {Z}}$

Beispiel

Um die obigen Definitionen zu veranschaulichen, betrachten Sie das folgende Beispiel unter Verwendung des Moduls 10.

Zwei ganze Zahlen sind genau dann kongruent mod 10, wenn ihre Differenz beispielsweise durch 10 teilbar ist

${\ displaystyle 32 \ equiv 12 {\ pmod {10}}}$ da 10 teilt 32 - 12 = 20 und

${\ displaystyle 111 \ equiv 1 {\ pmod {10}}}$ da 10 teilt 111 - 1 = 110.

Einige der zehn Kongruenzklassen in Bezug auf diesen Modul sind:

${\ displaystyle {\ overline {0}} = \ {\ cdots, -20, -10,0,10,20, \ cdots \}}$

${\ displaystyle {\ overline {1}} = \ {\ cdots, -19, -9,1,11,21, \ cdots \}}$

${\ displaystyle {\ overline {5}} = \ {\ cdots, -15, -5,5,15,25, \ cdots \}}$ und

${\ displaystyle {\ overline {9}} = \ {\ cdots, -11, -1,9,19,29, \ cdots \}.}$

Die lineare Kongruenz 4 x ≡ 5 (mod 10) hat keine Lösungen, da die zu 5 kongruenten ganzen Zahlen (dh die in ) alle ungerade sind, während 4 x immer gerade ist. Die lineare Kongruenz 4 x ≡ 6 (mod 10) hat jedoch zwei Lösungen, nämlich x = 4 und x = 9 . Der gcd (4, 10) = 2 und 2 teilt nicht 5, sondern 6. ${\ displaystyle {\ overline {5}}}$

Da gcd (3, 10) = 1 ist , hat die lineare Kongruenz 3 x ≡ 1 (mod 10) Lösungen, dh es existieren modulare multiplikative Inversen von 3 modulo 10. Tatsächlich erfüllt 7 diese Kongruenz (dh 21 - 1 = 20). Es erfüllen jedoch auch andere ganze Zahlen die Kongruenz, zum Beispiel 17 und –3 (dh 3 (17) - 1 = 50 und 3 (–3) - 1 = –10). Insbesondere wird jede ganze Zahl in die Kongruenz erfüllen, da diese ganzen Zahlen für einige ganze Zahlen r und die Form 7 + 10 r haben${\ displaystyle {\ overline {7}}}$

${\ displaystyle 3 (7 + 10r) -1 = 21 + 30r-1 = 20 + 30r = 10 (2 + 3r),}$

ist klar durch 10 teilbar. Diese Kongruenz hat nur diese eine Kongruenzklasse von Lösungen. Die Lösung in diesem Fall hätte durch Überprüfen aller möglichen Fälle erhalten werden können, aber für größere Module wären systematische Algorithmen erforderlich, die im nächsten Abschnitt angegeben werden.

Das Produkt von Kongruenzklassen und kann erhalten werden, indem ein Element von beispielsweise 25 und ein Element von beispielsweise –2 ausgewählt wird und beobachtet wird, dass ihr Produkt (25) (–2) = –50 in der Kongruenzklasse liegt . Also , . Die Addition wird auf ähnliche Weise definiert. Die zehn Kongruenzklassen bilden zusammen mit diesen Additions- und Multiplikationsoperationen der Kongruenzklassen den Ring der ganzen Zahlen Modulo 10, d . H. ${\ displaystyle {\ overline {5}}}$${\ displaystyle {\ overline {8}}}$${\ displaystyle {\ overline {5}}}$${\ displaystyle {\ overline {8}}}$${\ displaystyle {\ overline {0}}}$${\ displaystyle {\ overline {5}} \ cdot _ {10} {\ overline {8}} = {\ overline {0}}}$${\ displaystyle \ mathbb {Z} / 10 \ mathbb {Z}}$

Ein vollständiges Restsystem Modulo 10 kann die Menge {10, –9, 2, 13, 24, –15, 26, 37, 8, 9} sein, wobei sich jede ganze Zahl in einer anderen Kongruenzklasse Modulo 10 befindet. Das eindeutige System der kleinsten Reste Modulo 10 ist {0, 1, 2, ..., 9}. Ein reduziertes Rückstandssystem Modulo 10 könnte {1, 3, 7, 9} sein. Das Produkt von zwei beliebigen Kongruenzklassen, die durch diese Zahlen dargestellt werden, ist wiederum eine dieser vier Kongruenzklassen. Dies impliziert, dass diese vier Kongruenzklassen eine Gruppe bilden, in diesem Fall die zyklische Gruppe der Ordnung vier, die entweder 3 oder 7 als (multiplikativen) Generator hat. Die dargestellten Kongruenzklassen bilden die Gruppe der Einheiten des Rings . Diese Kongruenzklassen sind genau diejenigen, die modulare multiplikative Inversen haben. ${\ displaystyle \ mathbb {Z} / 10 \ mathbb {Z}}$

Berechnung

Erweiterter euklidischer Algorithmus

Ein modularer multiplikative Inverse von einem Modulo - m kann mit Hilfe des erweiterten euklidischen Algorithmus gefunden werden.

Der euklidische Algorithmus bestimmt den größten gemeinsamen Teiler (gcd) von zwei ganzen Zahlen, beispielsweise a und m . Wenn a ein multiplikatives inverses Modulo m hat , muss dieser gcd 1 sein. Die letzte von mehreren vom Algorithmus erzeugten Gleichungen kann für diesen gcd gelöst werden. Dann kann unter Verwendung einer Methode, die als "Rücksubstitution" bezeichnet wird, ein Ausdruck erhalten werden, der die ursprünglichen Parameter und diese gcd verbindet. Mit anderen Worten, es können ganze Zahlen x und y gefunden werden, um Bézouts Identität zu erfüllen .

${\ displaystyle axe + my = \ gcd (a, m) = 1.}$

Umgeschrieben, das ist

${\ displaystyle ax-1 = (- y) m,}$

das ist,

${\ displaystyle axe \ equiv 1 {\ pmod {m}},}$

Daher wurde eine modulare multiplikative Inverse von a berechnet. Eine effizientere Version des Algorithmus ist der erweiterte euklidische Algorithmus, der unter Verwendung von Hilfsgleichungen zwei Durchgänge durch den Algorithmus (Rücksubstitution kann als umgekehrter Durchlauf des Algorithmus angesehen werden) auf nur einen reduziert.

In der Big-O-Notation läuft dieser Algorithmus in der Zeit O (log ( m ) ² ) unter der Annahme von | a | < m und wird als sehr schnell und im Allgemeinen effizienter als seine alternative Exponentiation angesehen.

Mit dem Satz von Euler

Als Alternative zum erweiterten euklidischen Algorithmus kann der Satz von Euler verwendet werden, um modulare Inversen zu berechnen.

Nach dem Eulerschen Theorem , wenn a ist coprime bis m , das heißt, gcd ( a , m ) = 1 , dann

${\ displaystyle a ^ {\ phi (m)} \ equiv 1 {\ pmod {m}},}$

wo ist Eulersche Phi-Funktion . Dies ergibt sich aus der Tatsache , dass ein gehört zu der Multiplikationsgruppe ^{× ,} wenn und nur wenn eine ist coprime zu m . Daher kann eine modulare multiplikative Inverse direkt gefunden werden: ${\ displaystyle \ phi}$${\ displaystyle (\ mathbb {Z} / m \ mathbb {Z})}$

${\ displaystyle a ^ {\ phi (m) -1} \ equiv a ^ {- 1} {\ pmod {m}}.}$

In dem speziellen Fall, in dem m eine Primzahl ist und eine modulare Inverse gegeben ist durch ${\ displaystyle \ phi (m) = m-1}$

${\ displaystyle a ^ {- 1} \ equiv a ^ {m-2} {\ pmod {m}}.}$

Diese Methode ist im Allgemeinen langsamer als der erweiterte euklidische Algorithmus, wird jedoch manchmal verwendet, wenn bereits eine Implementierung für die modulare Exponentiation verfügbar ist. Einige Nachteile dieser Methode sind:

• Der Wert muss bekannt sein und die effizienteste bekannte Berechnung erfordert die Faktorisierung von m . Es wird allgemein angenommen, dass die Faktorisierung ein rechenintensives Problem ist. Die Berechnung ist jedoch einfach, wenn die Primfaktorisierung von m bekannt ist. ${\ displaystyle \ phi (m)}$${\ displaystyle \ phi (m)}$
• Die relativen Kosten der Potenzierung. Obwohl es durch modulare Exponentiation effizienter implementiert werden kann , wird dies bei großen Werten von m am effizientesten mit der Montgomery-Reduktionsmethode berechnet. Dieser Algorithmus selbst erfordert einen modularen inversen Mod m , der zunächst berechnet werden sollte. Ohne die Montgomery-Methode ist die standardmäßige binäre Exponentiation , die bei jedem Schritt eine Teilung mod m erfordert , eine langsame Operation, wenn m groß ist.

Ein bemerkenswerter Vorteil dieser Technik besteht darin, dass es keine bedingten Verzweigungen gibt, die vom Wert von a abhängen , und daher kann der Wert von a , der ein wichtiges Geheimnis in der Kryptographie mit öffentlichen Schlüsseln sein kann, vor Seitenkanalangriffen geschützt werden . Aus diesem Grund verwendet die Standardimplementierung von Curve25519 diese Technik, um eine Inverse zu berechnen.

Mehrere Umkehrungen

Es ist möglich, die Umkehrung mehrerer Zahlen a _i , modulo a common m mit einem einzigen Aufruf des euklidischen Algorithmus und drei Multiplikationen pro zusätzlicher Eingabe zu berechnen. Die Grundidee besteht darin, das Produkt aller a _{i zu bilden} , diese umzukehren und dann mit a _j für alle j ≠ i zu multiplizieren , um nur das gewünschte a zu belassen ⁻¹
_i .

Insbesondere ist der Algorithmus (alle arithmetisch durchgeführten Moduleo m ):

1. Berechnen Sie die Präfixprodukte für alle i ≤ n . ${\ textstyle b_ {i} = \ prod _ {j = 1} ^ {i} a_ {j} = a_ {i} b_ {i-1}}$
2. Berechnen Sie b ⁻¹
   _n unter Verwendung eines beliebigen verfügbaren Algorithmus.
3. Berechnen Sie für i von n bis 2
   • ein ⁻¹
     _i = b ⁻¹
     _i b _{i −1} und
   • b ⁻¹
     _{i −1} = b ⁻¹
     _i a _i .
4. Schließlich a ⁻¹
   ₁ = b ⁻¹
   ₁ .

Es ist möglich, die Multiplikationen in einer Baumstruktur anstatt linear durchzuführen, um paralleles Rechnen auszunutzen .

Anwendungen

Das Finden einer modularen multiplikativen Inversen hat viele Anwendungen in Algorithmen, die auf der Theorie der modularen Arithmetik beruhen. Beispielsweise ermöglicht die Verwendung der modularen Arithmetik in der Kryptographie, dass einige Operationen schneller und mit weniger Speicheranforderungen ausgeführt werden, während andere Operationen schwieriger werden. Beide Funktionen können vorteilhaft genutzt werden. Insbesondere wird beim RSA-Algorithmus das Ver- und Entschlüsseln einer Nachricht unter Verwendung eines Zahlenpaars durchgeführt, das multiplikative Inversen in Bezug auf einen sorgfältig ausgewählten Modul ist. Eine dieser Nummern wird veröffentlicht und kann in einem schnellen Verschlüsselungsverfahren verwendet werden, während die andere, die in dem Entschlüsselungsverfahren verwendet wird, verborgen bleibt. Das Ermitteln der versteckten Nummer aus der öffentlichen Nummer wird als rechnerisch nicht durchführbar angesehen. Aus diesem Grund arbeitet das System, um die Privatsphäre zu gewährleisten.

Betrachten Sie als weiteres Beispiel in einem anderen Kontext das genaue Teilungsproblem in der Informatik, bei dem Sie eine Liste ungerader wortgroßer Zahlen haben, die jeweils durch k teilbar sind, und Sie alle durch k teilen möchten . Eine Lösung lautet wie folgt:

1. Verwenden Sie den erweiterten euklidischen Algorithmus, um k ⁻¹ zu berechnen , die modulare multiplikative Inverse von k mod 2 ^w , wobei w die Anzahl der Bits in einem Wort ist. Diese Umkehrung wird existieren, da die Zahlen ungerade sind und der Modul keine ungeraden Faktoren hat.
2. Multiplizieren Sie für jede Zahl in der Liste diese mit k ⁻¹ und nehmen Sie das niedrigstwertige Wort des Ergebnisses.

Auf vielen Maschinen, insbesondere solchen ohne Hardware-Unterstützung für die Division, ist die Division langsamer als die Multiplikation, so dass dieser Ansatz zu einer erheblichen Beschleunigung führen kann. Der erste Schritt ist relativ langsam, muss aber nur einmal durchgeführt werden.

Modulare multiplikative Inversen werden verwendet, um eine Lösung eines linearen Kongruenzsystems zu erhalten, das durch den chinesischen Restsatz garantiert wird .

Zum Beispiel das System

X ≡ 4 (mod 5)

X ≡ 4 (mod 7)

X ≤ 6 (mod 11)

hat gemeinsame Lösungen, da 5,7 und 11 paarweise Koprime sind . Eine Lösung ist gegeben durch

X = t ₁ (7 × 11) × 4 + t ₂ (5 × 11) × 4 + t ₃ (5 × 7) × 6

wo

t ₁ = 3 ist die modulare multiplikative Inverse von 7 × 11 (mod 5),

t ₂ = 6 ist die modulare multiplikative Inverse von 5 × 11 (mod 7) und

t ₃ = 6 ist die modulare multiplikative Inverse von 5 × 7 (mod 11).

So,

X = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504

und in seiner einzigartigen reduzierten Form

X ≤ 3504 ≤ 39 (mod 385)

seit 385 ist das LCM von 5,7 und 11.

Auch die modularen multiplikativen inversen Zahlen spielen bei der Definition der Kloosterman-Summe eine herausragende Rolle .

Siehe auch

• Inversiver Kongruenzgenerator - Ein Pseudozufallszahlengenerator, der modulare multiplikative Inversen verwendet
• Rationale Rekonstruktion (Mathematik)

Anmerkungen

Verweise

• Irland, Kenneth; Rosen, Michael (1990), Eine klassische Einführung in die moderne Zahlentheorie (2. Aufl.), Springer-Verlag, ISBN   0-387-97329-X
• Rosen, Kenneth H. (1993), Elementare Zahlentheorie und ihre Anwendungen (3. Aufl.), Addison-Wesley, ISBN   978-0-201-57889-8
• Schumacher, Carol (1996). Kapitel Null: Grundbegriffe der abstrakten Mathematik . Addison-Wesley. ISBN   0-201-82653-4 .
• Trappe, Wade; Washington, Lawrence C. (2006), Einführung in die Kryptographie mit Codierungstheorie (2. Aufl.), Prentice-Hall, ISBN   978-0-13-186239-5

Externe Links

• Weisstein, Eric W. "Modular Inverse" . MathWorld .
• Guevara Vasquez, Fernando, liefert ein gelöstes Beispiel für die Lösung der multiplikativen Modulo-Inverse unter Verwendung des Euklid-Algorithmus