Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Applicable Algebra in Engineering, Communication and Computing
Erschienen in: Applicable Algebra in Engineering, Communication and Computing 4/2023

16.09.2021 | Original Paper

Deterministic factoring with oracles

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

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 4/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.
Vorheriger Artikel A new algorithm for equivalence of cyclic codes and its applications
Nächster Artikel Several classes of p-ary linear codes with few weights

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
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
2.
3.
4.
Bach, E., Miller, G.L., Shallit, J.O.: Sums of divisors, perfect numbers and factoring. SIAM J. Comput. 15(4), 1143–1154 (1986)MathSciNetCrossRefMATH
5.
6.
Bernstein, D.J., Lenstra, H.W., Pila, J.: Detecting perfect powers by factoring into coprimes. Math. Comput. 76(257), 385–388 (2007)MathSciNetCrossRefMATH
7.
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)
8.
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)
9.
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.
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.
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.
25.
26.
27.
28.
Hittmeir, M.: A Babystep-Giantstep method for faster deterministic integer factorization. Math. Comput. 87(314), 2915–2935 (2018)MathSciNetCrossRefMATH
29.
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.
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.
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.
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.
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.
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.
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.
54.
55.
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
Metadaten
Titel
Deterministic factoring with oracles
verfasst von
François Morain
Guénaël Renault
Benjamin Smith
Publikationsdatum
16.09.2021
Verlag
Springer Berlin Heidelberg
Erschienen in
Applicable Algebra in Engineering, Communication and Computing / Ausgabe 4/2023
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-021-00521-8

Weitere Artikel der Ausgabe 4/2023

Applicable Algebra in Engineering, Communication and Computing 4/2023 Zur Ausgabe

Original Paper

A new algorithm for equivalence of cyclic codes and its applications

Original Paper

Several classes of p-ary linear codes with few weights

Original Paper

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

Original Paper

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

Original Paper

Rational homotopy theory methods in graph theory

Original Paper

Integration in finite terms: dilogarithmic integrals

Premium Partner

    Bildnachweise