Logarytm dyskretny

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Logarytm dyskretny elementu przy podstawie w danej grupie skończonej – liczba całkowita dla której zachodzi równość (w notacji multiplikatywnej):

Kryptologia (z gr. κρυπτός – kryptos – "ukryty" i λόγος – logos – "słowo") – dziedzina wiedzy o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem. Współcześnie kryptologia jest uznawana za gałąź zarówno matematyki, jak i informatyki; ponadto jest blisko związana z teorią informacji, inżynierią oraz bezpieczeństwem komputerowym.Liczby całkowite – liczby naturalne dodatnie N + = { 1 , 2 , 3 , … } {displaystyle mathbb {N} _{+}={1,2,3,dots }} oraz liczby przeciwne do nich { − 1 , − 2 , − 3 , … } {displaystyle {-1,-2,-3,dots }} , a także liczba zero. Uogólnieniem liczb całkowitych są liczby wymierne i tym samym liczby rzeczywiste, szczególnym przypadkiem liczb całkowitych są: liczby naturalne.

Logarytm dyskretny nie zawsze istnieje, a jeśli istnieje, może nie być jednoznaczny. Np. w ciele skończonym logarytmem przy podstawie 4 z elementu 9 jest liczba 3 (ale też 8). W tym ciele nie istnieje logarytm przy podstawie 4 z elementu 7.

Krzywa eliptyczna – pojęcie z zakresu geometrii algebraicznej, oznaczające według współczesnej definicji gładką krzywą algebraiczną (czyli rozmaitość algebraiczną wymiaru 1) o genusie równym 1 wraz z wyróżnionym punktem O, zwanym "punktem w nieskończoności". Elementy krzywej rozumianej jako zbiór nazywa się, zgodnie z terminologią geometryczną, punktami.ElGamal – jeden z dwóch najważniejszych algorytmów kryptografii asymetrycznej (obok RSA). System jest oparty na trudności problemu logarytmu dyskretnego w ciele liczb całkowitych modulo duża liczba pierwsza. Algorytm w połowie lat 80. XX wieku przedstawił Egipcjanin Taher Elgamal.

Znalezienie logarytmu dyskretnego jest zaskakująco trudnym problemem. O ile potęgowanie wymaga operacji – liczymy po czym wymnażamy te z nich, dla których bity c są równe 1, to jedyną prostą metodą rozwiązywania problemu logarytmu dyskretnego jest przeszukanie wszystkich możliwych Istnieją efektywniejsze metody, jednak żadna z ogólnych metod nie ma złożoności wielomianowej wobec ilości bitów wejścia (istnieją takie dla pewnych specyficznych klas liczb pierwszych, których należy więc w kryptografii unikać). Najszybszy algorytm (sito ciała liczbowego) obliczania logarytmu dyskretnego w GF(p) ma złożoność czasową:

Schemat identyfikacji Schnorra – w kryptografii, podpis cyfrowy wygenerowany algorytmem Schnorra. Jego bezpieczeństwo opiera się na trudności w rozwiązaniu logarytmu dyskretnego. Algorytm jest wydajny i tworzy krótkie podpisy.Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

gdzie c jest pewną stałą. Jedną z metod obliczania logarytmu dyskretnego w GF(p) jest redukcja Pohliga-Hellmana.

Redukcja Pohliga-Hellmana jest metodą obliczania logarytmu dyskretnego w ciele skończonym GF(p) wymyśloną przez Stephena Pohliga i Martina Hellmana.

Trudność znalezienia logarytmu dyskretnego jest podstawą istnienia wielu algorytmów kryptograficznych, takich jak ElGamal i protokół Diffiego-Hellmana czy kryptografia oparta na krzywych eliptycznych.

Zobacz też[ | edytuj kod]

  • schemat identyfikacji Schnorra




  • Reklama