Rozszerzony algorytm Pohliga-Hellmana i jego zastosowanie do faktoryzacji

• Autorzy: Źrałek B.

Warianty tytułu

EN

A generalization of the Pohlig-Hellman algorithm and its application to factoring

• Języki publikacji: PL

Abstrakty

PL

Wskażemy ścisły związek między problemami logarytmu dyskretnego i faktoryzacji. Opiszemy mianowicie uogólnienie algorytmu Pohliga-Hellmana dla grup niecyklicznych Z*_n, które można zastosować do derandomizacji algorytmu p−1 Pollarda. Algorytm ten bowiem w w wersji potrzebuje źródła losowości. Okazuje się, że obliczenia można przeprowadzić deterministycznie bez znaczącego pogorszenia złożoności.

EN

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.

Słowa kluczowe

PL

faktoryzacja; logarytm dyskretny; derandomizacja

EN

factoring; discrete logarithm; derandomization

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Studia Bezpieczeństwa Narodowego
• Rocznik: 2014
• Tom: R. 4, Nr 6
• Strony: 177--183
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Źrałek B.

• Instytut Matematyki Uniwersytetu Warszawskiego, Banacha 2, 02-097 Warszawa

Bibliografia

• [1] E. Bach, J. O. Shallit, Factoring with cyclotomic polynomials, Mathematics of Computation, 52 (1989), 201-219.
• [2] W. Diffie, M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, 22 (1976), 644-654.
• [3] J. von zur Gathen, Arithmetic circuits for discrete logarithms, Lecture Notes in Computer Science, 2976 (2004), 557-566.
• [4] D. Gordon, Discrete logarithms in GF(p) using the number field sieve, SIAM Journal on Discrete Mathematics, 6 (1993), 124-138.
• [5] M. R. Fellows, N. Koblitz, Self-witnessing polynomial-time complexity and prime factorization, Designs, Codes and Cryptography, 2 (1992), 231-235.
• [6] M. Fürer, Deterministic and Las Vegas primality testing algorithms, Lecture Notes in Computer Science, 194 (1985), 199-209.
• [7] 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.
• [8] A. Lenstra, H. Lenstra Jr. (Eds.), The development of the number field sieve, Lecture Notes in Mathematics, 1554 (1993).
• [9] H. Lenstra Jr., Factoring integers with elliptic curves, Annals of Mathematics, 126 (1987), 649-673.
• [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.
• [11] J. M. Pollard, Theorems on factorization and primality testing, Proceedings of the Cambridge Philosophical Society, 76 (1974), 521-528.
• [12] J. Pomykała, B. Źrałek, On reducing factorization to the discrete logarithm problem modulo a composite, computational complexity, 21 (2012), 421-429.
• [13] B. Źrałek, A deterministic version of Pollard’s p−1 algorithm, Mathematics of Computation, 79 (2010), 513-533.
• [14] B. Źrałek, Using partial smoothness of p−1 for factoring polynomials modulo p, Mathematics of Computation, 79 (2010), 2353–2359.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).