REVIEW PAPER
THE AVERAGE COMPLEXITY OF THE PROBABILISTIC ALGORITHM FOR FINDING PRIMITIVE ROOTS MODULO n
1
Politechnika Warszawska
Publication date: 2014-12-05
SBN 2014;6(2): 247-258
KEYWORDS
cryptographic algorithmsprobabilistic algorithmsaverage computationalcomplexityprimitive roots modulo ncyclic groups
ABSTRACT
Primitive roots from a natural number n (i.e. generators of the multiplicative group Zn∗) 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 Zn∗ can be in natural easy way generalized on the case of arbitrary finite
cyclic groups.
REFERENCES (10)
1.
V. Shoup, A computational Introduction to Number Theory and Algebra, Cambridge University Press, 2008.
5.
A. Menezes, P. Oorschot, S. Vanstone, Handbook of Applled Cryptography, CRC Press Inc., 1997. (http://cacr.math.uwaterloo.ca/...).
6.
D. Hankerson, A. Menezes, S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2004.
8.
J. Pieprzyk, T. Hardjono, J. Seberry, Fundamentals of Computer Security, Springer, Berlin, Heidelberg, 2003.
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.
| ISSN: | 2082-2677 |
We process personal data collected when visiting the website. The function of obtaining information about users and their behavior is carried out by voluntarily entered information in forms and saving cookies in end devices. Data, including cookies, are used to provide services, improve the user experience and to analyze the traffic in accordance with the Privacy policy. Data are also collected and processed by Google Analytics tool (more).
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
