Small Generating Sets and DLPC Problem

• Autorzy: Pomykała J.

Identyfikatory

DOI

10.3233/FI-2016-1351

• Języki publikacji: EN

Abstrakty

EN

In the paper we investigate the set of odd, squarefree positive integers n that can be factored completely in polynomial timeO(log^6+ε n), given the prime decomposition of orders ord_nb for b ≤ log^η n, (η > 2), which is closely related to DLPC problem. We prove that the number of n ≤ x that may not be factored in deterministic time O(log^6+εn), is at most (η - 2^)-1x(log x)^-c(η-2), for some c > 0 and arbitrary ε > 0.

Słowa kluczowe

EN

Dirichlet character; discrete logarithm problem for composite numbers; factoring algorithm; large sieve estimates; smooth numbers; Z* n-generating sets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 2
• Strony: 143--150
• Opis fizyczny: Bibliogr. 9 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. Available from: http://www.eecs.berkeley.edu/Pubs/TechRpts/1984/5973.html.
• [2] Pomykała J, Źrałek B. On reducing factorization to the discrete logarithm problem modulo a composite. Comput. Complex 21 (2012), 421–429.DOI: 10.1007/s00037-012-0037-5,Available from: http://dx.doi.org/10.1007/s00037-012-0037-5.
• [3] Pomykała J. On q-orders in primitive modular groups. Acta Arith. 166.4 (2014), 397–404.
• [4] Conrey JB. Problem 8 in: Future directions in algorithmic number theory. The American Institute of Mathematics, 2003. Available from: http://aimath.org/WWN/primesinp/.
• [5] Davenport H. Multiplicative Number Theory. Markham Publishing Company, Chicago 1967.
• [6] Montgomery HL. Topics in multiplicative number theory. Lecture Notes in Math. 227. Springer-Verlag, Berlin-New York, 1971.
• [7] Pomerance C, Konyagin S. On primes recognizable in deterministic polynomial time. in: The mathematics of Paul Erdos, R. L. Graham and J. Nesetril (eds.). Springer-Verlag, 1997, 176–198.
• [8] Lenstra HW Jr, Pomerance C. Primality testing with Gaussian periods. in: Manuscript, math.dartmouth.edu/carlp, 2005. Available from: http://www.ams.org/journals/mcom/2015-84-291/S0025-5718-2014-02840-8/#sthash.kmasMqnp.dpuf
• [9] Źrałek B. A deterministic version of Pollard’s p − 1 algorithm. Math. of Comp. 79 (2010), 513–533. DOI:10.1090/S0025-5718-09-02262-5, Available from: http://dx.doi.org/10.1090/S0025-5718-09-02262-5.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.