An optimal algorithm for multiplication in \(\mathbb{F}_{256}/\mathbb{F}_ 4\) (Q1177865): Difference between revisions

The authors present a bilinear algorithm for multiplication of two elements of \(\mathbb{F}_{256}=(\mathbb{F}_ 4)^ 4\) using eight multiplications in \(\mathbb{F}_ 4\). This number of 8 required \(\mathbb{F}_ 4\)-multiplications is minimal. This algorithm is an application of an interpolation from \textit{D. V. Chudnovsky} and \textit{G. V. Chudnovsky} [Proc. Natl. Acad. Sci. USA 84, 1739-1743 (1987; Zbl 0644.68066)] applied to a well-chosen projective curve, i.e. the Fermat curve \(x^ 3+y^ 3=1\) over \(\mathbb{F}_ 4\).