Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

Computing prime divisors in an interval


Authors: Minkyu Kim and Jung Hee Cheon
Journal: Math. Comp. 84 (2015), 339-354
MSC (2010): Primary 11Y05, 11Y16; Secondary 68Q25
DOI: https://doi.org/10.1090/S0025-5718-2014-02840-8
Published electronically: May 28, 2014
MathSciNet review: 3266963
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y05, 11Y16, 68Q25

Retrieve articles in all journals with MSC (2010): 11Y05, 11Y16, 68Q25


Additional Information

Minkyu Kim
Affiliation: Electronics and Telecommunications Research Institute, P. O. Box 1, Yuseong, Daejeon, 305-600, Korea
Email: mkkim@ensec.re.kr

Jung Hee Cheon
Affiliation: ISaC and Department of Mathematical Sciences, Seoul National University, Seoul 151-747, Korea
Email: jhcheon@snu.ac.kr

DOI: https://doi.org/10.1090/S0025-5718-2014-02840-8
Keywords: Integer factorization, prime divisors in an interval
Received by editor(s): December 15, 2012
Received by editor(s) in revised form: April 11, 2013, and May 10, 2013
Published electronically: May 28, 2014
Additional Notes: This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea Government (NRF-2011-0018345).
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.