On the bounds of the bilinear complexity of multiplication in some finite fields

被引：8

作者：

Ballet, S ^{[1
]}

Chaumine, J ^{[1
]}

机构：

[1] Univ Polynesie Francaise, Lab Geometrie Algebr & Applicat Theorie Informat, BP 6570, Faaa 98702, Tahiti, France

来源：

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING | 2004年 / 15卷 / 3-4期

关键词：

bilinear complexity; finite fields; algebraic functions fields; algebraic curves;

D O I：

10.1007/s00200-004-0155-7

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

From the existence of a tower of algebraic function fields, we improve upper bounds on the bilinear complexity of multiplication in all the extensions of the finite fields F-p and F-p2 where p is a prime greater than or equal to 5. In particular, we improve asymptotic upper bounds on this complexity for prime finite fields of characteristic p > 5.

引用

页码：205 / 211

页数：7

共 11 条

[1] Multiplication algorithm in a finite field and tensor rank of the multiplication [J].

Ballet, R ;

Rolland, R .

JOURNAL OF ALGEBRA, 2004, 272 (01) :173-185

[2] Low increasing tower of algebraic function fields and bilinear complexity of multiplication in any extension of Fq [J].

Ballet, S .

FINITE FIELDS AND THEIR APPLICATIONS, 2003, 9 (04) :472-478

[3] Curves with many points and multiplication complexity in any extension of Fq [J].

Ballet, S .

FINITE FIELDS AND THEIR APPLICATIONS, 1999, 5 (04) :364-377

[4]

BALLET S, EXISTENCE NONSPECIAL

[5] CHARACTERIZATION OF DIVISION-ALGEBRAS OF MINIMAL RANK AND THE STRUCTURE OF THEIR ALGORITHM VARIETIES [J].

DEGROOTE, HF .

SIAM JOURNAL ON COMPUTING, 1983, 12 (01) :101-117

[6]

Garcia A, 2003, J REINE ANGEW MATH, V557, P53

[7] A new construction of algebraic-geometry codes [J].

Niederreiter, H ;

Xing, CP ;

Lam, KY .

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 1999, 9 (05) :373-381

[8] OPTIMAL-ALGORITHMS FOR MULTIPLICATION IN CERTAIN FINITE-FIELDS USING ELLIPTIC-CURVES [J].

SHOKROLLAHI, MA .

SIAM JOURNAL ON COMPUTING, 1992, 21 (06) :1193-1198

[9]

SHPARLINSKI IE, 1992, LECT NOTES MATH, V1518, P145

[10]

Stichtenoth H., 1993, LECT NOTES MATH, V314

← 1 2 →