Deterministic Integer Factorization with Oracles for Euler's Totient Function

• Autorzy: Hittmeir Markus , Pomykała Jacek

Identyfikatory

DOI

10.3233/FI-2020-1891

• Języki publikacji: EN

Abstrakty

EN

In this paper, we construct deterministic factorization algorithms for natural numbers N under the assumption that the prime power decomposition of Euler’s totient function φ (N ) is known. Their runtime complexities depend on the number ω (N ) of distinct prime divisors of N , and we present efficient methods for relatively small values of ω (N ) as well as for its large values. One of our main goals is to establish an asymptotic expression with explicit remainder term O (x /A ) for the number of positive integers N ≤ x composed of s distinct prime factors that can be factored nontrivially in deterministic time t = t (x ), provided that the prime power decomposition of φ (N ) is known. We obtain it for A = A (x ) = x ^1–ɛ , where ɛ = ɛ (s ) > 0 is sufficiently small and t = t (x ) is a polynomial in log x of degree d = d (ɛ ). An analogous bound is deduced under the assumption of the oracle providing the decomposition of orders of elements in ℤ_N *.

Słowa kluczowe

EN

deterministic reduction; factorization; totient function

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 172, nr 1
• Strony: 39--51
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Hittmeir Markus

• SBA Research, Floragasse 7, 1040 Vienna, Austria

autor

Pomykała Jacek

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

Bibliografia

• [1] Riesel H. Prime Numbers and Computer Methods for Factorization. Birkhäuser Boston, Progress in Mathematics (Vol. 126), 1994. 2nd Edition. ISBN-0-8176-3743-5.
• [2] Crandall R, Pomerance C. Prime Numbers, A Computational Perspective. Springer-Verlag, New York, 2001. 2nd Edition. ISBN-978-0-387-28979-3.
• [3] Hittmeir M. A babystep-giantstep method for faster deterministic integer factorization. Math. Comp., 2018. 87(314):2915-2935. doi:10.1090/mcom/3313.
• [4] Hafner JL, McCurley KS. On the distribution of running times of certain integer factoring algorithms. J. Algorithms, 1989. 10(4):531-556. doi:10.1016/0196-6774(89)90004-7.
• [5] Adleman LM, McCurley KS. Open Problems in number theoretic complexity, Discrete Algorithms and Complexity. In: Proceedings of the Japan-US Joint Seminar 1986, Kyoto, Japan, Academic Press. 1987 pp. 237-262.
• [6] Adleman LM, McCurley KS. Open problems in number theoretic complexity II. In: Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA, Springer-Verlag. 1994 pp. 291-322. doi:10.1007/3-540-58691-1_70.
• [7] Morain F, Renault G, Smith B. Deterministic factoring with oracles. https://hal.inria.fr/hal-01715832/document, Preprint, 2018. ArXiv: 1802.08444.
• [8] Durnoga K, Pomykała J. Large sieve, Miller-Rabin compositeness witnesses and integer factoring problem. Fundam. Inform., 2017. 156:179-185. doi:10.3233/FI-2017-1603.
• [9] Dryło R, Pomykała J. Factoring n and the number of points of Kummer hypersurfaces mod n. In: Number-Theoretic Methods in Cryptology, J. Kaczorowski, J. Pieprzyk, J. Pomykała (Eds.), LNCS 10737, Springer-Verlag. 2018 pp. 163-177. doi:10.1007/978-3-319-76620-1_10.
• [10] Źrałek B. A deterministic version of Pollard’s P-1 algorithm. Math. Comp., 2010. 79(269):513-533. doi:10.1090/S0025-5718-09-02262-5.
• [11] Źrałek B. An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient. Math. Comp., to appear.
• [12] Martin G. The least prime primitive root and the shifted sieve. Acta Arith., 1997. 80(3):277-288. doi:10.4064/aa-80-3-277-288.
• [13] Hittmeir M. Deterministic factorization of sums and differences of powers. Math. Comp., 2017. 86(308):2947-2954. doi:10.1090/mcom/3197.
• [14] Harvey D, v d Hoeven J, Lecerf G. Even faster integer multiplication. J. Complexity, 2016. 36:1-30. doi:10.1016/j.jco.2016.03.001.
• [15] 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.
• [16] Menezes AJ, van Oorschot PC, Vanstone SA. Handbook of Applied Cryptography. CRC Press LLC, Boca Raton, Florida, USA, 1997. ISBN-0-8493-8523-7.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).