Cyclic Vector Multiplication Algorithm Based on a Special Class of Gauss Period Normal Basis
Hidehiro Kato, Yasuyuki Nogami, Tomoki Yoshida, Yoshitaka Morikawa · ETRI Journal · 2007
This paper proposes a multiplication algorithm for , which can be efficiently applied to many pairs of characteristic p and extension degree m except for the case that 8p divides m(p–1). It uses a special class of type-⟨k, m⟩ Gauss period normal bases. This algorithm has several advantages: it is easily parallelized; Frobenius mapping is easily carried out since its basis is a normal basis; its calculation cost is clearly given; and it is sufficiently practical and useful when parameters k and m are small.