Accelerated Search for Gaussian Generator Based on Triple Prime Integers

Abstract

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 (p²) 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.