Algoritmus inverze Itoh – Tsujii - Itoh–Tsujii inversion algorithm
The Algoritmus inverze Itoh – Tsujii se používá k invertování prvků v a konečné pole. To bylo představeno v roce 1988 a poprvé použito přes GF (2m) za použití normální základ reprezentace prvků, avšak algoritmus je obecný a lze jej použít pro jiné báze, například polynomiální základ. Může být také použit v jakémkoli konečném poli, GF (pm).
Algoritmus je následující:
- Vstup: A ∈ GF (pm)
- Výstup: A−1
- r ← (pm − 1)/(p − 1)
- vypočítat Ar − 1 v GF (pm)
- vypočítat Ar = Ar − 1 · A
- vypočítat (Ar)−1 v GF (p)
- vypočítat A−1 = (Ar)−1 · Ar −1
- vrátit se A−1
Tento algoritmus je rychlý, protože kroky 3 a 5 zahrnují operace v podpole GF (p). Podobně, pokud je malá hodnota p je použito vyhledávací tabulku lze použít pro inverzi v kroku 4. Většina času stráveného v tomto algoritmu je v kroku 2, první umocňování. To je jeden z důvodů, proč je tento algoritmus vhodný pro normální základ, protože kvadratura a umocňování jsou na tomto základě relativně snadné.
Viz také
Reference
- T. Itoh a S. Tsujii. Rychlý algoritmus pro výpočet multiplikativních inverzí v GF (2m) Používání normálních základen. Informace a výpočet, 78:171–177, 1988.