Share This Article:

Deterministic Algorithm Computing All Generators: Application in Cryptographic Systems Design

Full-Text HTML Download Download as PDF (Size:73KB) PP. 715-719
DOI: 10.4236/ijcns.2012.511074    3,516 Downloads   4,980 Views   Citations


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.

Cite this paper

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.


[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.

comments powered by Disqus

Copyright © 2018 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.