Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator

被引：52

作者：

Bostan, Alin ^{[1
]}

Gaudry, Pierrick ^{[1
]}

Schost, Eric ^{[1
]}

机构：

[1] Ecole Polytech, Lab Informat LIX, F-91128 Palaiseau, France

来源：

SIAM JOURNAL ON COMPUTING | 2007年 / 36卷 / 06期

关键词：

linear recurrences; factorization; Cartier-Manin operator;

D O I：

10.1137/S0097539704443793

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the complexity of computing one or several terms (not necessarily consecutive) in a recurrence with polynomial coefficients. As applications, we improve the best currently known upper bounds for factoring integers deterministically and for computing the Cartier-Manin operator of hyperelliptic curves.

引用

页码：1777 / 1806

页数：30

共 43 条

[1] [Anonymous], 2003, ISSAC 2003 P 2003 IN, DOI DOI 10.1145/860854.860870
[2] [Anonymous], 1956, Appl. Sci. Res. B
[3] [Anonymous], ACT C INT MATH 1970
[4] ON COMPUTING THE DETERMINANT IN SMALL PARALLEL TIME USING A SMALL NUMBER OF PROCESSORS
BERKOWITZ, SJ
[J]. INFORMATION PROCESSING LETTERS, 1984, 18 (03) : 147 - 150
[5] The Magma algebra system .1. The user language
Bosma, W
Cannon, J
Playoust, C
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 1997, 24 (3-4) : 235 - 265
[6] Bostan A, 2004, LECT NOTES COMPUT SC, V2948, P40
[7] ON FAST MULTIPLICATION OF POLYNOMIALS OVER ARBITRARY ALGEBRAS
CANTOR, DG
KALTOFEN, E
[J]. ACTA INFORMATICA, 1991, 28 (07) : 693 - 701
[8] CARTIER P, 1957, CR HEBD ACAD SCI, V244, P426
[9] MATRIX MULTIPLICATION VIA ARITHMETIC PROGRESSIONS
COPPERSMITH, D
WINOGRAD, S
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 1990, 9 (03) : 251 - 280
[10] Flajolet P., 1997, SIGSAM Bulletin, V31, P36, DOI 10.1145/274888.274890

← 1 2 3 4 5 →