Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

A deterministic version of Pollard's $ p-1$ algorithm


Author: Bartosz Zrałek
Journal: Math. Comp. 79 (2010), 513-533
MSC (2000): Primary 11Y16; Secondary 11Y05, 68Q10
Published electronically: May 6, 2009
MathSciNet review: 2552238
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this article we present applications of smooth numbers to the unconditional derandomization of some well-known integer factoring algo- rithms.

We begin with Pollard's $ p-1$ algorithm, which finds in random polynomial time the prime divisors $ p$ of an integer $ n$ such that $ p-1$ is smooth. We show that these prime factors can be recovered in deterministic polynomial time. We further generalize this result to give a partial derandomization of the $ k$-th cyclotomic method of factoring ($ k\ge 2$) devised by Bach and Shallit.

We also investigate reductions of factoring to computing Euler's totient function $ \varphi$. We point out some explicit sets of integers $ n$ that are completely factorable in deterministic polynomial time given $ \varphi(n)$. These sets consist, roughly speaking, of products of primes $ p$ satisfying, with the exception of at most two, certain conditions somewhat weaker than the smoothness of $ p-1$. Finally, we prove that $ O(\ln n)$ oracle queries for values of $ \varphi$ are sufficient to completely factor any integer $ n$ in less than $ \exp\Bigl((1+o(1))(\ln n)^{\frac{1}{3}} (\ln\ln n)^{\frac{2}{3}}\Bigr)$ deterministic time.


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

  • 1. L. M. Adleman, K. S. McCurley, Open problems in number-theoretic complexity. II, Algorithmic Number Theory Symposium I (1994), 291-322. MR 1322733 (95m:11142)
  • 2. M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P, Annals of Mathematics (2), 160 (2004), 781-793. MR 2123939 (2006a:11170)
  • 3. E. Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation, 55 (1990), 355-380. MR 1023756 (91m:11096)
  • 4. E. Bach, G. Miller, J. O. Shallit, Sums of divisors, perfect numbers and factoring, SIAM Journal on Computing, 15 (1986), 1143-1154. MR 861378 (87k:11139)
  • 5. E. Bach, J. O. Shallit, Algorithmic number theory, Volume 1: Efficient algorithms, MIT Press, 1996. MR 1406794 (97e:11157)
  • 6. E. Bach, J. O. Shallit, Factoring with cyclotomic polynomials, Mathematics of Computation, 52 (1989), 201-219. MR 947467 (89k:11127)
  • 7. E. R. Berlekamp, Factoring polynomials over finite fields, Bell Systems Technical Journal, 46 (1967), 1853-1859. MR 0219231 (36:2314)
  • 8. R. J. Burthe, Jr., The average least witness is $ 2$, Acta Arithmetica, 80 (1997), 327-341. MR 1450927 (98h:11118)
  • 9. E. R. Canfield, P. Erdös, C. Pomerance, On a problem of Oppenheim concerning ``factorisatio numerorum'', Journal of Number Theory, 17 (1983), 1-28. MR 712964 (85j:11012)
  • 10. D. Coppersmith, N. Howgrave-Graham, S. V. Nagaraj, Divisors in residue classes, constructively, Mathematics of Computation, 77 (2008), 531-545. MR 2353965 (2009b:11221)
  • 11. M. R. Fellows, N. Koblitz, Self-witnessing polynomial-time complexity and prime factorization, Designs, Codes and Cryptography, 2 (1992), 231-235. MR 1181730 (93e:68032)
  • 12. M. Fürer, Deterministic and Las Vegas primality testing algorithms, Lecture Notes in Computer Science, 194 (1985), 199-209. MR 819255 (87c:11123)
  • 13. K. Hensel, Neue Grundlagen der Arithmetic, Journal für die Reine und Angewandte Mathematik, 127 (1904), 51-84.
  • 14. S. Konyagin, C. Pomerance, On primes recognizable in deterministic polynomial time, The Mathematics of Paul Erdös, R. L. Graham, J. Nesetril, eds., Springer-Verlag, 1997, 176-198. MR 1425185 (98a:11184)
  • 15. S. Landau, Some remarks on computing the square parts of integers, Information and Computation, 78, No. 3 (1988), 246-253. MR 959811 (89k:11003)
  • 16. A. K. Lenstra, H. W. Lenstra, Jr., L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 515-534. MR 682664 (84a:12002)
  • 17. H. W. Lenstra, Jr., Factoring integers with elliptic curves, Annals of Mathematics (2), 126 (1987), 649-673. MR 916721 (89g:11125)
  • 18. H. W. Lenstra, Jr., C. Pomerance, Primality testing with Gaussian periods, preliminary version, July 20, 2005.
  • 19. G. L. Miller, Riemann's Hypothesis and tests for primality, Journal of Computer and System Sciences, 13 (1976), 300-317. MR 0480295 (58:470a)
  • 20. S. C. Pohlig, M. E. Hellman, An improved algorithm for computing logarithms over $ GF(p)$ and its cryptographic significance, IEEE Transactions on Information Theory, 24 (1978), 106-110. MR 0484737 (58:4617)
  • 21. J. M. Pollard, Theorems on factorization and primality testing, Proceedings of the Cambridge Philosophical Society, 76 (1974), 521-528. MR 0354514 (50:6992)
  • 22. M. O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory, 12 (1980), 128-138. MR 566880 (81f:10003)
  • 23. R. L. Rivest, A. Shamir, L. M. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 21 (1978), 120-126. MR 700103 (83m:94003)
  • 24. V. Strassen, Einige Resultate über Berechnungskomplexität, Jahresbericht der Deutschen Mathematiker-Vereinigung, 78 (1976), 1-8. MR 0438807 (55:11713)
  • 25. J. W. M. Turk, Fast arithmetic operations on numbers and polynomials, Computational Methods in Number Theory I (1982), 43-54. MR 700257 (84f:10006)
  • 26. H. C. Williams, A $ p+1$ method of factoring, Mathematics of Computation, 39 (1982), 225-234. MR 658227 (83h:10016)
  • 27. B. Źrałek, Using the smoothness of $ p-1$ for computing roots modulo $ p$, submitted, preliminary version available on http://arxiv.org/abs/0803.0471.

Similar Articles

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

Retrieve articles in all journals with MSC (2000): 11Y16, 11Y05, 68Q10


Additional Information

Bartosz Zrałek
Affiliation: Institute of Mathematics, Polish Academy of Sciences, 00-956 Warsaw, Poland
Email: b.zralek@impan.gov.pl

DOI: http://dx.doi.org/10.1090/S0025-5718-09-02262-5
Keywords: Pollard's $p-1$ method, derandomization, Euler's $\varphi $-function and factorization
Received by editor(s): November 26, 2007
Received by editor(s) in revised form: October 3, 2008, and January 1, 2009
Published electronically: May 6, 2009
Article copyright: © Copyright 2009 American Mathematical Society