β Scribed by Shuhong Gao; Joachim Von zur gathen; Daniel Panario; Victor Shoup
No coin nor oath required. For personal study only.
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 integers n, multiplication in a normal basis of F q n over Fq can be computed with O(n log n loglog n), division with O(n log 2 n loglog n) operations in Fq, and exponentiation of an arbitrary element in F q n with O(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, and O(n 2 log n log log n) for exponentiation in a polynomial basis.
π SIMILAR VOLUMES
By means of GrΓΆbner basis techniques algorithms for solving various problems concerning subfields K (g) := K (g 1 , . . . , gm) of a rational function field K (x) := K (x 1 , . . . , xn) are derived: computing canonical generating sets, deciding field membership, computing the degree and separabilit