Najnowszy Numer
Archiwum
O Nas
Międzynarodowa Rada Naukowa
Rada Redakcyjna
Kontakt
Recenzenci
Standardy etyczne
Standardy etyczne czasopisma (COPE)
Polityka Open Access
Procedura zabezpieczająca oryginalność publikacji
Dla Autorów
Wymagania Edytorskie
Wytyczne Merytoryczne
Proces Recenzji
Dla Recenzentów
ARTYKUŁ PRZEGLĄDOWY
ROZSZERZONY ALGORYTM POHLIGA-HELLMANA I JEGO ZASTOSOWANIE DO FAKTORYZACJI
1
Uniwersytet Warszawski
Data publikacji: 05-12-2014
SBN 2014;6(2): 177-183
SŁOWA KLUCZOWE
STRESZCZENIE
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.
REFERENCJE (14)
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. Furer, 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¨os, 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.
Udostępnij
| ISSN: | 2082-2677 |
Przetwarzamy dane osobowe zbierane podczas odwiedzania serwisu. Realizacja funkcji pozyskiwania informacji o użytkownikach i ich zachowaniu odbywa się poprzez dobrowolnie wprowadzone w formularzach informacje oraz zapisywanie w urządzeniach końcowych plików cookies (tzw. ciasteczka). Dane, w tym pliki cookies, wykorzystywane są w celu realizacji usług, zapewnienia wygodnego korzystania ze strony oraz w celu monitorowania ruchu zgodnie z Polityką prywatności. Dane są także zbierane i przetwarzane przez narzędzie Google Analytics (więcej).
Możesz zmienić ustawienia cookies w swojej przeglądarce. Ograniczenie stosowania plików cookies w konfiguracji przeglądarki może wpłynąć na niektóre funkcjonalności dostępne na stronie.
Możesz zmienić ustawienia cookies w swojej przeglądarce. Ograniczenie stosowania plików cookies w konfiguracji przeglądarki może wpłynąć na niektóre funkcjonalności dostępne na stronie.
