Kalkulator modularnog inverza
Izračunajte modularni multiplikativni inverz cijelog broja a modulo m pomoću proširenog Euklidovog algoritma.
Kako radi ovaj kalkulator?
Modularni inverz od a modulo m je cijeli broj x u [0, m) za koji je a·x ≡ 1 (mod m). Postoji samo kada je gcd(a, m) = 1, a pronalazi se proširenim Euklidovim algoritmom, zatim normalizira na pozitivan ostatak. Ako a i m dijele faktor, inverz ne postoji.
Formula
How this is calculated
Broj a reducira se modulo m u raspon [0, m), a modul m mora biti cijeli broj veći od 1. Prošireni Euklidov algoritam zatim se pokreće na (a mod m, m), proizvodeći i najveći zajednički djelitelj gcd(a, m) i Bezoutov koeficijent x takav da a·x + m·y = gcd(a, m).
Modularni inverz postoji samo kada je gcd(a, m) = 1. Kada postoji, sirovi koeficijent x može biti negativan, pa se normalizira u [0, m) pomoću ((x mod m) + m) mod m. Vraćeni inverz zadovoljava (a · x) mod m = 1, prikazano u statistici provjere. Ako je gcd(a, m) ≠ 1, inverz ne postoji i umjesto toga se prijavljuje djelitelj.
Sva aritmetika interno koristi BigInt kako bi se izbjegao gubitak preciznosti s velikim cijelim brojevima. Ulazi moraju biti cijeli brojevi; necijele vrijednosti odbijaju se. Negativne vrijednosti od a obrađuju se redukcijom, pa se primjerice -8 mod 11 tretira kao 3.
Često postavljana pitanja
Inverz od a modulo m postoji samo kada su a i m relativno prosti, to jest gcd(a, m) = 1. Ako dijele zajednički faktor veći od 1, nijedan cijeli broj x ne zadovoljava a·x ≡ 1 (mod m).
Ne. Modul može biti bilo koji cijeli broj veći od 1. Kada je m prost, svaki a od 1 do m−1 ima inverz jer su svi relativno prosti s m, ali složeni moduli također rade za svaki a relativno prost s m.
Broj a najprije se reducira u raspon [0, m) prije pokretanja algoritma, pa se negativni ulazi tretiraju svojim pozitivnim ostatkom. Dobiveni inverz također se normalizira da leži u [0, m).
Poznato i kao
TG we-Calculate Editorial Team. (2026). Kalkulator modularnog inverza [Online calculator]. TG we-Calculate. https://we-calculate.com/hr/calculator/modular-inverse-calculator
TG we-Calculate Editorial Team. "Kalkulator modularnog inverza." TG we-Calculate. 2026. https://we-calculate.com/hr/calculator/modular-inverse-calculator.
TG we-Calculate Editorial Team, "Kalkulator modularnog inverza," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/hr/calculator/modular-inverse-calculator
@misc{wecalculate_modular_inverse_calculator, title = {Kalkulator modularnog inverza}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/hr/calculator/modular-inverse-calculator}}, year = {2026}, note = {TG we-Calculate} }
Je li vam ovaj kalkulator pomogao?