Computing prime divisors in an interval

Kim, Minkyu; Cheon, Jung Hee

doi:10.1090/S0025-5718-2014-02840-8

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.

[1] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, 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, https://doi.org/10.1090/S0025-5718-1990-1023756-8
[4] Dan Boneh, Glenn Durfee, and Nick Howgrave-Graham, Factoring 𝑁=𝑝^{𝑟}𝑞 for large 𝑟, Advances in cryptology—CRYPTO ’99 (Santa Barbara, CA), Lecture Notes in Comput. Sci., vol. 1666, Springer, Berlin, 1999, pp. 326–337. MR 1729303, 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, 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, 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
[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
[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, 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, 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, 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 354514, https://doi.org/10.1017/s0305004100049252
[16] J. M. Pollard, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 331–334. MR 392798, https://doi.org/10.1007/bf01933667
[17] J. M. Pollard, Monte Carlo methods for index computation (𝑚𝑜𝑑𝑝), Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, https://doi.org/10.1090/S0025-5718-1978-0491431-9
[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, 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 292344, https://doi.org/10.1007/bf02242355
[20] H. C. Williams, A 𝑝+1 method of factoring, Math. Comp. 39 (1982), no. 159, 225–234. MR 658227, https://doi.org/10.1090/S0025-5718-1982-0658227-7