Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/37AC6B13-2596-4AEE-B751-51D4BADB1933 | ||
| Year | 2022 | ||
| Type of Item | Diploma Work | ||
| License |
|
||
| 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 |
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.
Copyright © DIAS 2013
