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

被引：53

作者：

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 [J].

BERKOWITZ, SJ .

INFORMATION PROCESSING LETTERS, 1984, 18 (03) :147-150

[5] The Magma algebra system .1. The user language [J].

Bosma, W ;

Cannon, J ;

Playoust, C .

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 [J].

CANTOR, DG ;

KALTOFEN, E .

ACTA INFORMATICA, 1991, 28 (07) :693-701

[8]

CARTIER P, 1957, CR HEBD ACAD SCI, V244, P426

[9] MATRIX MULTIPLICATION VIA ARITHMETIC PROGRESSIONS [J].

COPPERSMITH, D ;

WINOGRAD, S .

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 →