Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Properties of primitive roots of prime numbers and applications

Konidakis Ioannis

Full record


URI: http://purl.tuc.gr/dl/dias/37AC6B13-2596-4AEE-B751-51D4BADB1933
Year 2022
Type of Item Diploma Work
License
Details
Bibliographic Citation Ioannis Konidakis, "Properties of primitive roots of prime numbers and applications", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2022 https://doi.org/10.26233/heallink.tuc.94431
Appears in Collections

Summary

In this work we derive a few properties of primitive roots of prime numbers and use them to generate an algorithm that functions as a Lehmer pseudo-random number generator, as well as a solution to the discrete logarithm problem. Specifically, we capitalize patterns in the exponentiation of primitive roots to achieve the calculation of the primitive root's power sequence by mainly using additions instead of multiplications. Our new generated algorithm has three different forms, their difference lying on their initialization step. We test our algorithm as a Lehmer pseudo-random number generator against a multiplication-based brute-force algorithm, achieving satisfying results for all three initialization forms. Finally, we use our algorithm to solve the discrete logarithm problem, testing it against Shanks' Baby Step - Giant Step algorithm. The results show that Shanks' algorithm, even for small numbers, achieves a lower cost than all forms of our algorithm. However, our algorithm could be implemented in Baby Step - Giant Step to potentially reduce its total cost.

Available Files

Services

Statistics