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

Tomasz Adamski , Wojciech Nowakowski


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.
Author Tomasz Adamski (FEIT / PE)
Tomasz Adamski,,
- The Institute of Electronic Systems
, Wojciech Nowakowski
Wojciech Nowakowski,,
Journal seriesBulletin of the Polish Academy of Sciences, Technical Sciences, ISSN 0239-7528, (A 20 pkt)
Issue year2015
Publication size in sheets0.5
Keywords in English probabilistic algorithm, average time complexity, group generator, cyclic groups, primitive roots, primitive polynomials
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 20.0, 27-03-2017, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 27-03-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2015 = 1.087 (2) - 2015=0.941 (5)
Citation count*1 (2018-11-12)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.