A HYPERELLIPTIC SMOOTHNESS TEST .1.

被引：23

作者：

LENSTRA, HW ^{[1
]}

PILA, J ^{[1
]}

POMERANCE, C ^{[1
]}

机构：

[1] UNIV GEORGIA, DEPT MATH, ATHENS, GA 30602 USA

来源：

PHILOSOPHICAL TRANSACTIONS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES | 1993年 / 345卷 / 1676期

关键词：

D O I：

10.1098/rsta.1993.0138

中图分类号：

O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

This series of papers is concerned with a probabilistic algorithm for finding small prime factors of an integer, While the algorithm is not practical, it yields an improvement over previous complexity results. The algorithm uses the jacobian varieties of curves of genus 2 in the same way that the elliptic curve method uses elliptic curves, In this first paper in the series a new density theorem is presented for smooth numbers in short intervals. It is a key ingredient of the analysis of the algorithm.

引用

页码：397 / 408

页数：12

共 18 条

[1]

BALOG A, 1987, ASTERISQUE, P27

[2] ON A PROBLEM OF OPPENHEIM CONCERNING FACTORISATIO NUMERORUM [J].

CANFIELD, ER ;

ERDOS, P ;

POMERANCE, C .

JOURNAL OF NUMBER THEORY, 1983, 17 (01) :1-28

[3]

FRIEDLANDER JB, 1976, P LOND MATH SOC, V33, P565

[4] SHORT INTERVALS CONTAINING NUMBERS WITHOUT LARGE PRIME FACTORS [J].

HARMAN, G .

MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1991, 109 :1-5

[5] FACTORING INTEGERS WITH ELLIPTIC-CURVES [J].

LENSTRA, HW .

ANNALS OF MATHEMATICS, 1987, 126 (03) :649-673

[6]

LENSTRA HW, 1992, J AM MATH SOC, V5, P483, DOI DOI 10.2307/2152702

[7] THEOREMS ON FACTORIZATION AND PRIMALITY TESTING [J].

POLLARD, JM .

PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1974, 76 (NOV) :521-528

[8]

POMERANCE C, 1982, MATH CENTRUM TRACT, V154, P89

[9]

Pomerance C., 1987, DISCRETE ALGORITHMS, P119

[10] INTEGERS FREE OF LARGE AND SMALL PRIME FACTORS .1. [J].

SAIAS, E .

ACTA ARITHMETICA, 1992, 61 (04) :347-374

← 1 2 →