publication . Article . Preprint . 2018

Rigorous analysis of a randomised number field sieve

Lee, Jonathan; Venkatesan, Ramarathnam;
Open Access
  • Published: 22 May 2018 Journal: Journal of Number Theory, volume 187, pages 92-159 (issn: 0022-314X, Copyright policy)
  • Publisher: Elsevier BV
Abstract
Abstract Factorisation of integers n is of number theoretic and cryptographic significance. The Number Field Sieve (NFS) introduced circa 1990, is still the state of the art algorithm, but no rigorous proof that it halts or generates relationships is known. We propose and analyse an explicitly randomised variant. For each n, we show that these randomised variants of the NFS and Coppersmith's multiple polynomial sieve find congruences of squares in expected times matching the best-known heuristic estimates.
Subjects
free text keywords: Algebra and Number Theory, Sieve, law.invention, law, Mathematics, Factorization, Heuristic, Integer, Congruence relation, Polynomial, Discrete mathematics, Algebra, General number field sieve, Coppersmith, people.profession, people, Mathematics - Number Theory, 11Y05
Related Organizations
27 references, page 1 of 2

φ(q) [1] Leonard M. Adleman. Factoring numbers using singular integers. In Proceedings of the Twenty-third Annual ACM

Symposium on Theory of Computing, STOC '91, pages 64-71, New York, NY, USA, 1991. ACM. [2] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. Primes is in P. Ann. of Math, 2:781-793, 2002. [3] E. Artin. Quadratische ko¨rper im gebiete der h¨oheren kongruenzen. i, ii. (analytischer teil.). Mathematische Zeitschrift,

19:153-246, 1924. [4] P. Balister, B. Bollob´as, and R. Morris. The sharp threshold for making squares. ArXiv e-prints, August 2016. [5] Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, and Emmanuel Thom´e. A heuristic quasi-polynomial algorithm for

discrete logarithm in finite fields of small characteristic. In Advances in Cryptology-Eurocrypt 2014, pages 1-16. Springer,

2014. [6] Joe P. Buhler, Jr. Hendrik W. Lenstra, and Carl Pomerance. Factoring integers with the number field sieve. In A. K.

Lenstra and H. W. Lenstra, Jr., editors, The development of the number field sieve, number 1554 in Lecture Notes in

Mathematics, pages 50-94. Springer-Verlag, 1993. [7] E.R Canfield, Paul Erd˝os, and Carl Pomerance. On a problem of Oppenheim concerning “factorisatio numerorum”.

Journal of Number Theory, 17(1):1-28, 1983. [8] A.C. Cojocaru, R. Murty, and London Mathematical Society. An Introduction to Sieve Methods and Their Applications.

London Mathematical Society Student Texts. Cambridge University Press, 2006. [9] Don Coppersmith. Modifications to the number field sieve. Journal of Cryptology, 6(3):169-180, 1993. [10] Ernie Croot, Andrew Granville, Robin Pemantle, and Prasad Tetali. On sharp transitions in making squares. Ann. Math.

(2), 175(3):1507-1550, 2012. [11] John D. Dixon. Asymptotically Fast Factorization of Integers. Mathematics of Computation, 36:255-260, 1981. [12] Sary Drappeau. Propri´et´es multiplicatives des entiers friables translat´es. Colloq. Math, 137:149-164, 2014. [13] Sary Drappeau. Th´eor`emes de type Fouvry-Iwaniec pour les entiers friables. Compos. Math., forthcoming. [14] Andrew Granville. Integers, without large prime factors, in arithmetic progressions. I. Acta Mathematica, 170:255-273,

1993. [15] Andrew Granville. Integers, without large prime factors, in arithmetic progressions. II. Philosophical Transactions of the [OpenAIRE]

Royal Society of London Series A, 345:349-362, 1993. [16] Andrew Granville and K. Soundararajan. Large character sums. J. Amer. Math. Soc., 14(2):365-397, 2001. [17] A. J. Harper. Bombieri-Vinogradov and Barban-Davenport-Halberstam type theorems for smooth numbers. ArXiv

e-prints, August 2012. [18] Adam J. Harper. On a paper of K. Soundararajan on smooth numbers in arithmetic progressions. Journal of Number

Theory, 132(1):182 - 199, 2012. [19] Adolf Hildebrand. Integers free of large prime divisors in short intervals. Quarterly Journal of Mathematics, 36:57-69,

1985. [20] Adolf Hildebrand. On the number of positive integers ≤ x and free of prime factors > y. Journal of Number Theory,

27 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Article . Preprint . 2018

Rigorous analysis of a randomised number field sieve

Lee, Jonathan; Venkatesan, Ramarathnam;