Modulo număr reciproc

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 20 aprilie 2022; verificările necesită 18 modificări .

Inversul modulo un număr întreg a este un număr întreg x astfel încât produsul ax este congruent cu 1 modulo m [1] . În notația aritmetică modulară standard , această echivalență este scrisă ca:

ax\equiv 1{\pmod {m)),

care este un mod prescurtat de a spune că m împarte (fără rest) valoarea ax − 1 , sau, pentru a spune altfel, restul când ax este împărțit la întregul m este 1. Dacă a are un modulo invers invers , atunci există un număr infinit de soluții la această echivalență, care formează clasa de reziduuri pentru acest modul. Mai mult, orice număr întreg care este echivalent cu a (adică din clasa de echivalență a ) va avea ca invers orice element al clasei de echivalență x . Folosind notația pentru o clasă de echivalență care conține , afirmația de mai sus poate fi scrisă după cum urmează: elementul invers modulo o clasă de echivalență este o clasă de echivalență astfel încât $\overline {w}$ $w$ ${\overline {a}}$ $\overline{x}$

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

unde simbol înseamnă multiplicarea claselor de echivalență modulo m [2] . Acest tip de notaţie reprezintă un analog al conceptului obişnuit de număr invers în mulţimea numerelor raţionale sau reale , dacă înlocuim numerele cu clase de echivalenţă şi definim corect operaţiile binare . $\cdot _{m}$

Utilizarea fundamentală a acestei operații este de a rezolva o echivalență liniară de forma:

ax\equiv b{\pmod {m)).

Găsirea inversului modular are aplicații practice în domeniul criptografiei , cum ar fi criptosistemul cu cheie publică și algoritmul RSA [3] [4] [5] . Avantajul implementării acestor aplicații este că există un algoritm foarte rapid (algoritmul lui Euclid extins ) care poate fi folosit pentru a calcula inversele modulare.

Aritmetică modulară

Pentru un număr pozitiv dat m , se spune că două numere întregi a și b sunt congruente modulo m dacă m împarte diferența lor. Această relație binară se notează ca

a\equiv b{\pmod {m)).

Aceasta este o relație de echivalență pe mulțimea numerelor întregi , iar clasele de echivalență sunt numite clase de reziduuri modulo m . Să notăm o clasă de echivalență care conține un număr întreg a [6] , atunci $\mathbb {Z}$ ${\overline {a}}$

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

Comparația liniară este o comparație modulo a formei

ax\equiv b{\pmod {m)).

Spre deosebire de ecuațiile liniare din numere întregi , o comparație liniară poate avea zero, una sau mai multe soluții. Dacă x este o soluție la o comparație liniară, atunci orice element al este și o soluție, deci atunci când vorbim despre numărul de soluții la o comparație liniară, ne referim la numărul de clase de echivalență diferite pe care le conțin aceste soluții. $\overline{x}$

Dacă d este cel mai mare divizor comun al lui a și m , atunci comparația liniară are soluții dacă și numai dacă d împarte b . Dacă d împarte b , atunci există exact d soluții [7] . $ax\equiv b{\pmod {m)}$

Modul reciprocă a unui număr întreg a modulo m este soluția comparației liniare

ax\equiv 1{\pmod {m)).

S-a spus mai devreme că o soluție există dacă și numai dacă cel mai mare divizor comun al lui a și m este 1, adică a și m trebuie să fie numere prime relativ . Mai mult, dacă această condiție este îndeplinită, există exact o soluție, adică dacă există o soluție, inversul modular este unic [8] .

Dacă are o soluție, este adesea notat după cum urmează $ax\equiv 1{\pmod {m)}$

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

totuși, acest lucru poate fi considerat un abuz de , deoarece poate fi interpretat greșit ca o reciprocă normală (care, spre deosebire de reciproca modulului, nu este un număr întreg decât atunci când a este 1 sau -1). Notația ar fi acceptabilă dacă a ar fi interpretată ca notație pentru clasa de reziduuri , deoarece elementul invers al clasei de reziduuri este din nou o clasă de reziduuri cu operația de înmulțire definită în secțiunea următoare. $A$ ${\overline {a}}$

Numerele întregi modulo m

Relația de echivalență modulo m împarte mulțimea de numere întregi în m clase de echivalență. Operațiile de adunare și înmulțire pot fi definite pe aceste obiecte astfel: pentru adunarea sau înmulțirea claselor de echivalență, mai întâi, reprezentanții acestor clase sunt selectați în orice mod, apoi operația obișnuită este efectuată asupra numerelor întregi selectate și, în final, rezultatul al operațiunii se află în clasa de reziduuri, care este rezultatul operației asupra claselor . În formă simbolică, cu și reprezentând operații pe clase de reziduuri, aceste definiții pot fi scrise ca ${\displaystyle +_{m))$ $\cdot _{m}$

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

și

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

Aceste operațiuni sunt bine definite (ceea ce înseamnă că rezultatul final nu depinde de alegerea reprezentanților).

Clasele de reziduuri modulo m cu aceste două operații formează un inel , numit inel de numere întregi modulo m . Există mai multe notații utilizate pentru aceste entități algebrice, cea mai frecvent utilizată fiind sau , cu toate acestea, unele manuale și aplicații elementare folosesc notația simplificată, cu excepția cazului în care intră în conflict cu alte entități algebrice. $\mathbb{Z}/m\mathbb{Z}$ $\mathbb {Z} /m$ $\mathbb {Z} _{m}$

Clasele reziduale de numere întregi modulo m au fost cunoscute în mod tradițional ca clase de reziduuri mod m , reflectând faptul că toate elementele unei clase de echivalență au același rest atunci când sunt împărțite la m . Orice set de m numere întregi alese din diferite clase de reziduuri modulo m se numește sistem complet de resturi modulo m [9] . Împărțirea la o coloană arată că mulțimea numerelor întregi {0, 1, 2, ..., m − 1} formează un sistem complet de reziduuri modulo m , cunoscut sub numele de cel mai mic sistem de resturi modulo m . Când se lucrează cu probleme aritmetice, uneori este mai convenabil să se lucreze cu întregul sistem de reziduuri și să se folosească limbajul de echivalență, în timp ce în alte cazuri este mai convenabil să se uite în termeni de clase de echivalență inelă [10] . $\mathbb{Z}/m\mathbb{Z}$

Grupul multiplicativ al inelului rezidual

Nu fiecare element al sistemului complet de reziduuri modulo m are un element invers, de exemplu, zero nu are invers. După îndepărtarea elementelor sistemului complet de reziduuri care nu sunt relativ prime pentru m , elementele rămase, care se numesc sistemul redus de reziduuri , au toate inverse. Numărul de elemente din sistemul redus de reziduuri este , unde este funcția Euler , adică numărul de numere întregi pozitive mai mici decât m care sunt relativ prime pentru m . $\phi (m)$ $\phi$

Într -un inel cu o unitate generală, nu orice element are un invers , iar cei care o au se numesc inversabil . Deoarece produsul elementelor inversabile este inversabil, elementele inversabile ale unui inel formează un grup , grupul de elemente inversabile ale unui inel , iar acest grup este adesea notat ca și cum R ar fi numele unui inel. Grupul de elemente inversabile ale inelului de numere întregi modulo m se numește grupul multiplicativ de numere întregi modulo m și este izomorf la sistemul redus de reziduuri. În special, ordinea (dimensiunea) este . $R^{\times )$ $\phi (m)$

Când m este prim , să spunem p , atunci toate elementele nenule au inverse și este atunci un câmp finit . În acest caz, grupul multiplicativ de numere întregi modulo p formează un grup ciclic de ordinul p − 1 . $\phi (p)=p-1$ $\mathbb{Z}/p\mathbb{Z}$ $\mathbb{Z}/p\mathbb{Z}$

Exemplu

Pentru a ilustra definițiile de mai sus, luați în considerare exemplul numerelor modulo 10.

Două numere sunt echivalente în 10 dacă și numai dacă diferența lor este divizibilă cu 10, de exemplu

32\equiv 12{\pmod {10}}

deoarece 10 împarte 32 − 12 = 20,

111\equiv 1{\pmod {10}}

deoarece 10 împarte 111 − 1 = 110.

Unele dintre clasele de reziduuri pentru acest modulo sunt:

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

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

{\overline {5}}=\{\cdots ,-15,-5,5,15,25,\cdots \)

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

Comparația liniară nu are soluție deoarece numerele întregi congruente cu 5 (adică cele din ) sunt toate impare, în timp ce 4x sunt toate pare. Totuși, comparația liniară are două soluții și anume și . mcd(4, 10) = 2 și 2 nu împarte 5, ci împarte 6. $4x\equiv 5{\pmod {10}}$ ${\overline {5}}$ $4x\equiv 6{\pmod {10}}$ $x=4$ $x=9$

Deoarece gcd(3, 10) = 1, comparația liniară va avea soluții, adică va exista reciproca modulo a lui 3 modulo 10. 7 satisface această ecuație (21 − 1 = 20). Cu toate acestea, alte numere întregi satisfac această ecuație, cum ar fi 17 și −3 (deoarece 3(17) − 1 = 50 și 3(−3) − 1 = −10). În special, orice număr întreg din va satisface ecuația, deoarece aceste numere sunt de forma 7 + 10 r pentru unele r și este clar că $3x\equiv 1{\pmod {10}}$ ${\overline {7)}$

3(7+10r)-1=21+30r-1=20+30r=10(2+3r),

este divizibil cu 10. Această ecuație are doar o singură clasă de reziduuri ca soluții. Soluția în acest caz poate fi obținută pur și simplu prin enumerarea claselor posibile, dar sunt necesari algoritmi sistematici pentru a obține o soluție pentru module mari și vor fi prezentați în secțiunile următoare.

Produsul claselor de reziduuri și poate fi obținut prin alegerea unui element din , să zicem 25, și a unui element din , să zicem −2, iar produsul lor (25)(−2) = −50 este în clasa de echivalență . Astfel, . Adăugarea este definită într-un mod similar. Cele zece clase de reziduuri, împreună cu aceste operații de adunare și multiplicare a claselor de reziduuri, formează un inel de numere întregi modulo 10, adică . ${\overline {5}}$ ${\overline {8}}$ ${\overline {5}}$ ${\overline {8}}$ $\overline {0}$ ${\overline {5}}\cdot _{10}{\overline {8}}={\overline {0}}$ $\mathbb {Z} /10\mathbb {Z}$

Un sistem complet de reziduuri modulo 10 poate fi mulțimea {10, −9, 2, 13, 24, −15, 26, 37, 8, 9}, unde fiecare număr întreg aparține propriei sale clase de reziduuri modulo 10. Sistemul de reziduuri minime modulo 10 servește ca {0, 1, 2, ..., 9}. Sistemul redus de reziduuri modulo 10 poate fi {1, 3, 7, 9}. Produsul oricăror două clase de reziduuri reprezentate de aceste numere este din nou una dintre aceste patru clase. Rezultă că aceste patru clase de reziduuri formează un grup, în acest caz un grup ciclic de ordinul 4, având ca generator 3 sau 7. Clasele de reziduuri prezentate formează grupul de elemente inversabile ale inelului . Aceste clase de reziduuri sunt exact cele care au reciproce modulo. $\mathbb {Z} /10\mathbb {Z}$

Calcul

Algoritmul lui Euclid extins

Modul invers al unui modulo m poate fi găsit folosind algoritmul euclidian extins.

Algoritmul lui Euclid determină cel mai mare divizor comun (mcd) a două numere întregi, să spunem a și m . Dacă a are inversul modulo m , acest mcd trebuie să fie egal cu 1. Ultimele câteva egalități obținute în timpul funcționării algoritmului pot fi rezolvate pentru a găsi mcd. Apoi, folosind metoda „substituției inverse”, poate fi obținută o expresie care leagă parametrii originali și GCD. Cu alte cuvinte, pot fi găsite numere întregi x și y care satisfac egalitatea lui Bézout ,

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

Să-l rescriem după cum urmează

ax-1=(-y)m,

acesta este,

ax\equiv 1{\pmod {m)),

și se calculează reciproca modulo a lui a . O versiune mai eficientă este algoritmul Euclid extins, care reduce două treceri ale algoritmului (substituția înapoi poate fi considerată ca parcurgând algoritmul în ordine inversă) la una folosind egalități suplimentare.

În notația O mare, acest algoritm rulează în timp presupunând că , și este considerat a fi foarte rapid. Este de obicei mai eficient decât algoritmul exponențial alternativ. $O(\log(m)^{2})$ $|a|<m$

Folosind teorema lui Euler

Ca o alternativă la algoritmul euclidian extins pentru calcularea elementului invers modular, se poate lua în considerare utilizarea teoremei lui Euler [11] .

Conform teoremei lui Euler , dacă a este relativ prim pentru m , adică mcd( a , m ) = 1, atunci

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

unde este funcția Euler . Aceasta rezultă din faptul că a aparține grupului multiplicativ dacă și numai dacă a este relativ prim cu m . Deci inversul modular poate fi găsit direct: $\phi$ $(\mathbb {Z} /m\mathbb {Z} )^{\times )$

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

În cazul special în care m este prim și inversul modular este dat de $\phi (m)=m-1$

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

Această metodă este, în general, mai lentă decât algoritmul Euclid extins, dar este uneori folosită dacă este deja disponibilă o implementare pentru exponențiarea modulară. Dezavantajele acestei metode:

Valoarea trebuie cunoscută, iar cea mai eficientă metodă de calcul necesită m extinderi . Descompunerea este bine cunoscută ca o problemă în care calculul ocupă cea mai mare parte a complexității soluției. Cu toate acestea, poate fi calculat direct dacă se cunoaște descompunerea în factori primi a numărului m . $\phi (m)$ $\phi (m)$
Cost relativ ridicat de exponentiare. Deși acest lucru se poate face mai eficient cu construcția modulară , pentru valori mari de m , metoda algoritmului Montgomery este cea mai eficientă . Acest algoritm în sine necesită calcularea inversului modulo m . Fără algoritmul lui Montgomery, algoritmul standard de exponențiere binară , care necesită modulo m la fiecare pas, este o operație lentă pentru m mare .

Avantajul remarcabil al acestei tehnici este că nu există ramuri condiționate care să depindă de valoarea a , și, prin urmare, valoarea a , care poate fi un secret important în criptosistemele cu cheie publică , poate fi protejată de atacurile pe canalul lateral . Din acest motiv, implementarea standard a Curbei25519 folosește tehnica de calcul a elementului invers.

Calcularea inverselor multiple

Este posibil să se calculeze reciprocele mai multor numere modulo m folosind o trecere a algoritmului Euclid și trei înmulțiri pentru fiecare număr de intrare suplimentar [12] . Ideea de bază este de a forma toate , de a o inversa și apoi de a înmulți cu pentru toți , lăsând doar . $a_{i}$ $a_{i}$ $a_{j}$ $j\neq i$ ${\displaystyle a_{i}^{-1))$

Algoritm (toată aritmetica se face modulo m ):

Calculați produse cu prefix pentru toate . ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1))$ $i\leqslant n$
Calculați folosind orice algoritm disponibil. $b_{n}^{-1)$
Pentru i de la n la 2 calculăm
- ${\displaystyle a_{i}^{-1}=b_{i}^{-1}b_{i-1))$ și
- ${\displaystyle b_{i-1}^{-1}=b_{i}^{-1}a_{i))$ .
În cele din urmă, . ${\displaystyle a_{1}^{-1}=b_{1}^{-1))$

Este posibil să se implementeze înmulțirea sub forma unei structuri arborescente, mai degrabă decât una liniară, pentru a asigura paralelismul calculelor .

Aplicații

Căutarea inversului modular are multe aplicații în algoritmi bazați pe teoria aritmeticii modulare. De exemplu, în criptografie, utilizarea aritmeticii modulare permite ca unele operații să fie efectuate mai rapid și cu mai puține cerințe de memorie, în timp ce alte operațiuni devin mai dificil de efectuat [13] . Ambele proprietăți pot fi folosite definitiv. În special, în algoritmul RSA , criptarea și procesul invers de comunicare se realizează folosind o pereche de numere reciproce unul cu celălalt într-un modulo atent ales. Unul dintre aceste numere este făcut public și poate fi folosit în procedura de criptare rapidă, în timp ce celălalt număr este folosit în procedura de decriptare și nu este dezvăluit. Determinarea unei chei ascunse de la una publică este considerată o sarcină imposibilă, deoarece soluția ei necesită mai multă putere de calcul decât există pe Pământ, ceea ce protejează împotriva accesului neautorizat [14] .

Ca o altă utilizare într-un context diferit, luați în considerare problema diviziunii exacte în computere, în care vi se oferă o listă de numere impare de dimensiunea unui cuvânt de calculator, fiecare dintre ele divizibil cu k și trebuie să le împărțiți cu k . O soluție este următoarea:

Folosim algoritmul euclidian extins pentru a calcula , inversul modular al lui , unde w este egal cu numărul de biți din cuvânt. Acest invers există, deoarece toate numerele sunt impare, iar reziduurile sunt considerate modulo, care nu are divizori impari. $k^{{-1}}$ $k{\pmod {2^{w)})$
Înmulțim fiecare număr din listă cu și selectăm biții cei mai puțin semnificativi ai rezultatului (adică aruncăm toți biții din afara cuvântului computerului). $k^{{-1}}$

Pe multe mașini, în special pe cele fără suport hardware pentru divizare, diviziunea este o operațiune mai lentă decât înmulțirea, astfel încât această abordare poate duce la o creștere semnificativă a vitezei. Primul pas este relativ lent, dar trebuie făcut o singură dată.

reciprocele modulare sunt folosite pentru a obține o soluție la un sistem de comparații liniare, care este garantată de teorema chineză a restului .

De exemplu, sistemul

{\begin{cases}X\equiv 4{\pmod {5}}\\X\equiv 4{\pmod {7}}\\X\equiv 6{\pmod {11}}\\\end {cazuri}}

are o soluție generală deoarece 5, 7 și 11 sunt coprime perechi . Soluția este dată de formula

X=t_{1}(7\times 11)\times 4+t_{2}(5\times 11)\times 4+t_{3}(5\times 7)\times 6

Unde

t_{1}=3

invers modular ,

7\times 11{\pmod {5}}

t_{2}=6

invers modular ,

5\times 11{\pmod {7}}

t_{3}=6

invers modular .

5\times 7{\pmod {11}}

Apoi,

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

iar în forma dată

X\equiv 3504\equiv 39{\pmod {385}}

deoarece 385 este cel mai mic multiplu comun al lui 5, 7 și 11.

Inversul modular figurează proeminent în definiția sumelor Kloosterman .

Vezi și

Metoda congruențială inversă este un algoritm pentru generarea de numere pseudoaleatoare care utilizează numere inverse modulo.
Recuperarea unui număr rațional modulo it

Note

↑ Rosen, 1993 , p. 132.
↑ Schumacher, 1996 , p. 88.
↑ Stinson, 1995 , p. 124–128.
↑ Trappe, Washington, 2006 , p. 164-169.
↑ Moriarty, K.; Kaliski, B.; Jonsson, J.; Rusch, A. PKCS #1: Specificații de criptare RSA Versiunea 2.2 . Internet Engineering Task Force RFC 8017 . Grupul operativ de inginerie a internetului (2016). Preluat la 21 ianuarie 2017. Arhivat din original la 12 decembrie 2018. (nedefinit)
↑ Alte notații sunt adesea folosite, inclusiv [ a ] și [ a ] m .
↑ Irlanda, Rosen, 1990 , p. 32.
↑ Shoup, 2005 , p. 15 Teorema 2.4.
↑ Rosen, 1993 , p. 121.
↑ Irlanda, Rosen, 1990 , p. 31.
↑ Koshy, 2007 , p. 346.
↑ Brent, Zimmermann, 2010 , p. 67–68.
↑ Trappe, Washington, 2006 , p. 167.
↑ Trappe, Washington, 2006 , p. 165.

Literatură

Douglas R. Stinson. Criptografie / Teorie și practică. - CRC Press, 1995. - ISBN 0-8493-8521-0 .
Victor Shop. O introducere computațională în teoria numerelor și algebră . - Cambridge University Press, 2005. - ISBN 9780521851541 .
Thomas Koshy. Teoria elementară a numerelor cu aplicații . — ediția a II-a. - Presa Academică, 2007. - ISBN 978-0-12-372487-8 .
Richard P. Brent , Paul Zimmermann . §2.5.1 Mai multe inversiuni deodată // Teoria elementară a numerelor cu aplicații. Aritmetica computerizată modernă . - Cambridge University Press, 2010. - V. 18. - (Cambridge Monographies on Computational and Applied Mathematics). — ISBN 978-0-521-19469-3 .

Kenneth Irlanda, Michael Rosen. O introducere clasică în teoria modernă a numerelor. — al 2-lea. - Springer-Verlag, 1990. - ISBN 0-387-97329-X .
- C. Irlanda, M. Rosen. Introducere clasică în teoria numerelor moderne / Tradus din engleză de S. P. Demushkin. - Moscova: Mir, 1987.

Kenneth H. Rosen. Teoria elementară a numerelor și aplicațiile sale. — al 3-lea. - Addison-Wesley, 1993. - ISBN 978-0-201-57889-8 .
Carol Schumacher. Capitolul Zero: Noțiuni fundamentale de matematică abstractă . - Addison-Wesley, 1996. - ISBN 0-201-82653-4 .
Wade Trappe, Lawrence C. Washington. Introducere în Criptografie cu Teoria Codării. — al 2-lea. - Prentice-Hall, 2006. - ISBN 978-0-13-186239-5 .

Link -uri

Weisstein, Eric W. Modular Inverse (engleză) pe site-ul web Wolfram MathWorld .
Guevara Vasquez, Fernando oferă un exemplu de rezolvare a modulo inversă folosind algoritmul euclidian.