A GENERALIZATION OF THE POHLIG-HELLMAN ALGORITHM AND ITS APPLICATION TO FACTORING

We will show that the discrete logarithm problem and the problem of factoring are closely related. Namely, we will describe a generalization of the Pohlig-Hellman algorithm to noncyclic Z∗ n groups which can be used to derandomize Pollard’s p − 1 algorithm. The original version of this factoring algorithm needs indeed a source of randomness. It turns out however that the computations can be done deterministically with only slightly worse complexity.

REFERENCES (14)

E. Bach, J. O. Shallit, Factoring with cyclotomic polynomials, Mathematics of Computation, 52 (1989), 201-219.

Google Scholar

W. Diffie, M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, 22 (1976), 644-654.

Google Scholar

J. von zur Gathen, Arithmetic circuits for discrete logarithms, Lecture Notes in Computer Science, 2976 (2004), 557-566.

Google Scholar

D. Gordon, Discrete logarithms in GF(p) using the number field sieve, SIAM Journal on Discrete Mathematics, 6 (1993), 124-138.

Google Scholar

M. R. Fellows, N. Koblitz, Self-witnessing polynomial-time complexity and prime factorization, Designs, Codes and Cryptography, 2 (1992), 231-235.

Google Scholar

M. Furer, Deterministic and Las Vegas primality testing algorithms, Lecture Notes in Computer Science, 194 (1985), 199-209.

Google Scholar

S. Konyagin, C. Pomerance, On primes recognizable in deterministic polynomial time, The Mathematics of Paul Erd¨os, R. L. Graham, J. Nesetril, eds., Springer-Verlag, 1997, 176-198.

Google Scholar

A. Lenstra, H. Lenstra Jr. (Eds.), The development of the number field sieve, Lecture Notes in Mathematics, 1554 (1993).

Google Scholar

H. Lenstra Jr., Factoring integers with elliptic curves, Annals of Mathematics, 126 (1987), 649-673.

Google Scholar

10.

S. Pohlig, M. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Transactions on Information Theory, 24 (1978), 106-110.

Google Scholar

11.

J. M. Pollard, Theorems on factorization and primality testing, Proceedings of the Cambridge Philosophical Society, 76 (1974), 521-528.

Google Scholar

12.

J. Pomykała, B. Źrałek, On reducing factorization to the discrete logarithm problem modulo a composite, computational complexity, 21 (2012), 421-429.

Google Scholar

13.

B. Źrałek, A deterministic version of Pollard’s p−1 algorithm, Mathematics of Computation, 79 (2010), 513-533.

Google Scholar

14.

B. Źrałek, Using partial smoothness of p − 1 for factoring polynomials modulo p, Mathematics of Computation, 79 (2010), 2353–2359.

Google Scholar

Submit your paper