Large Sieve, Miller-Rabin Compositeness Witnesses and Integer Factoring Problem

• Autorzy: Durnoga K. , Pomykała J.

Identyfikatory

DOI

10.3233/FI-2017-1603

• Języki publikacji: EN

Abstrakty

EN

G. Miller in his seminal paper from the mid 1970s has proven that the problem of factoring integers reduces to computing Euler’s totient function Φ under the Extended Riemann Hypothesis. We show, unconditionally, that such a deterministic polynomial reduction exists for a large class of integers.

Słowa kluczowe

EN

large sieve; factoring algorithm; Zn-generating sets; Dirichlet character; smooth numbers; discrete logarithm problem for composite numbers

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 156, nr 2
• Strony: 179--185
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Durnoga K.

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

autor

Pomykała J.

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

Bibliografia

• [1] Durnoga K, Źrałek B. On Computing Discrete Logarithms in Bulk and Randomness Extractors. Fundam. Inform., 2015;141(4):345–366. doi:10.3233/FI-2015-1279.
• [2] Pomykała J. On q-orders in primitive modular groups. Acta Arithmetica, 2014;166(4):397–404. URL http://eudml.org/doc/279782.
• [3] Rabin M. Probabilistic algorithm for testing primality. Journal of Number Theory, 1980;12(1):128–138. URL https://doi.org/10.1016/0022-314X(80)90084-0.
• [4] Miller G. Riemann’s Hypothesis and Tests for Primality. Journal of Computer and System Sciences, 1976;13(3):300–317. URL https://doi.org/10.1016/S0022-0000(76)80043-8.
• [5] 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.
• [6] Pomykała J. Small generating sets and DLPC Problem. Fundamenta Informaticae, 2016;145(2):143–150. doi:10.3233/FI-2016-1351.
• [7] Adleman L, McCurley K. Open problems in number theoretic complexity, II. In: L.M. Adleman, M.A. Huang (eds.), Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA, May 6-9, 1994, Proceedings, volume 877 of Lecture Notes in Computer Science. Springer. ISBN 3-540-58691-1, 1994 pp. 291–322.
• [8] Źrałek B. A deterministic version of Pollard’s p–1 algorithm. Math. Comp., 2010;79(269):513–533. URL https://doi.org/10.1090/S0025-5718-09-02262-5.
• [9] Bach E. Discrete Logarithms and Factoring. Technical report, Berkeley, CA, USA, 1984.
• [10] Pomykała J, Źrałek B. On reducing factorization to the discrete logarithm problem modulo a composite. Computational Complexity, 2012;21(3):421–429. doi:10.1007/s00037-012-0037-5.
• [11] Pomykała J. On Deterministic Reduction of Factoring Integers to Computing the Exponents of Elements in Modular Group. Fundamenta Informaticae, 2017;152(3):289–295. doi:10.3233/FI-2017-1521.
• [12] Konyagin S, Pomerance C. On Primes Recognizable in Deterministic Polynomial Time. In: R.L. Graham, J.S. Nesetril (eds.), The Mathematics of Paul Erdős I., pp. 159–186. Springer. ISBN:978-1-4614-7258-2, 2013. URL http://dblp.uni-trier.de/db/books/collections/GNB2013.html #KonyaginP13.
• [13] Gallagher P. The large sieve. Mathematika, 1967;14(1):14–20.
• [14] Montgomery H, Vaughan R. Extreme values of Dirichlet L-functions at 1. In: K. Györy, H. Iwaniec, J. Urbanowicz (ed.), Number Theory in Progress, volume 2, de Gruyter, Berlin 1999, pp. 1039–1052.
• [15] Elliott P. On the Mean Value of f(p). Proceedings of the London Mathematical Society, 1970;s3-21(1):28–96. doi:10.1112/plms/s3-21.1.28.
• [16] Lau Y,Wu J. On the least quadratic non-residue. International Journal of Number Theory, 2008; 4(3):423–435. URL https://doi.org/10.1142/S1793042108001432.
• [17] Hardy G, Wright E. An introduction to the theory of numbers. The Clarendon Press, Oxford University Press, New York, fifth edition, 1979. ISBN:0-19-853170-2; 0-19-853171-0.
• [18] Davenport H. Multiplicative Number Theory. Markham Publishing Company, Chicago, 1967.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).