Normal Elliptic Bases
and Torus-Based Cryptography.
In Daniel Panario Gary McGuire, Gary L. Mullen and Igor E.
Shparlinski, editors, Finite Fields: Theory and Applications,
Contemporary Mathematics, pages 137-153. American Mathematical Society,
Ninth International Conference Finite Fields and Applications..
We consider representations of algebraic tori Tn(Fq)
over finite fields. We make use of normal elliptic bases to
show that, for infinitely many squarefree integers n and
infinitely many values of q, we can encode m torus
elements, to a small fixed overhead and to m
φ(n)-tuples of Fq elements, in quasi-linear
time in logq. This improves upon previously known
algorithms, which all have a quasi-quadratic complexity. As
a result, the cost of the encoding phase is now negligible
in Diffie-Hellman cryptographic schemes.
[ bib |