Megtalálása inverz eleme a gyűrűmaradék - verem túlcsordulás az orosz
Kétféle módon lehet megoldani ezt a problémát.
Az első út - használata a kiterjesztett euklideszi algoritmus.
Euklideszi algoritmus keresi a legnagyobb közös osztója a két szám. Extended euklideszi algoritmus ugyanabban az időben, mint a legnagyobb közös osztója jelentése egész szám, lineáris kombinációja a kezdeti szám:
Amint az könnyen látható, ha az A és C nem relatív prím, akkor nincs megoldás, és ha vannak - a együtthatója A jelentése a kívánt inverz elem (igazolására lehet cserélni a fenti képletben B C és vegye mindkét oldalán a C mod) .
Rekurzív algoritmus nagyon egyszerű. A következő lépés, a nagyobb a két szám (egyedinek, a) képviseli, mint a C + K ∙ b. akkor az algoritmus az úgynevezett rekurzívan (b, c):
Így van egy Ka = KC1 és Kb = KB1 - KC1 ∙ k
Kapjuk körülbelül az algoritmus:
Iteratív algoritmus egyszerű megvalósítani, de nehéz megérteni. A legegyszerűbb módja, hogy használja a sablont. Először is, meg kell írja le a konverziós együttható mátrix formában:
Ezek mátrix faktorizációja lehet menteni:
Kiderült, a következő algoritmus:
Most, hogy megvan a GCD, továbbra is megtalálja a GCD (A, C), ellenőrizze, hogy az értéke 1, és vegye (Ka% C), amíg a kívánt fordított száma.
Óra - nagyságrendű log A bázis φ ismétléseket (annak a ténynek köszönhető, hogy a legrosszabb esetben az euklideszi algoritmus - a szomszédos Fibonacci-számok).
A második út - használata Euler-képlet
Ha a szám a C előre ismert, vagy elég ideje felkészülni, akkor Euler-képlet:
Ami amelynek triviális közös osztók A és C megoldani a problémát még nem - a korlátozás nem akadályoz meg minket.
A képlet szerint, a válasz egy ^ (φ (C) - 1)% C. gyorsan találni lehet használni az algoritmust gyors hatványozás:
Helyességét az algoritmus könnyen igazolható, ha azt látjuk, hogy a ^ x * b - annak invariáns.
Természetesen, miután a válasz ellenőriznie kell, hogy helyes-e, ha ez a baj -, akkor a válasz nem létezik (A és C közös osztó).
Ez az algoritmus gyorsabb lesz, mint az euklideszi algoritmus, mert itt a logaritmus alapja nagyobb, és maguk iteráció - könnyebb. De φ (C) kell előre tudni az alkalmazás ezen algoritmus