Średnia złożoność obliczeniowa probabilistycznego algorytmu wyszukiwania pierwiastków pierwotnych modulo n

• Autorzy: Adamski T.

Warianty tytułu

EN

The Average Complexity of the Probabilistic Algorithm for Finding Primitive Roots Modulo n

• Języki publikacji: PL

Abstrakty

PL

W pracy oszacowano średnią złożoność obliczeniową probabilistycznego algorytmu wyszukiwania pierwiastków pierwotnych modulo n. Uzyskany wynik może być w naturalny sposób uogólniony na przypadek algorytmu wyszukiwania generatorów dowolnej skończonej grupy cyklicznej jeśli znamy rozkład na czynniki pierwsze rzędu tej grupy.

EN

Primitive roots from a natural number n (i.e. generators of the multiplicative group Z* _n) play an important role in many cryptographic algorithms like public key ciphers, digital signatures and key agreement algorithms. In the paper, proof of correctness of the probabilistic algorithm for finding primitive roots is given along with assessment of its average computational complexity. Results obtained for the multiplicative group Z* _n can be in natural easy way generalized on the case of arbitrary finite cyclic groups.

Słowa kluczowe

PL

algorytmy probabilistyczne; pierwiastki pierwotne modulo n; generatory skończonych grup cyklicznych; algorytmy kryptograficzne; złożoność obliczeniowa

EN

cryptographic algorithms; probabilistic algorithms; average computational complexity; primitive roots modulo n; cyclic groups

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Studia Bezpieczeństwa Narodowego
• Rocznik: 2014
• Tom: R. 4, Nr 6
• Strony: 247--257
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Adamski T.

• Instytut Systemów Elektronicznych; Wydział Elektroniki i Technik Informacyjnych Politechniki Warszawskiej

Bibliografia

• [1] V. Shoup, A computational Introduction to Number Theory and Algebra, Cambridge University Press, 2008.
• [2] N. Koblitzc, A Course in Number Theory and Cryptography, Springer, New York 1994.
• [3] C. Bagiński, Introduction to Group Theory (in Polish), Script, Warszawa 2002.
• [4] W. Narkiewicz, Number Theory (in Polish), PWN. Warszawa, 1990.
• [5] A. Menezes, P. Oorschot, S. Vanstone, Handbook of Applled Cryptography, CRC Press Inc., 1997. (http://cacr.math.uwaterloo.ca/hac).
• [6] D. Hankerson, A. Menezes, S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2004.
• [7] S. Yan; Number Theory for Computing, Springer, Berlin-Heidelberg, 2002.
• [8] J. Pieprzyk, T. Hardjono, J. Seberry, Fundamentals of Computer Security, Springer, Berlin, Heidelberg, 2003.
• [9] A. Białynicki, Algebra, Warszawa, PWN, 2010.
• [10] A. Paszkiewicz, Badania własności liczb pierwszych i wielomianów nieprzywiedlnych pod kątem zastosowania w telekomunikacji, Oficyna Wydawnicza P.W.; Warszawa 2012.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).