OPTIMAL-ALGORITHMS FOR MULTIPLICATION IN CERTAIN FINITE-FIELDS USING ELLIPTIC-CURVES

被引：25
作者：
SHOKROLLAHI, MA
机构：
来源：
SIAM JOURNAL ON COMPUTING | 1992年 / 21卷 / 06期
关键词：
ELLIPTIC CURVES; BILINEAR COMPLEXITY; FINITE FIELDS;
D O I：
10.1137/0221071
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Using the results given in [D. V Chudnovsky and G. V Chudnovsky, Proc. Nat. Acad. Sci. USA, 84 (1987), pp. 1739-17431 and [W. C. Waterhouse, Ann. Sci. Ecole Norm. Sup., 4 (1969), pp. 521-560], it is proven that the rank (=bilinear complexity of multiplication) of the finite field F(qn) viewed as an F(q)-algebra is 2n if n satisfies 1/2q + 1 < n < 1/2(q + 1 + epsilon(q)). Here epsilon(q) is the greatest integer less-than-or-equal-to 2 square-root q, which is prime to q if q is not a perfect square and epsilon(q) = 2 square-root q if q is a perfect square.
引用
收藏
页码：1193 / 1198
页数：6
相关论文
共 11 条
[1]  
ARTIN E, 1977, ALGEBRAIC NUMBERS AL
[2]  
CHEVALLEY C, 1958, INTRO ALGEBRAIC FUNC
[3]   ALGEBRAIC COMPLEXITIES AND ALGEBRAIC-CURVES OVER FINITE-FIELDS [J].
CHUDNOVSKY, DV ;
CHUDNOVSKY, GV .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1987, 84 (07) :1739-1743
[4]  
CHUDNOVSKY DV, 1987, RC12065 IBM RES CTR
[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]  
DEGROOTE HF, 1985, LECTURE NOTES COMPUT, V245
[7]  
DEURING M, 1973, LECTURE NOTES MATH, V314
[8]  
HAASE H, 1933, NACHR MATH GESELLSCH, V3, P253
[9]  
SILVERMAN J, 1986, ARITHMETIC ELLIPTIC
[10]  
Winograd S., 1979, Theoretical Computer Science, V8, P359, DOI 10.1016/0304-3975(79)90017-3
12