Abstract
We use pruned enumeration algorithms to find lattice vectors close to a specific target vector for the prime number lattice. These algorithms generate multiplicative prime number relations modulo N that factorize a given integer N. The algorithm New Enum performs the stages of exhaustive enumeration of close lattice vectors in order of decreasing success rate. For example an integer N ≈ 1014 can be factored by about 90 prime number relations modulo N for the 90 smallest primes. Our randomized algorithm generated for example 139 such relations in 15 minutes. This algorithm can be further optimized. The optimization for larger integers N is still open.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L.A.: Factoring and lattice reduction. Manuscript (1995)
Babai, L.: On Lovász lattice reduction and the nearest lattice point problem. Combinatorica 6 (1), 1–13 (1986)
Buchmann, J., Ludwig, C.: Practical lattice basis sampling reduction. eprint.iacr.org, TR 072 (2005)
Charlet, M.: Faktorisierung ganzer Zahlen mit dem NEW ENUM-Gitteralgorithmus. Diplomarbeit, Frankfurt (2013)
Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. of Comput. 44, 463–471 (1985)
Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008)
Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme pruning. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 257–278. Springer, Heidelberg (2010)
Granville, A.: Smooth numbers: computational number theory and beyond. Algorithmic Number Theory 44, 267–323 (2008)
Hildebrand, A.: Integers free of large prime factors and the Riemann hypothesis. Mathematika 31, 258–271 (1984)
Hirschhorn, P.S., Hoffstein, J., Howgrave-Graham, N., Whyte, W.: Choosing NTRUEncrypt parameters in light of combined lattice reduction and MITM approaches. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 437–455. Springer, Heidelberg (2009)
Howgrave-Graham, N.: A hybrid lattice–reduction and meet-in-the-middle attiack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 150–169. Springer, Heidelberg (2007)
Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12, 415–440 (1987)
Lange, B.: Neue Schranken für SVP-Approximation und SVP-Algorithmen. Dissertation, Frankfurt (2013)
Lenstra Jr., H.W., Lenstra, A.K., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515–534 (1982)
lOVász, L.: An Algorithmic Theory of Numbers, Graphs and Convexity. SIAM (1986)
Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: A Cryptographic Perspective. Kluwer Academic Publishers, Boston (2002)
Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. ECCC Report No. 65 (2009)
Nguyen, P.Q.: Hermite’s Constant and Lattice Algorithms. In: Nguyen, P.Q., Vallée, B. (eds.) The LLL Algorithm. Springer (January 2010)
Schnorr, C.P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53, 201–224 (1987)
Schnorr, C.-P.: Factoring integers and computing discrete logarithms via Diophantine approximation. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 281–293. Springer, Heidelberg (1991)
Schnorr, C.P., Euchner, M.: Lattce basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical Programming 66, 181–199 (1994), http://www.mi.informatik.uni-frankfurt.de/
Schnorr, C.-P., Hörner, H.H.: Attacking the Chor–Rivest cryptosystem by improved lattice reduction. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 1–12. Springer, Heidelberg (1995)
Schnorr, C.P.: Lattice reduction by sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 145–156. Springer, Heidelberg (2003), www.mi.informatik.uni-frankfurt.de
Schnorr, C.P.: Progress on LLL and lattice reduction. In: Phong, P.Q., Vallée, B. (eds.) Proceedings LLL+25, Caen, France, June 29-July 1. The LLL Algorithm (2007), www.mi.informatik.uni-frankfurt.de/
Schnorr, C.P.: Average Time Fast SVP and CVP Algorithms for Low Density Lattices and the Factorisation of Integers (2010), www.mi.informatik.uni-frankfurt.de
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Schnorr, C.P. (2013). Factoring Integers by CVP Algorithms. In: Fischlin, M., Katzenbeisser, S. (eds) Number Theory and Cryptography. Lecture Notes in Computer Science, vol 8260. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-42001-6_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-42001-6_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-42000-9
Online ISBN: 978-3-642-42001-6
eBook Packages: Computer ScienceComputer Science (R0)