Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings

被引：0

作者：

Busch, J. ^{[1
]}

机构：

[1] Archer Sch Girls, Dept Math, Los Angeles, CA 90049 USA

来源：

JOURNAL OF SYMBOLIC COMPUTATION | 2009年 / 44卷 / 06期

基金：

美国国家科学基金会;

关键词：

Arithmetic complexity; Computational complexity; Coprimality; Eisenstein integers; Gaussian integers; gcd; Lower bounds; ALGORITHM; GCD; COMPUTATIONS;

D O I：

10.1016/j.jsc.2008.11.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove lower bounds for the complexity of deciding several relations in imaginary, norm-Euclidean quadratic integer rings, where computations are assumed to be relative to a basis of piecewise-linear operations. In particular, we establish lower bounds for deciding coprimality in these rings, which yield lower bounds for gcd computations. In each imaginary, norm-Euclidean quadratic integer ring, a known binary-like gcd algorithm has complexity that is quadratic in our lower bound. (C) 2008 Elsevier Ltd. All rights reserved.

引用

页码：683 / 699

页数：17

共 15 条

[1] Agarwal S, 2004, LECT NOTES COMPUT SC, V3076, P57
[2] Busch J, 2007, FUND INFORM, V76, P1
[3] BUSCH J, 2008, THESIS U CALIFORNIA
[4] Discrete Logarithms in GF(p)
Coppersmith, Don
Odlzyko, Andrew M.
Schroeppel, Richard
[J]. ALGORITHMICA, 1986, 1 (1-4) : 1 - 15
[5] Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers
Damgård, IB
Frandsen, GS
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 2005, 39 (06) : 643 - 652
[6] Lamacchia B. A., 1991, Designs, Codes and Cryptography, V1, P47, DOI 10.1007/BF00123958
[7] A LOWER BOUND FOR INTEGER GREATEST COMMON DIVISOR COMPUTATIONS
MANSOUR, Y
SCHIEBER, B
TIWARI, P
[J]. JOURNAL OF THE ACM, 1991, 38 (02) : 453 - 471
[8] LOWER BOUNDS FOR COMPUTATIONS WITH THE FLOOR OPERATION
MANSOUR, Y
SCHIEBER, B
TIWARI, P
[J]. SIAM JOURNAL ON COMPUTING, 1991, 20 (02) : 315 - 327
[9] LOWER BOUNDS FOR ARITHMETIC PROBLEMS
MEIDANIS, J
[J]. INFORMATION PROCESSING LETTERS, 1991, 38 (02) : 83 - 87
[10] Moschovakis YN, 2005, LECT NOTES COMPUT SC, V3526, P350

← 1 2 →