Computing prime divisors in an interval
HTML articles powered by AMS MathViewer
- by Minkyu Kim and Jung Hee Cheon PDF
- Math. Comp. 84 (2015), 339-354 Request permission
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
- Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, DOI 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 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 10.1007/3-540-48405-1_{2}1
- 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 10.1007/3-540-68339-9_{1}4
- Don Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology 10 (1997), no. 4, 233–260. MR 1476612, DOI 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 10.1007/978-3-642-60408-9_{1}5
- H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 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 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 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 10.1007/bf01933667
- J. M. Pollard, Monte Carlo methods for index computation $(\textrm {mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, DOI 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 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 10.1007/bf02242355
- H. C. Williams, A $p+1$ method of factoring, Math. Comp. 39 (1982), no. 159, 225–234. MR 658227, DOI 10.1090/S0025-5718-1982-0658227-7
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
- 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).
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 3266963