On Deterministic Reduction of Factoring Integers to Computing the Exponents of Elements in Modular Group

• Autorzy: Pomykała J.

Identyfikatory

DOI

10.3233/FI-2017-1521

• Języki publikacji: EN

Abstrakty

EN

In the paper we prove that all but at most x/A(x) positive integers n ≤ x can be completely factored in deterministic polynomial time C(x), querying the prime decomposition exponent oracle at most D(x) times. The functions A(x), C(x) and D(x) have the polynomial growth (of log x) at infinity.

Słowa kluczowe

EN

Brun-Titchmarsh inequality; Dirichlet character; discrete logarithm problem for composite numbers; factoring algorithm; smooth numbers; Zn-generating sets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 152, nr 3
• Strony: 289--295
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Pomykała J.

• Institute of Mathematics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland

Bibliografia

• [1] Bach E. Discrete logarithms and factoring, Technical report UCB/CSD-84-186, EECS Department, University of California, Berkeley. URL http:// www.eecs.berkeley.edu/Pubs/TechRpts/1984/5973.html.
• [2] Bach E, Shallit J. Algorithmic Number Theory, The MIT Press, 1996, Cammbridge, Massachusetts, London, England. ISBN-13: 978-0262024051, 10: 0262024055.
• [3] Bondaryk K, Pomykała J. New Challenges for Polish Cryptology in Second Decade of XXI Century (in Polish), in: Conception of National Cryptology and Cybersecurity Policy, National Security Studies, 2014;6:19-33.
• [4] Conrey JB. Problem 8 in: Future directions in algorithmic number theory, The American Institute of Mathematics, 2003, URL http://aimath.org/WWN/primesinp/.
• [5] Durnoga K, Źrałek B. On Computing Discrete Logarithms in Bulk and Randomness Extractors, Fundamenta Informaticae, 2014;141(4):345-366. doi:10.3233/FI-2015-1279.
• [6] Fellows MR, Koblitz N. Self-witnessing polynomial-time complexity and prime factorization, Designs, Codes and Cryptography, 1992;2(3):231–235. doi:10.1109/SCT.1992.215385.
• [7] Konyagin S, Pomerance C. On primes recognizable in deterministic polynomial time, in: The mathematics of Paul Erdos, R. L. Graham and J. Nesetril (eds.), Springer-Verlag, 1997, pp. 176–198. doi:10. 1007/978-3-642-60408-9_15.
• [8] Lenstra HW, Jr., Pomerance C. Primality testing with Gaussian periods, in: Manuscript, math.dartmouth.edu/carlp, 2005. - See more at: URL http://www.ams.org/journals/mcom/2015-84-291/S0025-5718-2014-02840-8/#sthash.kmasMqnp.dpuf.
• [9] Pomykała J. Small generating sets and DLPC problem, Fundamenta Informaticae, 2016;145(2):143–150. doi:10.3233/FI-2016-1351.
• [10] Pomykała J. On exponents of modular subgroups generated by small consecutive integers, Acta Arithmetica, 2016;176.4:321–342. doi:10.4064/aa8255-8-2016.
• [11] Pomykała J, Źrałek B. On reducing factorization to the discrete logarithm problem modulo a composite, Comput. Complex 2012;21(3):421–429. doi:10.1007/s00037-012-0037-5.
• [12] Prachar K. Primzahlverteilung, Springer-Verlag, Berlin-Gottingen-Heidelberg, 1957.