{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T19:45:54Z","timestamp":1710359154396},"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":"
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-28T11:45:12Z","timestamp":1401277512000},"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":[]},{"given":"Jung Hee","family":"Cheon","sequence":"additional","affiliation":[]}],"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":"http:\/\/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":"http:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"4","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"},{"key":"5","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"},{"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":"http:\/\/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":"http:\/\/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":"http:\/\/id.crossref.org\/isbn\/0198531702","edition":"5"},{"key":"9","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"},{"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":"http:\/\/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":"http:\/\/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":"http:\/\/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":"http:\/\/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":"http:\/\/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":"http:\/\/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":"http:\/\/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":"http:\/\/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":[[2021,7,30]],"date-time":"2021-07-30T05:52:40Z","timestamp":1627624360000},"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":"http:\/\/dx.doi.org\/10.1090\/s0025-5718-2014-02840-8","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"value":"0025-5718","type":"print"},{"value":"1088-6842","type":"electronic"}],"subject":["Applied Mathematics","Computational Mathematics","Algebra and Number Theory"],"published":{"date-parts":[[2014,5,28]]}}}