@comment{ generated by <http://infoscience.epfl.ch/> }

@InProceedings{ALGO-CONF-2007-005,
   abstract    = {In this paper we propose a new structure for
                 multiplication using optimal normal bases of type $2$.
                 The multiplier uses an efficient linear transformation to
                 convert the normal basis representations of elements of
                 $F_{q^{n}}$ to suitable polynomials of degree at most $n$
                 over $F_{q}$. These polynomials are multiplied using any
                 method which is suitable for the implementation platform,
                 then the product is converted back to the normal basis
                 using the inverse of the above transformation. The
                 efficiency of the transformation arises from a special
                 factorization of its matrix into sparse matrices. This
                 factorization --- which resembles the FFT factorization
                 of the DFT matrix --- allows to compute the
                 transformation and its inverse using $O(n \log n)$
                 operations in $F_{q}$, rather than $O(n^{2})$ operations
                 needed for a general change of basis. Using this
                 technique we can reduce the asymptotic cost of
                 multiplication in optimal normal bases of type $2$ from
                 $2 M(n) + O(n)$ reported by Gao et
                 al.~(2000)\nocite{gaogat00} to $M(n)+O(n \log n)$
                 operations in $F_{q}$, where $M(n)$ is the number of
                 $F_{q}$-operations to multiply two polynomials of degree
                 $n-1$ over $F_{q}$. We show that this cost is also
                 smaller than other proposed multipliers for $n > 160$,
                 values which are used in elliptic curve cryptography.},
   address     = { },
   affiliation = {EPFL},
   author      = {von zur Gathen, Joachim and Shokrollahi, Amin and Shokrollahi, Jamshid},
   booktitle   = {International {W}orkshop on the {A}rithmetic of {F}inite
                 {F}ields, {WAIFI} 2007},
   details     = {http://infoscience.epfl.ch/record/112310},
   documenturl = {http://infoscience.epfl.ch/record/112310/files/WaiFi-Final.pdf},
   keywords    = {Finite field arithmetic; optimal normal bases;
                 asymptotically fast algorithms; algoweb_numbertheory},
   location    = {Madrid},
   oai-id      = {oai:infoscience.epfl.ch:112310},
   oai-set     = {conf},
   pages       = {55--68},
   publisher   = { },
   review      = {REVIEWED},
   series      = { },
   status      = {PUBLISHED},
   title       = {Efficient multiplication using type $2$ optimal normal bases},
   unit        = {ALGO},
   url         = { },
   year        = 2007
}