Tytuł:

ROZSZERZONY ALGORYTM POHLIGA-HELLMANA I JEGO ZASTOSOWANIE DO FAKTORYZACJI

Twórca:

ŹRAŁEK Bartosz

Abstrakt:

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.

Data wydania:

2014-12-05

Identyfikator:

doi:10.37055/sbn/135229 ; oai:editorialsystem.com:article-135229

ISSN drukowany:

2082-2677

Identyfikator wydawcy:

135229

Licencja:

kliknij tutaj, żeby przejść

Strona początkowa:

177

Strona końcowa:

183

Tom:

6

Wydanie:

2

Czasopismo:

SBN

Słowa kluczowe:

faktoryzacja ; logarytm dyskretny ; derandomizacja