Title:

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

Creator:

ŹRAŁEK Bartosz

Abstract:

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.

Date issued:

2014-12-05

Identifier:

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

Print ISSN:

2082-2677

Publisher ID:

135229

License:

click here to follow the link

Starting page:

177

Ending page:

183

Volume:

6

Issue:

2

Journal:

SBN

Keywords:

factoring ; discrete logarithm ; derandomization