## Abstract

Gauss periods yield (self-dual) normal bases in finite fields, and these normal bases can be used to implement arithmetic efficiently. It is shown that for a small prime power q and infinitely many integersn , multiplication in a normal basis of Fqn over Fq can be computed with O(n logn loglog n), division with O(n log^{2}n loglog n) operations in Fq, and exponentiation of an arbitrary element in Fqn withO (n^{2}loglog n) operations in Fq. We also prove that using a polynomial basis exponentiation in F 2 n can be done with the same number of operations in F 2 for all n. The previous best estimates were O(n^{2}) for multiplication in a normal basis, andO (n^{2}log n loglog n) for exponentiation in a polynomial basis.

Original language | English (US) |
---|---|

Pages (from-to) | 879-889 |

Number of pages | 11 |

Journal | Journal of Symbolic Computation |

Volume | 29 |

Issue number | 6 |

DOIs | |

State | Published - Jun 2000 |

## ASJC Scopus subject areas

- Algebra and Number Theory
- Computational Mathematics