Accelerated Search for Gaussian Generator Based on Triple Prime Integers
Boris S. Verkhovsky and Md Shiblee Sadik
DOI : 10.3844/jcssp.2009.614.618
Journal of Computer Science
Volume 5, Issue 9
Problem statement: Modern cryptographic algorithms are based on complexity of two problems: Integer factorization of real integers and a Discrete Logarithm Problem (DLP). Approach: The latter problem is even more complicated in the domain of complex integers, where Public Key Cryptosystems (PKC) had an advantage over analogous encryption-decryption protocols in arithmetic of real integers modulo p: The former PKC have quadratic cycles of order O (p2) while the latter PKC had linear cycles of order O(p). Results: An accelerated non-deterministic search algorithm for a primitive root (generator) in a domain of complex integers modulo triple prime p was provided in this study. It showed the properties of triple primes, the frequencies of their occurrence on a specified interval and analyzed the efficiency of the proposed algorithm. Conclusion: Numerous computer experiments and their analysis indicated that three trials were sufficient on average to find a Gaussian generator.
© 2009 Boris S. Verkhovsky and Md Shiblee Sadik. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.