Valoare inversă modulo

Un număr simplu este un număr mai mare decât unul, ale cărui singuri factori sunt 1 și în sine: nu este divizibil prin nici un alt număr. Două este un număr prime. Simple sunt, de asemenea, 73, 2521, 2365347734339 și 2756839-1. Există nenumărate numere prime. Criptografia, în special criptografia cu chei publice, utilizează adesea numere prime mari (512 de biți sau mai mult).

Cel mai mare divizor comun

Se spune că două numere sunt relativ prime dacă nu au multiplicatori comuni cu excepția 1. Cu alte cuvinte, dacă cel mai mare divizor comun al a și n este 1. Acesta este scris ca:
GCD (a, n) = 1

Simplu sunt simple numerele 15 și 28. 15 și 27 nu sunt reciproc prime, iar 13 și 500 sunt. Un număr prime este relativ prime pentru toate celelalte numere, cu excepția numerelor care sunt multipli ai unui număr prime dat.
O modalitate de a calcula cel mai mare divizor comun de două numere este algoritmul euclidian. Euclid a descris acest algoritm în cartea sa Elemente scrise în 300 î.Hr. Nu a inventat-o. Istoricii cred că acest algoritm este cu 200 de ani mai în vârstă. Acesta este cel mai vechi algoritm netrivial care a coborât în ​​zilele noastre și este încă bun. Knut a descris algoritmul și modificările sale moderne.

Valoare inversă modulo

Amintiți-vă care sunt valorile opuse? Valoarea reciprocă a valorii pentru 4 este 1/4, deoarece 4 * 1/4 = 1. În lumea reziduurilor, problema devine mai complicată:
4 * x = 1 (mod 7)
Această ecuație este echivalentă cu detectarea lui x și k, astfel încât
4x = 7k + 1
unde x și k sunt numere întregi. Problema generală este de a găsi x, astfel încât
1 = (a * x) mod n
Acest lucru poate fi scris și ca
a-1 = x (mod n)
Problema valorilor inverse modulo nu este ușor de rezolvat. Uneori are o soluție, uneori nu. De exemplu, valoarea inversă a lui 5 modulo 14 este 3. Pe de altă parte, numărul 2 nu are o valoare inversă modulo 14.






În cazul general, pentru ecuația a-1 = x (mod n) există o soluție unică dacă a și n sunt relativ prime. Dacă a și n nu sunt coprime, atunci a-1 = x (mod n) nu are soluții. Dacă n este un număr prime, atunci orice număr de la 1 la n-1 este relativ prime la n și are exact o valoare inversă modulo n.
Deci, e bine. Și acum cum veți căuta inversul unui modulo n? Există două moduri. Valoarea inversă a unui modulo n poate fi calculată folosind algoritmul euclidian. Uneori se numește algoritmul extins al lui Euclid.
Algoritmul este iterativ și poate funcționa încet pentru numere mari. Knuth a arătat că numărul mediu de diviziuni realizat de algoritm este:
0,843 * log2 (n) + 1,47.
Soluția pentru coeficienți
Euclid algoritmul poate fi, de asemenea, folosit pentru a rezolva următoarele probleme: dat o serie de variabile m x1, x2. xm, găsiți o matrice de coeficienți m, ul, u2. um, astfel încât
ul * x1 +. + um * xm, = 1
Teorema restului chinezesc
Dacă este cunoscută descompunerea numărului n în factori simpli, atunci teorema restului chinez poate fi utilizată pentru a rezolva întregul sistem de ecuații. Versiunea de bază a acestei teoreme a fost descoperită în primul secol de matematicianul chinez Sun Jie.
În cazul general, dacă descompunerea numărului n în factori simpli este p1 * p2 *. * pt, apoi sistemul de ecuații
(x mod pi) = ai, unde i = 1, 2. t
are o soluție unică, x, mai mică de n. (Rețineți că unele numere simple pot apărea de mai multe ori. De exemplu, p1 poate fi egal cu p2.) Cu alte cuvinte, numărul (mai mic decât produsul unui număr de numere prime) este definit în mod unic prin reziduurile sale modulo numerele prime.
De exemplu, luați numerele prime 3 și 5 și 14 ca numărul dat. 14 mod 3 = 2 și 14 mod 5 = 4. Există un singur număr mai mic de 3 * 5 = 15, cu astfel de reziduuri: 14. Două resturi determină în mod unic numărul.
Prin urmare, pentru un arbitrar a

x = a (mod p) și x = b (mod q)
Pentru a obține x, mai întâi folosim algoritmul lui Euclid pentru a găsi u, astfel încât
u * q 1 (mod p)
Calculați apoi:
x = (((a - b) * u) mod p) * q + b
Contactarea teoremă restul chineză poate fi folosit pentru a rezolva următoarea problemă: dacă p și q - amorse, iar p este mai mic decât q, atunci există un x unic, mai puțin de pq, astfel încât
a = x (mod p) și b = x (mod q)
Dacă a> = b mod p, atunci
x = (((a - (b mod p)) * u) mod p) * q + b
Dacă a x = ((a + p - (b mod p)) * u) mod p) * q + b