Top

Applicable Algebra in Engineering, Communication and Computing

Published in:

16-09-2021 | Original Paper

Deterministic factoring with oracles

Authors: François Morain, Guénaël Renault, Benjamin Smith

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 4/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Can we factor an integer \(N\) unconditionally, in deterministic polynomial time, given the value of its Euler totient \(\varphi (N)\)? We show that this can be done under certain size conditions on the prime factors of \(N\). The key technique is lattice basis reduction using the LLL algorithm. Among our results, we show that if \(N\) has a prime factor \(p > \sqrt{N}\), then we can recover \(p\) in deterministic polynomial time given \(\varphi (N)\). We also shed some light on the analogous factorization problems given oracles for the sum-of-divisors function, Carmichael’s function, and the order oracle that is used in Shor’s quantum factoring algorithm.

previous article A new algorithm for equivalence of cyclic codes and its applications

next article Several classes of p-ary linear codes with few weights

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Adleman, L.M., McCurley, K.S.: Open problems in number theoretic complexity, II. In: Adleman, L.M, Huang, M.-D. (eds.) Algorithmic Number Theory, pp. 291–322. Springer, Berlin Heidelberg (1994)CrossRef

Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Ann. Math. 160(2), 781–793 (2004)MathSciNetCrossRefMATH

Bach, E., Driscoll, J., Shallit, J.O.: Factor refinement. J. Algorithms 15, 199–222 (1993)MathSciNetCrossRefMATH

Bach, E., Miller, G.L., Shallit, J.O.: Sums of divisors, perfect numbers and factoring. SIAM J. Comput. 15(4), 1143–1154 (1986)MathSciNetCrossRefMATH

Bernstein, D.J.: Factoring into coprimes in essentially linear time. J. Algorithms 54, 1–30 (2005)MathSciNetCrossRefMATH

Bernstein, D.J., Lenstra, H.W., Pila, J.: Detecting perfect powers by factoring into coprimes. Math. Comput. 76(257), 385–388 (2007)MathSciNetCrossRefMATH

Blömer, J., May, A.: A tool kit for finding small roots of bivariate polynomials over the integers. In: Cramer, R. (eds) Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 2005, Proceedings, vol. 3494 of Lecture Notes in Computer Science, pp. 251–267. Springer (2005)

Boneh, D., Durfee, G., Howgrave-Graham, N.: Factoring \({N} = p^r q\) for large \(r\). In: Wiener, M.J. (ed) Advances in Cryptology - CRYPTO ’99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, 1999, Proceedings, vol. 1666 of Lecture Notes in Computer Science, pp. 326–337. Springer (1999)

Bostan, A., Gaudry, P., Schost, É.: Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator. SIAM J. Comput. 36(6), 1777–1806 (2007)MathSciNetCrossRefMATH

10.

Chow, A.: Applications of Fourier coefficients of modular forms. PhD thesis, University of Toronto, 2015. https://tspace.library.utoronto.ca/handle/1807/70815

11.

Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997)MathSciNetCrossRefMATH

12.

Coppersmith, D., Howgrave-Graham, N., Nagaraj, S.V.: Divisors in residue classes, constructively. Math. Comput. 77(261), 531–545 (2008)MathSciNetCrossRefMATH

13.

Coppersmith, D.: Finding a small root of a bivariate integer equation; factoring with high bits known. In: Maurer, U.M. (ed) Advances in Cryptology - EUROCRYPT ’96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, 1996, Proceeding, vol. 1070 of Lecture Notes in Computer Science, pp. 178–189. Springer (1996)

14.

Coppersmith, D.: Finding small solutions to small degree polynomials. In: Silverman, J.H. (ed) Cryptography and Lattices, International Conference, CaLC 2001, Providence, RI, USA, 2001, Revised Papers, vol. 2146 of Lecture Notes in Computer Science, pp. 20–31. Springer (2001)

15.

Coron, J.-S., May, A.: Deterministic polynomial-time equivalence of computing the RSA secret key and factoring. J. Cryptol. 20(1), 39–50 (2007)MathSciNetCrossRefMATH

16.

Coron, J.S., Faugère, J.C., Renault, G., Zeitoun, R.: Factoring \({N}=p^rq^s\) for large \(r\) and \(s\). In: Sako, K. (ed) Topics in Cryptology - CT-RSA 2016 - The Cryptographers’ Track at the RSA Conference 2016, San Francisco, CA, USA, 2016, Proceedings, vol. 9610 of Lecture Notes in Computer Science, pp. 448–464. Springer (2016)

17.

Coron, J.S.: Finding small roots of bivariate integer polynomial equations revisited. In: Cachin, C., Camenisch, J. (eds) Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, 2004, Proceedings, vol. 3027 of Lecture Notes in Computer Science, pp. 492–505. Springer (2004)

18.

Coron, J.O.: Finding small roots of bivariate integer polynomial equations: A direct approach. In: Menezes, A. (ed) Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, 2007, Proceedings, vol. 4622 of Lecture Notes in Computer Science, pp. 379–394. Springer (2007)

19.

Costa, E., Harvey, D.: Faster deterministic integer factorization. Math. Comput. 83(285), 339–345 (2014)MathSciNetCrossRefMATH

20.

Crandall, R., Pomerance, C.: Prime numbers: a computational perspective, 2nd edn. Springer, New York (2005)

21.

Donald KE.: The Art of Computer Programming: Seminumerical Algorithms, 3rd edn. Addison-Wesley, New York (1997)

22.

Erdős, P.: On the sum \(\sum ^x_{k=1} d(f(k))\). J. Lond. Math. Soc. 27, 7–15 (1952)MATH

23.

Faugère, J.C., Marinier R., Renault G.: Implicit factoring with shared most significant and middle bits. In: Nguyen, P.Q., Pointcheval, D. (eds) Public Key Cryptography - PKC 2010, 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, 2010. Proceedings, vol. 6056 of Lecture Notes in Computer Science, pp. 70–87. Springer (2010)

24.

Grosshans, F., Lawson, T., Smith, B., Morain, F.: Factoring safe semiprimes with a single quantum query (2016). https://arxiv.org/abs/1511.04385

25.

Harvey, D.: An exponent one-fifth algorithm for deterministic integer factorisation (2020). https://arxiv.org/abs/2010.05450

26.

Harvey, D., Hittmeir, M.: A log-log speedup for exponent one-fifth deterministic integer factorisation (2021). https://arxiv.org/abs/2105.11105

27.

Hendrik, W. Lenstra J.: Divisors in residue classes. Math. Comput. 42(165), 331–340 (1984)MathSciNetCrossRefMATH

28.

Hittmeir, M.: A Babystep-Giantstep method for faster deterministic integer factorization. Math. Comput. 87(314), 2915–2935 (2018)MathSciNetCrossRefMATH

29.

Hittmeir, M.: A time-space tradeoff for Lehman’s deterministic integer factorization method (2020). https://arxiv.org/abs/2006.16729

30.

Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited. In: Proceedings of the Cryptography and Coding, 6th IMA International Conference, Cirencester, UK, 1997, pp. 131–142 (1997)

31.

Jutla, C.J.: On finding small solutions of modular multivariate polynomial equations. In: Nyberg, K. (ed) Advances in Cryptology - EUROCRYPT ’98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, 1998, Proceeding, vol. 1403 of Lecture Notes in Computer Science, pp. 158–170. Springer (1998)

32.

Landau, S.: Some remarks on computing the square parts of integers. Inf. Comput. 78(3), 246–253 (1988)MathSciNetCrossRefMATH

33.

LeVeque, W.J.: Fundamentals of number theory. Dover, Downers Grove (1996)MATH

34.

Lehman, R.S.: Factoring large integers. Math. Comput. 28, 637–646 (1974)

35.

Lenstra, H.W., Jr.: Millers primality test. Inform. Process. Lett. 8(2), 86–88 (1979)MathSciNetCrossRefMATH

36.

Lenstra, A.K., Lenstra, H.W., Jr., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)MathSciNetCrossRefMATH

37.

Long, D.L.: Random equivalence of factorization and computation of orders. Technical Report 284, Princeton University, Depatment of Electrical Engineering and Computer Science (1981). http://www.lix.polytechnique.fr/Labo/Francois.Morain/Introuvables/long-orders.pdf

38.

Luca, F., Pomerance, C.: On the average number of divisors of the Euler function. Publ. Math. Debrecen 70(1–2), 125–148 (2007)MathSciNetCrossRefMATH

39.

May, A., Ritzenhofen, M.: Implicit factoring: On polynomial time factoring given only an implicit hint. In: Jarecki, S., Tsudik, G. (eds) Public Key Cryptography - PKC 2009, 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, CA, USA, 2009. Proceedings, vol. 5443 of Lecture Notes in Computer Science, pp. 1–14. Springer (2009)

40.

Miller, G.L.: Riemann’s hypothesis and tests for primality. In: Proceedings of the 7th STOC, pp. 234–239 (1975)

41.

Nguyen, P.Q., Stehlé, D.: An LLL algorithm with quadratic complexity. SIAM J. Comput. 39(3), 874–903 (2009)MathSciNetCrossRefMATH

42.

Nick, H.G.: Approximate integer common divisors. In: Silverman, J.H. (ed) Cryptography and Lattices, International Conference, CaLC 2001, Providence, RI, USA, 2001, Revised Papers, vol. 2146 of Lecture Notes in Computer Science, pp. 51–66. Springer (2001)

43.

Novocin, A., Stehlé, D., Villard, G.: An lll-reduction algorithm with quasi-linear time complexity: extended abstract. In: Fortnow, L., Vadhan, S.P. (eds) Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 2011, pp. 403–412. ACM (2011)

44.

Pollard, J.M.: Theorems on factorization and primality testing. Proc. Cambr. Philos. Soc. 76, 521–528 (1974)MathSciNetCrossRefMATH

45.

Rabin, M.O.: Digitalized signatures and public-key functions as intractable as factorization, Technical report. Massachusetts Institute of Technology, Cambridge (1979)

46.

Ritzhofen, M.: On efficiently calculating small solutions of systems of polynomial equations: lattice-based methods and applications to cryptography. PhD thesis, Ruhr University Bochum (2010)

47.

Rivest, R.L., Shamir, A.: Efficient factoring based on partial information. In: Pichler, F. (ed) Advances in Cryptology - EUROCRYPT ’85, Workshop on the Theory and Application of of Cryptographic Techniques, Linz, Austria, 1985, Proceedings, vol. 219 of Lecture Notes in Computer Science, pp. 31–34. Springer (1985)

48.

Sarkar, S., Maitra, S.: Further results on implicit factoring in polynomial time. Adv. Math. Commun. 3(2), 205–217 (2009)MathSciNetCrossRefMATH

49.

Sarkar, S., Maitra, S.: Approximate integer common divisor problem relates to implicit factorization. IEEE Trans. Inform. Theory 57(6), 4002–4013 (2011)MathSciNetCrossRefMATH

50.

Schorr, C.-P., Euchner, M.: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Lattice basis reduction. Math. Program. 66, 181–199 (1994)

51.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRefMATH

52.

von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 3rd edn. Cambridge University Press, Cambridge (2013)

53.

Wolke, D.: A new proof of a theorem of van der Corput. J. Lond. Math. Soc. 2(5), 609–612 (1972)MathSciNetCrossRefMATH

54.

Woll, H.: Reductions among number theoretic problems. Inform. Comput. 72, 167–179 (1987)MathSciNetCrossRefMATH

55.

Źrałek, B.: A deterministic version of Pollards p-1 algorithm. Math. Comput. 79(269), 513–533 (2010)MathSciNetCrossRefMATH

56.

Źrałek, B.: An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Eulers totient. Math. Comput. 88(317), 1261–1272 (2019)MathSciNetCrossRefMATH

Title: Deterministic factoring with oracles
Authors: François Morain
Guénaël Renault
Benjamin Smith
Publication date: 16-09-2021
Publisher: Springer Berlin Heidelberg
Published in: Applicable Algebra in Engineering, Communication and Computing / Issue 4/2023
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-021-00521-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2023

Special LCD codes from products of graphs

Using double Weil sums in finding the c-boomerang connectivity table for monomial functions on finite fields

On the security of DLCSP over

Integration in finite terms: dilogarithmic integrals

Multilinear algebra for minimum storage regenerating codes: a generalization of the product-matrix construction

Several classes of p-ary linear codes with few weights

Premium Partner