TY - JOUR
T1 - Algorithms for Exponentiation in Finite Fields
AU - Gao, Shuhong
AU - Von Zur Gathen, Joachim
AU - Panario, Daniel
AU - Shoup, Victor
PY - 2000/6
Y1 - 2000/6
N2 - 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 log2n loglog n) operations in Fq, and exponentiation of an arbitrary element in Fqn withO (n2loglog 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(n2) for multiplication in a normal basis, andO (n2log n loglog n) for exponentiation in a polynomial basis.
AB - 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 log2n loglog n) operations in Fq, and exponentiation of an arbitrary element in Fqn withO (n2loglog 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(n2) for multiplication in a normal basis, andO (n2log n loglog n) for exponentiation in a polynomial basis.
UR - http://www.scopus.com/inward/record.url?scp=0000185837&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0000185837&partnerID=8YFLogxK
U2 - 10.1006/jsco.1999.0309
DO - 10.1006/jsco.1999.0309
M3 - Article
AN - SCOPUS:0000185837
SN - 0747-7171
VL - 29
SP - 879
EP - 889
JO - Journal of Symbolic Computation
JF - Journal of Symbolic Computation
IS - 6
ER -