Modulares multiplikatives Inverses

In der Mathematik , insbesondere im Bereich der Arithmetik , ist das modulare multiplikative Inverse einer ganzen Zahl a eine ganze Zahl x, sodass das Produkt ax bezüglich des Moduls m zu 1 kongruent ist . ^{[ 1 ]} In der Standardnotation der modularen Arithmetik wird diese Kongruenz wie folgt geschrieben:

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

Dies ist die Kurzform für die Aussage, dass m die Zahl ax − 1 (ohne Rest) teilt , oder anders ausgedrückt: Der Rest nach der Division von ax durch die ganze Zahl m ist 1. Besitzt a ein Inverses modulo m , so gibt es unendlich viele Lösungen dieser Kongruenz, die bezüglich dieses Moduls eine Kongruenzklasse bilden. Darüber hinaus besitzt jede ganze Zahl, die zu a kongruent ist (d. h. in der Kongruenzklasse von a liegt), jedes Element der Kongruenzklasse von x als modulares multiplikatives Inverses. Verwendet man die Notation , um die Kongruenzklasse zu bezeichnen, die w enthält , so lässt sich dies ausdrücken, indem man sagt, dass das modulo multiplikative Inverse der Kongruenzklasse diejenige Kongruenzklasse ist, für die gilt: ${\displaystyle {\overline {w}}}$${\displaystyle {\overline {a}}}$${\displaystyle {\overline {x}}}$

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

wobei das Symbol die Multiplikation von Äquivalenzklassen modulo m bezeichnet . ^{[ 2 ]} Auf diese Weise geschrieben, wird die Analogie zum üblichen Konzept eines multiplikativen Inversen in der Menge der rationalen oder reellen Zahlen deutlich dargestellt, indem die Zahlen durch Kongruenzklassen ersetzt und die binäre Operation entsprechend angepasst wird. ${\displaystyle \cdot }$

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

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

Die Bestimmung modularer multiplikativer Inversen findet auch praktische Anwendungen im Bereich der Kryptographie , z. B. in der Public-Key-Kryptographie und beim RSA-Algorithmus . ^{[ 3 ] [ 4 ] [ 5 ]} Ein Vorteil für die computergestützte Implementierung dieser Anwendungen besteht darin, dass ein sehr schneller Algorithmus (der erweiterte euklidische Algorithmus ) existiert , der zur Berechnung modularer multiplikativer Inversen verwendet werden kann.

Für eine gegebene positive ganze Zahl m heißen zwei ganze Zahlen a und b kongruent modulo m, wenn m ihre Differenz teilt. Diese binäre Relation wird mit bezeichnet.

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

Dies ist eine Äquivalenzrelation auf der Menge der ganzen Zahlen, und die Äquivalenzklassen werden Kongruenzklassen modulo m oder Restklassen modulo m genannt . Sei die Kongruenzklasse, die die ganze Zahl a enthält , ^{[ 6 ]} dann ${\displaystyle \mathbb {Z} }$${\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 ax\equiv b{\pmod {m}}.}$

Anders als lineare Gleichungen über den reellen Zahlen 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 x ebenfalls eine Lösung. Spricht man also von der Anzahl der Lösungen einer linearen Kongruenz, meint man die Anzahl der verschiedenen Kongruenzklassen, die Lösungen enthalten. ${\displaystyle {\overline {x}}}$

Ist d der größte gemeinsame Teiler von a und m, so besitzt die lineare Kongruenz ax ≡ b (mod m ) genau dann Lösungen, wenn d ein Teiler von b ist . Ist d ein Teiler von b , so gibt es genau d Lösungen. ^{[ 7 ]}

Das modulare multiplikative Inverse einer ganzen Zahl a bezüglich des Moduls m ist eine Lösung der linearen Kongruenz.

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

Das vorherige Ergebnis besagt, dass eine Lösung genau dann existiert, wenn ggT( a , m ) = 1 , d. h. a und m teilerfremd sein müssen . Wenn diese Bedingung erfüllt ist, existiert genau eine Lösung; das heißt, wenn sie existiert, ist das modulare multiplikative Inverse eindeutig: ^{[ 8 ]} Sind b und b' modulare multiplikative Inverse von a bezüglich des Moduls m , dann

${\displaystyle ab\equiv ab'\equiv 1{\pmod {m}},}$

daher

${\displaystyle a(bb')\equiv 0{\pmod {m}}.}$

Wenn a ≡ 0 (mod m ) , dann ist ggT( a , m ) = m , und a hat nicht einmal ein modulares multiplikatives Inverses. Daher ist b ≡ b' (mod m ) .

Wenn ax ≡ 1 (mod m ) eine Lösung besitzt, wird diese oft folgendermaßen bezeichnet:

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

Dies kann jedoch als missbräuchliche Notation angesehen werden , da es als Kehrwert von (der, im Gegensatz zum modularen multiplikativen Inversen, keine ganze Zahl ist, außer wenn a gleich 1 oder −1 ist) fehlinterpretiert werden könnte. Die Notation wäre korrekt, wenn a als Symbol für die Kongruenzklasse interpretiert würde , da das multiplikative Inverse einer Kongruenzklasse eine Kongruenzklasse mit der im nächsten Abschnitt definierten Multiplikation ist. ${\displaystyle a}$${\displaystyle {\overline {a}}}$

Die Kongruenzrelation modulo m unterteilt die Menge der ganzen Zahlen in m Kongruenzklassen. Addition und Multiplikation lassen sich auf diesen m Objekten folgendermaßen definieren: Um zwei Kongruenzklassen zu addieren oder zu multiplizieren, wählt man zunächst aus jeder Klasse einen Repräsentanten (beliebig), führt dann die übliche Operation für ganze Zahlen auf den beiden Repräsentanten durch und nimmt schließlich die Kongruenzklasse, in der das Ergebnis der Ganzzahloperation liegt, als Ergebnis der Operation auf den Kongruenzklassen. Symbolisch lauten diese Definitionen:

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

Und

${\displaystyle {\overline {a}}\cdot {\overline {b}}={\overline {ab}},}$

Dabei bezeichnen und auf der linken Seite die Addition und Multiplikation von Kongruenzklassen modulo m . Diese Operationen sind wohldefiniert , was bedeutet, dass das Endergebnis nicht von der Wahl der Repräsentanten abhängt, die zur Erzielung des Ergebnisses getroffen wurden. ${\displaystyle +}$${\displaystyle \,\!\cdot }$

Die m Kongruenzklassen mit diesen beiden definierten Operationen bilden einen kommutativen Ring , den sogenannten Ring der ganzen Zahlen modulo m . Für diese algebraischen Objekte werden verschiedene Notationen verwendet, am häufigsten oder , aber in einigen Lehrbüchern und Anwendungsgebieten wird eine vereinfachte Notation verwendet, 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 wurden traditionell als Restklassen modulo m bezeichnet , da alle Elemente einer Kongruenzklasse bei Division durch m denselben Rest (d. h. „Rest“) ergeben . Jede Menge von m ganzen Zahlen, die so gewählt sind, dass jede Zahl aus einer anderen Kongruenzklasse modulo m stammt, wird als vollständiges Restsystem modulo m bezeichnet . ^{[ 9 ]} Der Divisionsalgorithmus zeigt, dass die Menge der ganzen Zahlen {0, 1, 2, ..., m − 1} ein vollständiges Restsystem modulo m bildet , das als kleinstes Restsystem modulo m bekannt ist . Bei arithmetischen Problemen ist es manchmal praktischer, mit einem vollständigen Restsystem zu arbeiten und die Sprache der Kongruenzen zu verwenden, während in anderen Fällen die Betrachtungsweise der Kongruenzklassen des Rings nützlicher ist. ^{[ 10 ]}${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

Nicht jedes Element eines vollständigen Restklassensystems modulo m besitzt ein modulares multiplikatives Inverses; beispielsweise besitzt Null keins, wenn m > 1. Entfernt man die Elemente eines vollständigen Restklassensystems, die nicht teilerfremd zu m sind , so erhält man ein reduziertes Restklassensystem , dessen Elemente alle modulare multiplikative Inverse besitzen. Die Anzahl der Elemente in einem reduzierten Restklassensystem ist , wobei die Eulersche Phi-Funktion ist , d. h. die Anzahl der positiven ganzen Zahlen kleiner als m , die teilerfremd zu m sind . ${\displaystyle \phi (m)}$${\displaystyle \phi }$

In einem allgemeinen Ring mit Einselement besitzt nicht jedes Element ein multiplikatives Inverses ; diejenigen, die ein multiplikatives Inverses besitzen, werden als Einheiten bezeichnet . Da das Produkt zweier Einheiten wieder eine Einheit ist, bilden die Einheiten eines Rings eine Gruppe , die Einheitengruppe des Rings , die oft mit R ^× bezeichnet wird, wenn R der Name des Rings ist. Die Einheitengruppe des Rings der ganzen Zahlen modulo m wird als multiplikative Gruppe der ganzen Zahlen modulo m bezeichnet und ist isomorph zu einem reduzierten Restklassensystem. Insbesondere hat sie die Ordnung (Größe) m ≥ 1 . ${\displaystyle \phi (m)}$

Ist m eine Primzahl , etwa p , dann besitzen alle von Null verschiedenen Elemente von ein multiplikatives Inverses, und somit ist ein endlicher Körper . In diesem Fall bildet die multiplikative Gruppe der 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} }$

Für jede ganze Zahl n ist stets n das modulare multiplikative Inverse von n bezüglich des Moduls n , da n = n . Beispiele hierfür sind n = n, n = n, usw. ${\displaystyle n>1}$${\displaystyle n^{2}-n+1}$${\displaystyle n+1}$${\displaystyle n^{2}}$${\displaystyle (n+1)(n^{2}-n+1)=n^{3}+1}$${\displaystyle 3\times 3\equiv 1{\pmod {4}}}$${\displaystyle 4\times 7\equiv 1{\pmod {9}}}$${\displaystyle 5\times 13\equiv 1{\pmod {16}}}$

Das folgende Beispiel verwendet den Modulo 10: Zwei ganze Zahlen sind genau dann kongruent modulo 10, wenn ihre Differenz durch 10 teilbar ist, zum Beispiel

${\displaystyle 32\equiv 2{\pmod {10}}}$da 10 ein Teiler von 32 − 2 = 30 ist, und

${\displaystyle 111\equiv 1{\pmod {10}}}$da 10 ein Teiler von 111 − 1 = 110 ist.

Einige der zehn Kongruenzklassen bezüglich dieses Moduls 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 4x ≡ 5 (mod 10) hat keine Lösung , da alle zu 5 kongruenten Zahlen ungerade sind, während 4x immer gerade ist. Die lineare Kongruenz 4x ≡ 6 (mod 10) hingegen hat zwei Lösungen, nämlich x = 4 und x = 9. Der größte gemeinsame Teiler (ggT) von 4 und 10 ist 2, und 2 ist kein Teiler von 5, aber ein Teiler von 6. ${\displaystyle {\overline {5}}}$

Da ggT(3, 10) = 1 ist , besitzt die lineare Kongruenz 3x ≡ 1 (mod 10) Lösungen, d. h. es existieren modulare multiplikative Inverse von 3 modulo 10. Tatsächlich erfüllt 7 diese Kongruenz (d. h. 21 − 1 = 20). Allerdings erfüllen auch andere ganze Zahlen die Kongruenz, beispielsweise 17 und −3 (d. h. 3(17) − 1 = 50 und 3(−3) − 1 = −10). Insbesondere erfüllt jede ganze Zahl in ℝ die Kongruenz, da diese ganzen Zahlen die Form 7 + 10r für eine ganze Zahl r haben . ${\displaystyle {\overline {7}}}$

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

ist durch 10 teilbar. Diese Kongruenz besitzt nur diese eine Lösungsklasse. Die Lösung hätte in diesem Fall durch Überprüfung aller möglichen Fälle gefunden werden können, jedoch sind für größere Moduli systematische Algorithmen erforderlich, die im nächsten Abschnitt vorgestellt werden.

Das Produkt von Kongruenzklassen kann man erhalten, indem man ein Element von , beispielsweise 25, und ein Element von , beispielsweise −2, wählt und feststellt, dass ihr Produkt (25)(−2) = −50 in der Kongruenzklasse liegt . Somit gilt . Die Addition ist analog definiert. Die zehn Kongruenzklassen bilden zusammen mit diesen Operationen der Addition und Multiplikation von 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 {\overline {8}}={\overline {0}}}$${\displaystyle \mathbb {Z} /10\mathbb {Z} }$

Ein vollständiges Restklassensystem modulo 10 ist die Menge {10, −9, 2, 13, 24, −15, 26, 37, 8, 9}, wobei jede ganze Zahl zu einer anderen Kongruenzklasse modulo 10 gehört. Das eindeutige kleinste Restklassensystem modulo 10 ist {0, 1, 2, ..., 9}. Ein reduziertes Restklassensystem modulo 10 könnte {1, 3, 7, 9} sein. Das Produkt je zweier durch diese Zahlen repräsentierter Kongruenzklassen ist wiederum eine dieser vier Kongruenzklassen. Daraus folgt, dass diese vier Kongruenzklassen eine Gruppe bilden, in diesem Fall die zyklische Gruppe der Ordnung vier, deren (multiplikativer) Erzeuger entweder 3 oder 7 ist. Die repräsentierten Kongruenzklassen bilden die Einheitengruppe des Rings . Genau diese Kongruenzklassen besitzen modulare multiplikative Inverse. ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$

Das modulare multiplikative Inverse von a modulo m kann mithilfe des erweiterten euklidischen Algorithmus gefunden werden.

Der euklidische Algorithmus bestimmt den größten gemeinsamen Teiler (ggT) zweier ganzer Zahlen, etwa a und m . Besitzt a ein multiplikatives Inverses modulo m , so ist dieser ggT gleich 1. Die letzte der vom Algorithmus erzeugten Gleichungen kann nach diesem ggT aufgelöst werden. Anschließend lässt sich mithilfe der sogenannten Rückwärtssubstitution ein Ausdruck finden, der die ursprünglichen Parameter mit diesem ggT verknüpft. Anders ausgedrückt: Es können ganze Zahlen x und y gefunden werden, die die Bézout-Identität erfüllen .

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

Neu geschrieben lautet das:

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

das heißt,

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

Es wurde also das modulare multiplikative Inverse von a berechnet. Eine effizientere Version des Algorithmus ist der erweiterte euklidische Algorithmus, der durch die Verwendung von Hilfsgleichungen zwei Durchläufe des Algorithmus (die Rücksubstitution kann als umgekehrter Durchlauf des Algorithmus betrachtet werden) auf nur einen reduziert. In der O-Notation hat dieser Algorithmus eine Laufzeit von O(log₂ ⁽ m ) ) , vorausgesetzt | a | < m , und gilt als sehr schnell und im Allgemeinen effizienter als die Alternative, die Exponentiation.

Beispielsweise ist das modulare multiplikative Inverse von bezüglich des Moduls , aber auch , d. h. im Ring ist die Restklasse mit dem Inversen invertierbar .${\displaystyle a=15}$${\displaystyle m=34}$${\displaystyle -9}$${\displaystyle -9+34=25,}$${\displaystyle \mathbb {Z} /34\mathbb {Z} ,}$${\displaystyle {\overline {15}}}$

${\displaystyle {\overline {15}}^{\!\ -1}={\overline {-9}}={\overline {25}}.}$

Weil

${\displaystyle g=\mathrm {gcd} (m,a)=1=4m-9a,}$

Gemäß der nebenstehenden Berechnung. Im ersten Schritt, der der euklidischen Division entspricht , wird die Gleichung mit dem Produkt aus Gleichung und addiert , was zu führt. Sobald links ein Rest auftritt, steht darüber (oder allgemein, wenn auch negative Reste zulässig sind). In der zugehörigen Tabelle ganz rechts mit den analogen Zeilenoperationen könnte man die -Spalte scheinbar weglassen. Schließlich lässt sich direkt überprüfen: ${\displaystyle \;\!34\div 15}$${\displaystyle 2}$${\displaystyle 4\!\ }$${\displaystyle -2}$${\displaystyle 15=0m+1a}$${\displaystyle 34=1m+0a}$${\displaystyle 4=1m-2a.}$${\displaystyle 0,}$${\displaystyle g}$${\displaystyle \pm g}$${\displaystyle m}$${\displaystyle {\overline {15}}{}^{\!\ -1}={\overline {-9}}}$

${\displaystyle {\overline {15}}\cdot {\overline {-9}}={\overline {-135}}={\overline {-135+4\cdot 34}}={\overline {1}}}$

In${\displaystyle \mathbb {Z} /34\mathbb {Z} .}$

Alternativ zum erweiterten euklidischen Algorithmus kann der Satz von Euler zur Berechnung modularer Inversen verwendet werden. ^{[ 11 ]}

Nach dem Satz von Euler gilt : Wenn a teilerfremd zu m ist , d. h. ggT( a , m ) = 1 , dann

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

wobei die Eulersche Phi-Funktion ist . Dies folgt aus der Tatsache, dass a genau dann zur multiplikativen Gruppe ^{× gehört} , wenn a teilerfremd zu m ist . Daher kann ein modulares multiplikatives Inverses direkt gefunden werden: ${\displaystyle \phi }$${\displaystyle (\mathbb {Z} /m\mathbb {Z} )}$

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

Im Spezialfall, dass m eine Primzahl ist, und ein modulares Inverses 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 aber mitunter verwendet, wenn bereits eine Implementierung für die modulare Exponentiation verfügbar ist. Zu den Nachteilen dieser Methode gehören:

• Der Wert muss bekannt sein, und die effizienteste bekannte Berechnung erfordert die Primfaktorzerlegung von m . Die Primfaktorzerlegung gilt allgemein als rechenaufwändiges Problem. Die Berechnung ist jedoch unkompliziert, wenn die Primfaktorzerlegung von m bekannt ist.${\displaystyle \phi (m)}$${\displaystyle \phi (m)}$
• Die relativen Kosten der Exponentiation. Obwohl sie mithilfe der modularen Exponentiation effizienter implementiert werden kann , ist die Berechnung bei großen Werten von m mit der Montgomery-Reduktionsmethode am effizientesten . Diese Methode selbst benötigt eine modulare Inverse modulo m , die ursprünglich berechnet werden sollte. Ohne die Montgomery-Methode ist die standardmäßige binäre Exponentiation , die in jedem Schritt eine Division modulo m erfordert, bei großen m eine langsame Operation .

Ein wesentlicher Vorteil dieser Technik besteht darin, dass keine bedingten Verzweigungen vom Wert von a abhängen . Dadurch kann der Wert von a , der in der Public-Key-Kryptographie ein wichtiges Geheimnis darstellen kann , vor Seitenkanalangriffen geschützt werden . Aus diesem Grund verwendet die Standardimplementierung von Curve25519 diese Technik zur Berechnung der Inversen.

Es ist möglich, die Inversen mehrerer Zahlen a _{_i} modulo eines gemeinsamen m mit einem einzigen Aufruf des euklidischen Algorithmus und drei Multiplikationen pro zusätzlicher Eingabe zu berechnen. ^{[ 12 ]} Die Grundidee besteht darin, das Produkt aller a_i zu bilden , _dieses zu invertieren und anschließend mit a _{_j} für alle j ≠ i zu multiplizieren, um nur die gewünschten a _i zu erhalten.⁻¹ _iDie

Genauer gesagt lautet der Algorithmus (alle arithmetischen Operationen werden modulo m durchgeführt ):

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

Es ist möglich, die Multiplikationen in einer Baumstruktur anstatt linear durchzuführen, um die Vorteile des parallelen Rechnens auszunutzen .

Falls der Modul M die Form für eine Primzahl p und eine positive ganze Zahl m hat , lassen sich modulare multiplikative Inverse effizient mit dem Newton-Raphson-Verfahren berechnen, wodurch die Inverse durch Multiplikationen ermittelt werden kann. Es lässt sich zeigen, dass, wenn ${\displaystyle p^{m}}$${\displaystyle O(\log m)}$

${\displaystyle ax\equiv 1{\pmod {p^{k}}}}$

(das heißt, x ist ein modulares multiplikatives Inverses von a modulo einer Primzahlpotenz ), dann ${\displaystyle p^{k}}$

${\displaystyle ax\left(2-ax\right)\equiv 1{\pmod {p^{2k}}}}$

Dies bedeutet, dass eine modulare Inverse berechnet werden kann, indem man zunächst das modulare multiplikative Inverse von a modulo der Primzahl p oder einer kleinen Potenz davon berechnet und anschließend eine Reihe von Newton-Raphson-Iterationen durchführt, um die Inverse modulo immer größeren Primzahlpotenzen für immer größere Werte von n zu berechnen . ^{[ 13 ] [ 14 ]}${\displaystyle p^{2^{n}*k}}$

Eine praktische Anwendung dieser Methode ist die effiziente Berechnung modularer multiplikativer Inversen modulo Zweierpotenzen. Für eine solche Berechnung könnte man damit beginnen, festzustellen, dass alle ungeraden ganzen Zahlen ihre eigenen modularen multiplikativen Inversen modulo Zweierpotenzen sind , wie man durch Inspektion zeigen kann: ${\displaystyle 2^{3}}$

${\displaystyle 1*1=1\equiv 1{\pmod {8}}}$, , , , ${\displaystyle 3*3=9\equiv 1{\pmod {8}}}$${\displaystyle 5*5=25\equiv 1{\pmod {8}}}$${\displaystyle 7*7=49\equiv 1{\pmod {8}}}$

und dann iterativ Newton-Raphson-Iterationen verwenden, um die modulare Inverse modulo , , und so weiter zu berechnen. ${\displaystyle 2^{6}}$${\displaystyle 2^{12}}$${\displaystyle 2^{24}}$

In der Programmiersprache C , wo Additionen, Subtraktionen und Multiplikationen des uint64_tDatentyps alle modulo n durchgeführt werden , könnte man beispielsweise das modulare multiplikative Inverse einer ungeraden ganzen Zahl a modulo n mit der folgenden Funktion berechnen, die fünf Newton-Raphson-Iterationen durchführt: ${\displaystyle 2^{64}}$${\displaystyle 2^{64}}$

#include <stdint.h> uint64_t modinv64 ( uint64_t a ) { uint64_t x = a ; for ( int i = 0 ; i < 5 ; i ++ ) x *= 2 - a * x ; return x ; }

Je nach Anwendung und Plattform kann es sinnvoll sein, diese Routine weiter zu optimieren – beispielsweise können die ersten Iterationen übersprungen werden, indem eine Nachschlagetabelle verwendet wird , um das Inverse modulo einer größeren Zweierpotenz zu ermitteln. Auf manchen Systemen sind 32-Bit-Multiplikationen zudem schneller als 64-Bit-Multiplikationen. In diesem Fall lässt sich eine Beschleunigung erzielen, indem man zunächst nur 32-Bit-Multiplikationen durchführt, bis das Inverse modulo berechnet wurde, und erst danach auf 64-Bit-Multiplikationen umschaltet. Mit solchen Optimierungen ergibt sich für eine C-Routine, die das modulare multiplikative Inverse modulo berechnet, folgender Code : ${\displaystyle 2^{32}}$${\displaystyle 2^{64}}$

#include <stdint.h> uint64_t modinv64 ( uint64_t a ) { static const uint8_t tbl [ 256 ] = { 0 , 1 , 0 , 171 , 0 , 205 , 0 , 183 , 0 , 57 , 0 , 163 , 0 , 197 , 0 , 239 , 0 , 241 , 0 , 27 , 0 , 61 , 0 , 167 , 0 , 41 , 0 , 19 , 0 , 53 , 0 , 223 , 0 , 225 , 0 , 139 , 0 , 173 , 0 , 151 , 0 , 25 , 0 , 131 , 0 , 165 , 0 , 207 , 0 , 209 , 0 , 251 , 0 , 29 , 0 , 135 , 0 , 9 , 0 , 243 , 0 , 21 , 0 , 191 , 0 , 193 , 0 , 107 , 0 , 141 , 0 , 119 , 0 , 249 , 0 , 99 , 0 , 133 , 0 , 175 , 0 , 177 , 0 , 219 , 0 , 253 , 0 , 103 , 0 , 233 , 0 , 211 , 0 ,245 , 0 , 159 , 0 , 161 , 0 , 75 , 0 , 109 , 0 , 87 , 0 , 217 , 0 , 67 , 0 , 101 , 0 , 143 , 0 , 145 , 0 , 187 , 0 , 221 , 0 , 71 , 0 , 201 , 0 , 179 , 0 , 213 , 0 , 127 , 0 , 129 , 0 , 43 , 0 , 77 , 0 , 55 , 0 , 185 , 0 , 35 , 0 , 69 , 0 , 111 , 0 , 113 , 0 , 155 , 0 , 189 , 0 , 39 , 0 , 169 , 0 , 147 , 0 , 181 , 0 , 95 , 0 , 97 , 0 , 11 , 0 , 45 , 0 , 23 , 0 , 153 , 0 , 3 , 0 , 37 , 0 , 79 , 0 , 81 , 0 , 123 , 0 , 157 , 0 , 7 , 0 , 137 , 0 , 115 , 0 , 149 , 0 , 63 , 0 , 65 , 0 , 235 , 0 ,13 , 0 , 247 , 0 , 121 , 0 , 227 , 0 , 5 , 0 , 47 , 0 , 49 , 0 , 91 , 0 , 125 , 0 , 231 , 0 , 105 , 0 , 83 , 0 , 117 , 0 , 31 , 0 , 33 , 0 , 203 , 0 , 237 , 0 , 215 , 0 , 89 , 0 , 195 , 0 , 229 , 0 , 15 , 0 , 17 , 0 , 59 , 0 , 93 , 0 , 199 , 0 , 73 , 0 , 51 , 0 , 85 , 0 , 255 }; uint32_t a32 = ( uint32_t ) a ; uint32_t x = tbl [ a & 0xFF ]; // Inverse Modulo 2^8 x *= 2 - a32 * x ; // 32-Bit-Multiplikationen x *= 2 - a32 * x ; // 32-Bit-Multiplikationen return x * ( 2 - a * x ); // 64-Bit-Multiplikationen }

Die Bestimmung des modularen multiplikativen Inversen findet in Algorithmen, die auf der Theorie der modularen Arithmetik basieren, vielfältige Anwendung. Beispielsweise ermöglicht die Verwendung modularer Arithmetik in der Kryptographie die schnellere und speichereffizientere Durchführung bestimmter Operationen, während andere dadurch erschwert werden. ^{[ 15 ]} Beide Eigenschaften können vorteilhaft genutzt werden. Insbesondere beim RSA-Algorithmus erfolgt die Ver- und Entschlüsselung einer Nachricht mithilfe eines Zahlenpaares, dessen multiplikative Inverse bezüglich eines sorgfältig gewählten Moduls sind. Eine dieser Zahlen wird veröffentlicht und für die schnelle Verschlüsselung verwendet, während die andere, für die Entschlüsselung benötigte Zahl geheim gehalten wird. Die Bestimmung der geheimen Zahl aus der öffentlichen Zahl gilt als rechnerisch unmöglich, wodurch die Vertraulichkeit des Systems gewährleistet wird. ^{[ 16 ]}

Ein weiteres Beispiel in einem anderen Kontext ist das Problem der exakten Division in der Informatik. Hierbei hat man eine Liste ungerader Zahlen in Wortlänge, die jeweils durch k teilbar sind , und möchte sie alle durch k teilen . Eine Lösung sieht folgendermaßen aus:

1. Berechnen Sie mithilfe des erweiterten euklidischen Algorithmus k ^{− 1} , das modulare multiplikative Inverse von k mod 2 ^w , wobei w die Anzahl der Bits in einem Wort ist. Dieses Inverse existiert, da die Zahlen ungerade sind und der Modulus keine ungeraden Faktoren enthält.
2. Multipliziere jede Zahl in der Liste mit k ^{− 1} und nimm das niederwertigste Wort des Ergebnisses.

Auf vielen Rechnern, insbesondere solchen ohne Hardwareunterstützung für die Division, ist die Division langsamer als die Multiplikation, daher kann dieser Ansatz eine erhebliche Beschleunigung erzielen. Der erste Schritt ist zwar relativ langsam, muss aber nur einmal durchgeführt werden.

Modulare multiplikative Inverse werden verwendet, um eine Lösung eines Systems linearer Kongruenzen zu erhalten, die 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 teilerfremd sind . Eine Lösung ist gegeben durch

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

Wo

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

t² = ₆ ist das modulare multiplikative Inverse von 5 × 11 (mod 7) und

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

Daher,

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)

da 385 das kleinste gemeinsame Vielfache von 5, 7 und 11 ist.

Auch das modulare multiplikative Inverse spielt eine wichtige Rolle in der Definition der Kloosterman-Summe .

• Inverser Kongruenzgenerator – ein Pseudozufallszahlengenerator, der modulare multiplikative Inverse verwendet
• Rationale Rekonstruktion (Mathematik)

• Ireland, Kenneth; Rosen, Michael (1990), 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: Grundlegende Begriffe der abstrakten Mathematik . Addison-Wesley. ISBN 0-201-82653-4Die
• Trappe, Wade; Washington, Lawrence C. (2006), Einführung in die Kryptographie mit Codierungstheorie (2. Aufl.), Prentice-Hall, ISBN 978-0-13-186239-5

• Weisstein, Eric W. „Modular Inverse“ . MathWorld .
• Fernando Guevara Vasquez liefert ein gelöstes Beispiel zur Berechnung der modulo multiplikativen Inversen mithilfe des euklidischen Algorithmus.
• Die Methode zur Berechnung multiplikativer Inversen ganzer Zahlen mittels des Newton-Verfahrens liefert schnelle Algorithmen zur Berechnung multiplikativer Inversen modulo Zweierpotenzen.