Content deleted Content added
No edit summary |
m →top: Proper minus signs and other cleanup. Report bugs, errors, and suggestions at User talk:MinusBot |
||
| (4 intermediate revisions by one other user not shown) | |||
Line 1:
While the algorithm is often called the Itoh-Tsujii algorithm, it was first presented by Feng
Feng's paper was received on March 13, 1987 and published in October 1989. Itoh and Tsujii's paper was received on July 8, 1987 and published in 1988
▲This algorithm is first used to invert elements in [[finite field]] {{math|GF(2<sup>''m''</sup>)}} using
the [[normal basis]] representation of elements, however, it is generic and can be used for other bases,
such as the [[polynomial basis]]. It can also be used in any finite field {{math|GF(''p''<sup>''m''</sup>)}}.
Line 25 ⟶ 24:
</math>
The above {{math|''A''<sup>
<math display="block">
Norm(A)=\prod_{i=0}^{m-1}{A^{2^i}}.
Line 32 ⟶ 31:
This viewpoint leads us to consider the additive absolute Trace function
<ref>{{cite web |url=http://eprint.iacr.org/2020/482.pdf |title=A Trace Based {{math|GF(2<sup>''n''</sup>)}} Inversion Algorithm
|access-date=Jan 10, 2025 |archive-url=http://eprint.iacr.org/2020/482 |first1=Haining|last1=Fan
|archive-date=May 6, 2020 }}</ref>
, which is defined as
Line 43 ⟶ 42:
A=\sum_{i=1}^{m-1}{A^{2^i}}
</math>
and can express {{math|''A''<sup>
<math display="block">
A^{-1}=A^{-2}\sum_{i=1}^{m-1}{A^{2^i}}=\sum_{i=1}^{m-1}{A^{2^i-2}}=\sum_{j=0}^{m-2}{(A^2)^{2^{j}-1}}.
Line 63 ⟶ 62:
</math>
This additive formula needs 3 multiplications, 4 additions and 6 squarings.
But the multiplicative formula
Line 70 ⟶ 69:
</math>
needs 4 multiplications and 7 squarings.
== See also ==
| |||