The average time complexity of probabilistic algorithms for finding generators in finite cyclic groups
Tomasz Adamski , Wojciech Nowakowski
AbstractGenerators of ﬁnite cyclic groups play important role in many cryptographic algorithms like public key ciphers, digital signatures, entity identiﬁcation 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 ﬁnding generators of ﬁnite cyclic groups and primitive roots) are given along with assessment of their average time computational complexity.
|Journal series||Bulletin of the Polish Academy of Sciences, Technical Sciences, ISSN 0239-7528, (A 20 pkt)|
|Publication size in sheets||0.5|
|Keywords in English||probabilistic algorithm, average time complexity, group generator, cyclic groups, primitive roots, primitive polynomials|
|Score|| = 20.0, 27-03-2017, ArticleFromJournal|
= 25.0, 27-03-2017, ArticleFromJournal
|Publication indicators||: 2015 = 1.087 (2) - 2015=0.941 (5)|
|Citation count*||1 (2018-11-12)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.