Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

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?)

  • [1] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781-793. MR 2123939 (2006a:11170), https://doi.org/10.4007/annals.2004.160.781
  • [2] E. Bach, Discrete logarithms and factoring, Technical Report, University of California at Berkely.
  • [3] Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355-380. MR 1023756 (91m:11096), https://doi.org/10.2307/2008811
  • [4] 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 (2000i:11188), https://doi.org/10.1007/3-540-48405-1_21
  • [5] 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 (97h:94008), https://doi.org/10.1007/3-540-68339-9_14
  • [6] Don Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology 10 (1997), no. 4, 233-260. MR 1476612 (99b:94027), https://doi.org/10.1007/s001459900030
  • [7] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757 (2004g:68202)
  • [8] 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 (81i:10002)
  • [9] 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 (98a:11184), https://doi.org/10.1007/978-3-642-60408-9_15
  • [10] H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649-673. MR 916721 (89g:11125), https://doi.org/10.2307/1971363
  • [11] 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 (84a:12002), https://doi.org/10.1007/BF01457454
  • [12] H. W. Lenstra, Jr. and C. Pomerance, Primality testing with Gaussian periods, Manuscript, math.dartmouth.edu/~carlp, 2005.
  • [13] 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.
  • [14] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of applied cryptography, CRC Press, 1996.
  • [15] J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521-528. MR 0354514 (50 #6992)
  • [16] J. M. Pollard, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 331-334. MR 0392798 (52 #13611)
  • [17] J. M. Pollard, Monte Carlo methods for index computation $ ({\rm mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918-924. MR 0491431 (58 #10684)
  • [18] 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 (83m:94003), https://doi.org/10.1145/359340.359342
  • [19] A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281-292 (German, with English summary). MR 0292344 (45 #1431)
  • [20] H. C. Williams, A $ p+1$ method of factoring, Math. Comp. 39 (1982), no. 159, 225-234. MR 658227 (83h:10016), https://doi.org/10.2307/2007633

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.

American Mathematical Society