Rigorous Analysis of a Randomised Number Field Sieve

Preprint English OPEN
Lee, Jonathan; Venkatesan, Ramarathnam;
(2018)

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 anal... View more
  • References (27)
    27 references, page 1 of 3

    φ(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,

  • Similar Research Results (1)
  • Metrics
Share - Bookmark