{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:36:11Z","timestamp":1776785771825,"version":"3.51.2"},"reference-count":23,"publisher":"American Mathematical Society (AMS)","issue":"254","license":[{"start":{"date-parts":[[2007,1,23]],"date-time":"2007-01-23T00:00:00Z","timestamp":1169510400000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n Given an integer\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , how hard is it to find the set of all integers\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n such that\n \n \n \n \n \n \u03c6\n \n <\/mml:mi>\n (<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n \\varphi (m) = n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n \n \u03c6\n \n <\/mml:mi>\n \\varphi<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is the Euler totient function? We present a certain basic algorithm which, given the prime number factorization of\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , in polynomial time \u201con average\u201d (that is,\n \n \n \n \n (<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n n<\/mml:mi>\n \n )<\/mml:mo>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n (\\log n)^{O(1)}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ), finds the set of all such solutions\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . In fact, in the worst case this set of solutions is exponential in\n \n \n \n \n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n \\log n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , and so cannot be constructed by a polynomial time algorithm. In the opposite direction, we show, under a widely accepted number theoretic conjecture, that the\n Partition Problem<\/sc>\n , an\n NP<\/bold>\n -complete problem, can be reduced in polynomial (in the input size) time to the problem of deciding whether\n \n \n \n \n \n \u03c6\n \n <\/mml:mi>\n (<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n \\varphi (m) = n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n has a solution, for polynomially (in the input size of the\n Partition Problem<\/sc>\n ) many values of\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n (where the prime factorizations of these\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n are given). What this means is that the problem of deciding whether there even exists a solution\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n to\n \n \n \n \n \n \u03c6\n \n <\/mml:mi>\n (<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n \\varphi (m) = n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , let alone finding any or all such solutions, is very likely to be intractable. Finally, we establish close links between the problem of inverting the Euler function and the integer factorization problem.\n <\/p>","DOI":"10.1090\/s0025-5718-06-01826-6","type":"journal-article","created":{"date-parts":[[2006,2,15]],"date-time":"2006-02-15T11:05:20Z","timestamp":1140001520000},"page":"983-996","source":"Crossref","is-referenced-by-count":4,"title":["Complexity of inverting the Euler function"],"prefix":"10.1090","volume":"75","author":[{"given":"Scott","family":"Contini","sequence":"first","affiliation":[]},{"given":"Ernie","family":"Croot","sequence":"additional","affiliation":[]},{"given":"Igor","family":"Shparlinski","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2006,1,23]]},"reference":[{"issue":"2","key":"1","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","article-title":"PRIMES is in P","volume":"160","author":"Agrawal, Manindra","year":"2004","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"3","key":"2","doi-asserted-by":"publisher","first-page":"703","DOI":"10.2307\/2118576","article-title":"There are infinitely many Carmichael numbers","volume":"139","author":"Alford, W. R.","year":"1994","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"4","key":"3","doi-asserted-by":"publisher","first-page":"331","DOI":"10.4064\/aa-83-4-331-361","article-title":"Shifted primes without large prime factors","volume":"83","author":"Baker, R. C.","year":"1998","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-1-4612-3464-7_5","article-title":"The prime \ud835\udc58-tuplets conjecture on average","author":"Balog, Antal","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0817634819"},{"key":"5","isbn-type":"print","first-page":"29","article-title":"Multiplicative structure of values of the Euler function","author":"Banks, William D.","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/0821833537"},{"key":"6","doi-asserted-by":"crossref","unstructured":"W. Banks, K. Ford, F. Luca, F. Pappalardi and I. E. Shparlinski, \u2018Values of the Euler function in various sequences\u2019, Monatsh. Math., 146 (2005), 1\u201319.","DOI":"10.1007\/s00605-005-0302-7"},{"key":"7","doi-asserted-by":"publisher","first-page":"329","DOI":"10.4064\/aa-21-1-329-345","article-title":"The distribution of values of the Euler function","volume":"21","author":"Bateman, Paul T.","year":"1972","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"8","unstructured":"W. Bosma, \u2018Some computational experiments in number theory\u2019, Preprint, 2004."},{"key":"9","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9316-0","volume-title":"Prime numbers","author":"Crandall, Richard","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/0387947779"},{"issue":"1-2","key":"10","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1023\/A:1009753405498","article-title":"Euler\u2019s function in residue classes","volume":"2","author":"Dence, Thomas","year":"1998","journal-title":"Ramanujan J.","ISSN":"https:\/\/id.crossref.org\/issn\/1382-4090","issn-type":"print"},{"key":"11","unstructured":"L. E. Dickson, \u2018A new extension of Dirichlet\u2019s theorem on prime numbers\u2019, Messenger of Mathematics, 33 (1904), 155-161."},{"key":"12","doi-asserted-by":"crossref","unstructured":"P. Erd\u0151s, \u2018On the normal number of prime factors of \ud835\udc5d-1 and some related problems concerning Euler\u2019s \ud835\udf19-function\u2019, Quart. J. Math., 6 (1935), 205\u2013213.","DOI":"10.1093\/qmath\/os-6.1.205"},{"issue":"2","key":"13","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1216\/RMJ-1985-15-2-343","article-title":"On the normal number of prime factors of \ud835\udf19(\ud835\udc5b)","volume":"15","author":"Erd\u0151s, Paul","year":"1985","journal-title":"Rocky Mountain J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0035-7596","issn-type":"print"},{"issue":"1","key":"14","doi-asserted-by":"publisher","first-page":"283","DOI":"10.2307\/121103","article-title":"The number of solutions of \ud835\udf19(\ud835\udc65)=\ud835\udc5a","volume":"150","author":"Ford, Kevin","year":"1999","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"15","isbn-type":"print","first-page":"805","article-title":"Residue classes free of values of Euler\u2019s function","author":"Ford, Kevin","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/3110157152"},{"issue":"3","key":"16","doi-asserted-by":"publisher","first-page":"649","DOI":"10.2307\/1971363","article-title":"Factoring integers with elliptic curves","volume":"126","author":"Lenstra, H. W., Jr.","year":"1987","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"1676","key":"17","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1098\/rsta.1993.0138","article-title":"A hyperelliptic smoothness test. I","volume":"345","author":"Lenstra, H. W., Jr.","year":"1993","journal-title":"Philos. Trans. Roy. Soc. London Ser. A","ISSN":"https:\/\/id.crossref.org\/issn\/0962-8428","issn-type":"print"},{"issue":"1","key":"18","doi-asserted-by":"publisher","first-page":"37","DOI":"10.2307\/2689883","article-title":"The equation \ud835\udf19(\ud835\udc65)=\ud835\udc58","volume":"49","author":"Mendelsohn, N. S.","year":"1976","journal-title":"Math. Mag.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-570X","issn-type":"print"},{"issue":"3","key":"19","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","article-title":"Riemann\u2019s hypothesis and tests for primality","volume":"13","author":"Miller, Gary L.","year":"1976","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"},{"key":"20","doi-asserted-by":"crossref","unstructured":"L. L. Pennesi, \u2018A method for solving \ud835\udf11(\ud835\udc65)=\ud835\udc5b\u2019, Amer. Math. Monthly, 74 (1957), 497-499.","DOI":"10.2307\/2308462"},{"issue":"1","key":"21","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1112\/S0025579300009967","article-title":"Popular values of Euler\u2019s function","volume":"27","author":"Pomerance, Carl","year":"1980","journal-title":"Mathematika","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5793","issn-type":"print"},{"key":"22","isbn-type":"print","first-page":"135","article-title":"Two methods in elementary analytic number theory","author":"Pomerance, Carl","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0792301498"},{"key":"23","series-title":"Cours Sp\\'{e}cialis\\'{e}s [Specialized Courses]","isbn-type":"print","volume-title":"Introduction \\`a la th\\'{e}orie analytique et probabiliste des nombres","volume":"1","author":"Tenenbaum, G\u00e9rald","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/2856290329","edition":"2"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-06-01826-6\/S0025-5718-06-01826-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-06-01826-6\/S0025-5718-06-01826-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:35:54Z","timestamp":1776782154000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-06-01826-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1,23]]},"references-count":23,"journal-issue":{"issue":"254","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["S0025-5718-06-01826-6"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-06-01826-6","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2006,1,23]]}}}