{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:48:31Z","timestamp":1776797311015,"version":"3.51.2"},"reference-count":20,"publisher":"American Mathematical Society (AMS)","issue":"291","license":[{"start":{"date-parts":[[2015,5,28]],"date-time":"2015-05-28T00:00:00Z","timestamp":1432771200000},"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":"<p>We address the problem of finding a nontrivial divisor of a composite integer when it has a prime divisor in an interval. We show that this problem can be solved in time of the square root of the interval length with a similar amount of storage, by presenting two algorithms; one is probabilistic and the other is its derandomized version.<\/p>","DOI":"10.1090\/s0025-5718-2014-02840-8","type":"journal-article","created":{"date-parts":[[2014,5,28]],"date-time":"2014-05-28T07:45:12Z","timestamp":1401263112000},"page":"339-354","source":"Crossref","is-referenced-by-count":1,"title":["Computing prime divisors in an interval"],"prefix":"10.1090","volume":"84","author":[{"given":"Minkyu","family":"Kim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jung Hee","family":"Cheon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2014,5,28]]},"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"},{"key":"2","unstructured":"E. Bach, Discrete logarithms and factoring, Technical Report, University of California at Berkely."},{"issue":"191","key":"3","doi-asserted-by":"publisher","first-page":"355","DOI":"10.2307\/2008811","article-title":"Explicit bounds for primality testing and related problems","volume":"55","author":"Bach, Eric","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/3-540-48405-1_21","article-title":"Factoring \ud835\udc41=\ud835\udc5d^{\ud835\udc5f}\ud835\udc5e for large \ud835\udc5f","author":"Boneh, Dan","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/3540663479"},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/3-540-68339-9_14","article-title":"Finding a small root of a univariate modular equation","author":"Coppersmith, Don","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/354061186X"},{"issue":"4","key":"6","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s001459900030","article-title":"Small solutions to polynomial equations, and low exponent RSA vulnerabilities","volume":"10","author":"Coppersmith, Don","year":"1997","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"7","isbn-type":"print","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0521826462","edition":"2"},{"key":"8","isbn-type":"print","volume-title":"An introduction to the theory of numbers","author":"Hardy, G. H.","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/0198531702","edition":"5"},{"key":"9","isbn-type":"print","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-60408-9_15","article-title":"On primes recognizable in deterministic polynomial time","author":"Konyagin, Sergei","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540610324"},{"issue":"3","key":"10","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":"4","key":"11","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra, A. K.","year":"1982","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"key":"12","unstructured":"H. W. Lenstra, Jr. and C. Pomerance, Primality testing with Gaussian periods, Manuscript, math.dartmouth.edu\/~carlp, 2005."},{"key":"13","unstructured":"A. May, Using LLL-reduction for solving RSA and factorization problems: A Survey, LLL+25 Conference in honour of the 25th birthday of the LLL algorithm, 2007."},{"key":"14","unstructured":"A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of applied cryptography, CRC Press, 1996."},{"key":"15","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1017\/s0305004100049252","article-title":"Theorems on factorization and primality testing","volume":"76","author":"Pollard, J. M.","year":"1974","journal-title":"Proc. Cambridge Philos. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0008-1981","issn-type":"print"},{"issue":"3","key":"16","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/bf01933667","article-title":"A Monte Carlo method for factorization","volume":"15","author":"Pollard, J. M.","year":"1975","journal-title":"Nordisk Tidskr. Informationsbehandling (BIT)","ISSN":"https:\/\/id.crossref.org\/issn\/0901-246X","issn-type":"print"},{"issue":"143","key":"17","doi-asserted-by":"publisher","first-page":"918","DOI":"10.2307\/2006496","article-title":"Monte Carlo methods for index computation (\ud835\udc5a\ud835\udc5c\ud835\udc51\ud835\udc5d)","volume":"32","author":"Pollard, J. M.","year":"1978","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"18","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest, R. L.","year":"1978","journal-title":"Comm. ACM","ISSN":"https:\/\/id.crossref.org\/issn\/0001-0782","issn-type":"print"},{"key":"19","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"issue":"159","key":"20","doi-asserted-by":"publisher","first-page":"225","DOI":"10.2307\/2007633","article-title":"A \ud835\udc5d+1 method of factoring","volume":"39","author":"Williams, H. C.","year":"1982","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2015-84-291\/S0025-5718-2014-02840-8\/S0025-5718-2014-02840-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-291\/S0025-5718-2014-02840-8\/S0025-5718-2014-02840-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:12:46Z","timestamp":1776795166000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-291\/S0025-5718-2014-02840-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,28]]},"references-count":20,"journal-issue":{"issue":"291","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["S0025-5718-2014-02840-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2014-02840-8","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":[[2014,5,28]]}}}