Content deleted Content added
No edit summary |
m →top: Proper minus signs and other cleanup. Report bugs, errors, and suggestions at User talk:MinusBot |
||
| (2 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
Feng and Itoh-Tsujii algorithm is first used to invert elements in [[finite field]] {{math|GF(2<sup>''m''</sup>)}} using
Line 24:
</math>
The above {{math|''A''<sup>
<math display="block">
Norm(A)=\prod_{i=0}^{m-1}{A^{2^i}}.
Line 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 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 62:
</math>
This additive formula needs 3 multiplications, 4 additions and 6 squarings.
But the multiplicative formula
Line 69:
</math>
needs 4 multiplications and 7 squarings.
== See also ==
| |||