{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:21:15Z","timestamp":1764980475187,"version":"3.46.0"},"reference-count":18,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,8,20]]},"abstract":"Abstract<\/jats:title>\n \n We describe a reduction of the problem of factorization of integers\n n<\/jats:italic>\n \u2264\n x<\/jats:italic>\n in polynomial-time (log\n x<\/jats:italic>\n )\n \n M<\/jats:italic>\n +\n O<\/jats:italic>\n (1)\n <\/jats:sup>\n to computing Euler\u2019s totient function, with exceptions of at most\n x<\/jats:italic>\n \n O<\/jats:italic>\n (1\/\n M<\/jats:italic>\n )\n <\/jats:sup>\n composite integers that cannot be factored at all, and at most\n x<\/jats:italic>\n exp\n \n \n \n \n \n \n \n \n \n \n \u2212<\/m:mo>\n \n \n \n c<\/m:mi>\n M<\/m:mi>\n <\/m:msub>\n (<\/m:mo>\n log<\/m:mi>\n log<\/m:mi>\n \u2061<\/m:mo>\n x<\/m:mi>\n \n )<\/m:mo>\n 3<\/m:mn>\n <\/m:msup>\n <\/m:mrow>\n \n (<\/m:mo>\n log<\/m:mi>\n log<\/m:mi>\n log<\/m:mi>\n \u2061<\/m:mo>\n x<\/m:mi>\n \n )<\/m:mo>\n 2<\/m:mn>\n <\/m:msup>\n <\/m:mrow>\n <\/m:mfrac>\n <\/m:mrow>\n <\/m:mfenced>\n <\/m:mstyle>\n <\/m:mtd>\n <\/m:mtr>\n <\/m:mtable>\n <\/m:math>\n $\\begin{array}{}\n\\displaystyle\n\\left(-\\frac{c_M(\\log\\log x)^3}{(\\log\\log\\log x)^2}\\right)\n\\end{array}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n integers that cannot be factored completely. The problem of factoring square-free integers\n n<\/jats:italic>\n is similarly reduced to that of computing a multiple\n D<\/jats:italic>\n of\n \u03d5<\/jats:italic>\n (\n n<\/jats:italic>\n ), where\n D<\/jats:italic>\n \u226a exp((log\n x<\/jats:italic>\n )\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n ), with the exception of at most\n x<\/jats:italic>\n \n O<\/jats:italic>\n (1\/\n M<\/jats:italic>\n )\n <\/jats:sup>\n integers that cannot be factored at all, in particular\n O<\/jats:italic>\n (\n x<\/jats:italic>\n \n 1\/\n M<\/jats:italic>\n <\/jats:sup>\n ) integers of the form\n n<\/jats:italic>\n =\n pq<\/jats:italic>\n that cannot be factored.\n <\/jats:p>","DOI":"10.1515\/jmc-2019-0023","type":"journal-article","created":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T07:12:17Z","timestamp":1598425937000},"page":"346-358","source":"Crossref","is-referenced-by-count":3,"title":["Integer factoring and compositeness witnesses"],"prefix":"10.1515","volume":"14","author":[{"given":"Jacek","family":"Pomyka\u0142a","sequence":"first","affiliation":[{"name":"Faculty of Mathematics, Informatics and Mechanics , University of Warsaw ul.Banacha 2, PL-02-097 , Warsaw , Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maciej","family":"Radziejewski","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Computer Science , Adam Mickiewicz University ul.Umultowska 87, PL-61-614 , Pozna\u0144 , Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2020,8,20]]},"reference":[{"key":"2025120600172413888_j_jmc-2019-0023_ref_001_w2aab3b7e2071b1b6b1ab2b2b1Aa","doi-asserted-by":"crossref","unstructured":"L. M. Adleman, K. S. McCurley, Open problems in number theoretic complexity II. In: Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA, 291\u2013322 (1994), Springer-Verlag.","DOI":"10.1007\/3-540-58691-1_70"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_002_w2aab3b7e2071b1b6b1ab2b2b2Aa","doi-asserted-by":"crossref","unstructured":"N. C. Ankeny, The least quadratic non residue, Ann. of Math. 55 (1952), 65\u201372.","DOI":"10.2307\/1969420"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_003_w2aab3b7e2071b1b6b1ab2b2b3Aa","unstructured":"E. Bach, Discrete logarithms and factoring, Technical report UCB\/CSD-84-186, EECS Department, University of California, Berkeley. http:\/\/www.eecs.berkeley.edu\/Pubs\/TechRpts\/1984\/5973.html."},{"key":"2025120600172413888_j_jmc-2019-0023_ref_004_w2aab3b7e2071b1b6b1ab2b2b4Aa","doi-asserted-by":"crossref","unstructured":"S. Baier, On the least n with \u03c7(n) \u2260 1, Quart. J. Math. 57 (2006), 279\u2013283.","DOI":"10.1093\/qmath\/hai022"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_005_w2aab3b7e2071b1b6b1ab2b2b5Aa","unstructured":"R. Crandall, C. Pomerance, Prime Numbers \u2014 A Computational Perspective, Second Edition, Springer 2005."},{"key":"2025120600172413888_j_jmc-2019-0023_ref_006_w2aab3b7e2071b1b6b1ab2b2b6Aa","doi-asserted-by":"crossref","unstructured":"K. Durnoga, J. Pomyka\u0142a, Large sieve, Miller-Rabin compositeness witnesses and integer factoring problem, Fundamenta Informaticae, 156(2), 2017, 179\u2013185.","DOI":"10.3233\/FI-2017-1603"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_007_w2aab3b7e2071b1b6b1ab2b2b7Aa","doi-asserted-by":"crossref","unstructured":"K. Ford, The number of solutions of \u03d5(x) = m, Ann. of Math. (2) 150 (1999), no. 1, 283\u2013311.","DOI":"10.2307\/121103"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_008_w2aab3b7e2071b1b6b1ab2b2b8Aa","doi-asserted-by":"crossref","unstructured":"S. Konyagin, C. Pomerance, On primes recognizable in deterministic polynomial time, in: The mathematics of Paul Erdos, R. L. Graham and J. Nesetril (eds.), Springer-Verlag, 1997, 176\u2013198.","DOI":"10.1007\/978-3-642-60408-9_15"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_009_w2aab3b7e2071b1b6b1ab2b2b9Aa","doi-asserted-by":"crossref","unstructured":"S. Landau, Some remarks on computing the square parts of integers, Inf. Comput. 78(3), 1988, 246\u2013253.","DOI":"10.1016\/0890-5401(88)90028-4"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_010_w2aab3b7e2071b1b6b1ab2b2c10Aa","doi-asserted-by":"crossref","unstructured":"Y. K. Lau, J. Wu, On the least quadratic non-residue, Int. J. Number Theory 04, 423 (2008).","DOI":"10.1142\/S1793042108001432"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_011_w2aab3b7e2071b1b6b1ab2b2c11Aa","unstructured":"H. W. Lenstra, Jr., C. Pomerance, Primality testing with Gaussian periods, in: Manuscript, math.dartmouth.edu\/ carlp, 2005. - See more at: http:\/\/www.ams.org\/journals\/mcom\/2015-84-291\/S0025-5718-2014-02840-8\/#sthash.kmasMqnp.dpuf"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_012_w2aab3b7e2071b1b6b1ab2b2c12Aa","doi-asserted-by":"crossref","unstructured":"G. L. Miller, Riemann\u2019s Hypothesis and tests for primality, Journal of Computer and System Sciences 13(3), (1976), 300\u2013317.","DOI":"10.1016\/S0022-0000(76)80043-8"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_013_w2aab3b7e2071b1b6b1ab2b2c13Aa","unstructured":"F. Morain, G. Renault, B. Smith, Deterministic factoring with oracleshttps:\/\/hal.inria.fr\/hal-01715832\/document"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_014_w2aab3b7e2071b1b6b1ab2b2c14Aa","doi-asserted-by":"crossref","unstructured":"J. Pomyka\u0142a, B. \u0179ra\u0142ek, On reducing factorization to the discrete logarithm problem modulo a composite, Comput. Complex 21 (2012), 421\u2013429.","DOI":"10.1007\/s00037-012-0037-5"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_015_w2aab3b7e2071b1b6b1ab2b2c15Aa","doi-asserted-by":"crossref","unstructured":"M. O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12(1), 1980, 128\u2013138.","DOI":"10.1016\/0022-314X(80)90084-0"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_016_w2aab3b7e2071b1b6b1ab2b2c16Aa","doi-asserted-by":"crossref","unstructured":"A. Sch\u00f6nhage, V. Strassen, Schnelle Multiplikation gro\u00dfer Zahlen, Computing 7 (1971), 281\u2013292.","DOI":"10.1007\/BF02242355"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_017_w2aab3b7e2071b1b6b1ab2b2c17Aa","doi-asserted-by":"crossref","unstructured":"G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory: Third Edition, Graduate Studies in Mathematics 163, AMS, 2015.","DOI":"10.1090\/gsm\/163"},{"key":"2025120600172413888_j_jmc-2019-0023_ref_018_w2aab3b7e2071b1b6b1ab2b2c18Aa","doi-asserted-by":"crossref","unstructured":"B. \u0179ra\u0142ek, A deterministic version of Pollard\u2019s p \u2212 1 algorithm, Math. of Comp. 79 (2010), 513\u2013533.","DOI":"10.1090\/S0025-5718-09-02262-5"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/14\/1\/article-p346.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0023\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0023\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:17:57Z","timestamp":1764980277000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2019-0023\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,1]]},"references-count":18,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,8,7]]},"published-print":{"date-parts":[[2020,8,7]]}},"alternative-id":["10.1515\/jmc-2019-0023"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2019-0023","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"type":"electronic","value":"1862-2984"},{"type":"print","value":"1862-2976"}],"subject":[],"published":{"date-parts":[[2020,1,1]]}}}