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 Free Access
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.
- Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, DOI https://doi.org/10.4007/annals.2004.160.781
- E. Bach, Discrete logarithms and factoring, Technical Report, University of California at Berkely.
- Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI https://doi.org/10.1090/S0025-5718-1990-1023756-8
- Dan Boneh, Glenn Durfee, and Nick Howgrave-Graham, Factoring $N=p^rq$ for large $r$, Advances in cryptology—CRYPTO ’99 (Santa Barbara, CA), Lecture Notes in Comput. Sci., vol. 1666, Springer, Berlin, 1999, pp. 326–337. MR 1729303, DOI https://doi.org/10.1007/3-540-48405-1_21
- Don Coppersmith, Finding a small root of a univariate modular equation, Advances in cryptology—EUROCRYPT ’96 (Saragossa, 1996) Lecture Notes in Comput. Sci., vol. 1070, Springer, Berlin, 1996, pp. 155–165. MR 1421584, DOI https://doi.org/10.1007/3-540-68339-9_14
- Don Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology 10 (1997), no. 4, 233–260. MR 1476612, DOI https://doi.org/10.1007/s001459900030
- Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
- G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
- Sergei Konyagin and Carl Pomerance, On primes recognizable in deterministic polynomial time, The mathematics of Paul Erdős, I, Algorithms Combin., vol. 13, Springer, Berlin, 1997, pp. 176–198. MR 1425185, DOI https://doi.org/10.1007/978-3-642-60408-9_15
- H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI https://doi.org/10.2307/1971363
- A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI https://doi.org/10.1007/BF01457454
- H. W. Lenstra, Jr. and C. Pomerance, Primality testing with Gaussian periods, Manuscript, math.dartmouth.edu/~carlp, 2005.
- 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.
- A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of applied cryptography, CRC Press, 1996.
- J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI https://doi.org/10.1017/s0305004100049252
- J. M. Pollard, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 331–334. MR 392798, DOI https://doi.org/10.1007/bf01933667
- J. M. Pollard, Monte Carlo methods for index computation $({\rm mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, DOI https://doi.org/10.1090/S0025-5718-1978-0491431-9
- R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120–126. MR 700103, DOI https://doi.org/10.1145/359340.359342
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI https://doi.org/10.1007/bf02242355
- H. C. Williams, A $p+1$ method of factoring, Math. Comp. 39 (1982), no. 159, 225–234. MR 658227, DOI https://doi.org/10.1090/S0025-5718-1982-0658227-7
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
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.
