Deterministic Algorithm Computing All Generators: Application in Cryptographic Systems Design


Primitive elements play important roles in the Diffie-Hellman protocol for establishment of secret communication keys, in the design of the ElGamal cryptographic system and as generators of pseudo-random numbers. In general, a deterministic algorithm that searches for primitive elements is currently unknown. In information-hiding schemes, where a primitive element is the key factor, there is the freedom in selection of a modulus. This paper provides a fast deterministic algorithm, which computes every primitive element in modular arithmetic with special moduli. The algorithm requires at most O(log2p) digital operations for computation of a generator. In addition, the accelerated-descend algorithm that computes small generators is described in this paper. Several numeric examples and tables illustrate the algorithms and their properties.

Share and Cite:

B. Verkhovsky, "Deterministic Algorithm Computing All Generators: Application in Cryptographic Systems Design," International Journal of Communications, Network and System Sciences, Vol. 5 No. 11, 2012, pp. 715-719. doi: 10.4236/ijcns.2012.511074.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] W. Diffie and M. E. Hellman, “New Directions in Cryptography”, IEEE Transactions on Information Theory, Vol. 22, No. 6, 1976, pp. 644-654. Hdoi:10.1109/TIT.1976.1055638
[2] T. ElGamal, “A Public Key Crypto-System and a Signature Scheme Based on Discrete Logarithms”, IEEE Transactions on Information Theory, Vol. 31, No. 4, 1985, pp. 469-472. Hdoi:10.1109/TIT.1985.1057074
[3] D. Knuth, “The Art of Computer Programming, Vol. 2: Seminumerical Algorithms”, 3rd Edition, Addison-Wesley, Reading, 1998, pp. 18-21.
[4] C. F. Gauss, “Disquisitiones Arithmeticae”, 2nd Edition, Springer, New York, 1986.
[5] P. Ribenboim, “The New Book of Prime Number Records”, Springer, New York, 1996. Hdoi:10.1007/978-1-4612-0759-7
[6] E. Bach and J. Shallit, “Algorithmic Number Theory: Vol. 1: Efficient Algorithms”, MIT Press, Cambridge, 1996.
[7] V. S. Miller, “Use of Elliptic Curves in Cryptography”, Advances in Cryptography-CRYPTO (LNCS 218), 1986, pp. 417-426.
[8] N. Koblitz, “Elliptic Curve Crypto-Systems”, Mathematics of Computation, Vol. 48, No. 20, 1987, pp. 203-209. Hdoi:10.1090/S0025-5718-1987-0866109-5
[9] A. Menezes, P. van Oorschot and S. Vanstone, “Handbook of Applied Cryptography”, CRC Press, Boca Raton, 1997, pp. 162-164.
[10] B. Verkhovsky, “Integer Factorization of Semi-Primes Based on Analysis of a Sequence of Modular Elliptic Equations”, Int. J. of Communications, Network and System Sciences, Vol. 4, No. 10, 2011, pp. 609-615.

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.