Gashkov S.,Moscow State University |
Frolov A.,Moscow Power Engineering Institute |
Sergeev I.,Research Development Institute Kvant
Advances in Intelligent Systems and Computing | Year: 2016
In this paper, we generalize an approach of switching between different bases of a finite field to efficiently implement distinct stages of algebraic algorithms. We consider seven bases of finite fields supporting optimal normal bases of types 2 and 3: polynomial, optimal normal, permuted, redundant, reduced, doubled polynomial, and doubled reduced bases. With respect to fields of characteristic q = 7 we provide complexity estimates for conversion between the bases, multiplication, and exponentiation to a power qk, q-th root extraction. These operations are basic for inversion and exponentiation in GF(7n). One needs a fast arithmetic; in GF(7n) for efficient computations in field extensions (72n), GF(73n), GF(76n)GF(714n), GF(73x14n) which are the core of the Tate pairing on a supersingular hyperelliptic curve of genus three. The latter serves for an efficient implementation of cryptographic protocols. © Springer International Publishing Switzerland 2016.