definiție
Să presupunem că avem un modul natural și ia în considerare inelul format de către modulul (adică, format din numere de la). Apoi, pentru unele elemente ale acestui inel poate fi găsit un element invers.
Inversul numărului de module se numește un număr astfel încât:
și de multe ori notate.
Este clar că niciodată nu se întoarce la elementul de zero; pentru elementele rămase ale inversei, fie pot exista sau nu. Se afirmă că există inversul numai pentru acele elemente care sunt relativ prim la modul.
Luați în considerare următoarele două modalități de a găsi elementul invers de lucru, cu condiția ca acesta există.
În concluzie, să luăm în considerare un algoritm care vă permite să găsiți toate numerele înapoi la peste un anumit modul în timp liniar.
Găsirea folosind algoritmul lui Euclid extins
Să considerăm ecuația auxiliară (și relativ necunoscut):
Această ecuație liniară Diophantine este de ordinul doi. După cum se arată în articolul relevant din condiția ca această ecuație are o soluție care poate fi găsită folosind algoritmul Euclidian extins (deci în același mod, rezultă că atunci când, soluții, și, prin urmare, elementul invers nu există).
Pe de altă parte, dacă luăm din ambele părți ale modulului de echilibru ecuație, obținem:
Astfel, și va fi găsit la reflux.
Punerea în aplicare (inclusiv faptul că a constatat că este necesar să se ia valoarea absolută, și ar putea fi negativ):
Asymptotics ale soluțiilor obținute.
Găsirea folosind exponentiere binare
Noi folosim teorema lui Euler:
care este valabil doar pentru cazul relativ prim și.
Apropo, avem o chiar mai mult în cazul unei simple declarații a unui simplu modul - teorema lui Fermat puțin:
Inmultiti ambele părți ale fiecăreia dintre ecuațiile pentru a obține:
Astfel, avem formula pentru calcularea directă a returului. Pentru aplicații practice, de obicei folosesc un algoritm binar exponentiere eficient. care, în acest caz, va permite să facă exponentiere pentru.
Această metodă pare a fi oarecum mai ușor descrisă în paragraful precedent, dar necesită cunoașterea valorilor funcției lui Euler, care necesită de fapt factorizarea modulului, care poate fi uneori destul de dificilă.
Dacă numărul câtul este cunoscut, atunci această metodă funcționează, de asemenea, pentru comportamentul asimptotic.
Găsirea tuturor prim pentru un anumit modul în timp liniar
Având în vedere un modul simplu. Necesar pentru fiecare număr în intervalul de a găsi inversa ei.
Aplicarea algoritmului descris mai sus, obținem doar cu soluțiile asimptotice. Aici vom da o soluție simplă pentru comportamentul asimptotic.
Soluția este după cum urmează. Notam numărul modulo invers dorit. Apoi, pentru 1 „> adevărata identitate:
Punerea în aplicare a acestei soluții uimitor de concis:
Dovada acestei soluții este un lanț de transformări simplu:
în cazul în care, luând ambele părți ale modulului, obținem:
Înmulțind ambele părți prin inverse și invers pentru a obține formula cerută:
QED.