The average time complexity of probabilistic algorithms for finding generators in finite cyclic groups

• Autorzy: Adamski T. , Nowakowski W.

Identyfikatory

DOI

10.1515/bpasts-2015-0112

• Języki publikacji: EN

Abstrakty

EN

Generators of finite cyclic groups play important role in many cryptographic algorithms like public key ciphers, digital signatures, entity identification and key agreement algorithms. The above kinds of cryptographic algorithms are crucial for all secure communication in computer networks and secure information processing (in particular in mobile services, banking and electronic administration). In the paper, proofs of correctness of two probabilistic algorithms (for finding generators of finite cyclic groups and primitive roots) are given along with assessment of their average time computational complexity.

Słowa kluczowe

EN

probabilistic algorithm; average time complexity; group generator; cyclic groups; primitive roots; primitive polynomials

PL

algorytm probabilistyczny; generator grupy; grupy cykliczne; wielomian

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2015
• Tom: Vol. 63, nr 4
• Strony: 989--996
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Adamski T.

• Institute of Electronic Systems, Warsaw University of Technology, 15/19 Nowowiejska St., 00-662 Warsaw, Poland

autor

Nowakowski W.

• Institute of Mathematical Machines, 34 Krzywickiego St., 02-078 Warsaw, Poland

Bibliografia

• [1] V. Shoup, A Computational Introduction to Number Theory and Algebra, University Press, Cambridge, 2008.
• [2] N. Koblitz, A Course in Number Theory and Cryptography, Springer, New York, 1994.
• [3] C. Bagiński, Introduction to Group Theory, SCRIPT, Warszawa, 2002, (in Polish).
• [4] W. Narkiewicz, Number Theory, PWN,Warszawa, 1990, (in Polish).
• [5] A. Menezes, P. Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press Inc., London, 1997, (http://cacr.math.uwaterloo.ca/hac).
• [6] D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, New York, 2004.
• [7] S. Yan, Number Theory for Computing, Springer, Berlin, 2002.
• [8] J. Pieprzyk, T. Hardjono, and J. Seberry, Fundamentals of Computer Security, Springer, Berlin, 2003.
• [9] A. Białynicki-Birula, Algebra, PWN, Warszawa 2009, (in Polish).