O złożoności problemu wyznaczania podstawy logarytmu dyskretnego w schemacie Diffi’ego-Hellmana

• Autorzy: Paszkiewicz A.

Identyfikatory

DOI

10.15199/59.2018.1.3

Warianty tytułu

EN

On complexity problem of determining base for discrete logarithm problem in Diffie-Hellman scheme

• Języki publikacji: PL

Abstrakty

PL

W artykule pokazano, że w klasycznym schemacie Diffi’ego-Hellmana, opartym na logarytmie dyskretnym w grupie multiplikatywnej modulo liczba pierwsza, w większości przypadków generator tej grupy jest równy najmniejszej niereszcie kwadratowej modulo rząd grupy. W szczególności pokazano, że mimo tej obserwacji, problem znalezienia generatora grupy multiplikatywnej modulo losowo wybrana duża liczba pierwsza nie jest łatwy do rozwiązania. Przytoczone zostały argumenty obliczeniowe, ilustrujące zachowanie się najmniejszej niereszty kwadratowej oraz najmniejszego pierwiastka pierwotnego modulo liczba pierwsza.

EN

This paper concerns classical Diffie-Hellman key distribution protocol based on discrete logarithm problem in multiplicative groups modulo prime numbers. It has been shown here that in most cases generators of these groups are equal to their least quadratic non-residues. Despite of that observation, problem of determining a generator of multiplicative group modulo a large prime number seem to be still difficult computational problem. We quote in the paper computational arguments illustrating reciprocal behavior of the least quadratic non residues modulo primes and their least primitive roots.

Słowa kluczowe

PL

logarytm dyskretny; generator grupy skończonej; pierwiastek pierwotny; niereszta kwadratowa; schemat Diffi’ego-Hellmana; dystrybucja klucza

EN

discrete logarithm; generator of a finite group; primitive root; quadratic non-residue; Diffie-Hellman scheme; key distribution

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2018
• Tom: nr 1
• Strony: 16--21
• Opis fizyczny: Bibliogr. 6 poz., rys., tab.

Twórcy

autor

Paszkiewicz A.

• Instytut Matematyki i Kryptologii, Wojskowa Akademia Techniczna

Bibliografia

• [1] Heath-Brown D. R., Artin’s conjecture for primitive roots, Q. J. Math., Oxford ser., (2) 37 (1986), 27-38.
• [2] Hooley C., On Artin’s conjecture, J. Reine Angew. Math. 225 (1967), 209-220.
• [3] Paszkiewicz A., A. Schinzel, On the least prime primitive root modulo a prime, Math. Comp. 71 (2002), 1307-1321.
• [4] Paszkiewicz A., Badania własności liczb pierwszych i wielomianów nieprzywiedlnych pod kątem zastosowania w telekomunikacji, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa 2012.
• [5] Schinzel A., Primitive roots and quadratic non-residues, Acta Arith. 149.2 (2011), 161-170.
• [6] Wrench J. W., Jr. Evaluation of Artin’s constant and the twin-prime constant, Math. Comp. 5 (1961), 396-398.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).