Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1990 Copyright 1990 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope