Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1990 Copyright 1990 University of Bonn, Department of Computer Science, Abt. V
8553

08.01.2009

Optimal Algorithms for Multiplication in certain Finite Fields using Ellipctic Curves
Mohammad Amin Shokrollahi
[Download PostScript] [Download PDF]

Using results of D.V.Chudnowsky, G.V.Chudnowsky [3] and W.C.Waterhouse [10] we prove that the rank (=bilinear complexity of multiplication) of the finite field Fqn viewed as an Fq-algebra is 2n if n satisfies q/2 + 1 < n < (q + 1 + ε(q))/2. Here ε(q) is the greatest integer ≤ 2q1/2 which is prime to q if q is not a perfect square and ε(q) = 2q1/2 if q is a perfect square.

Last Change: 01/08/09 at 14:18:56
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V