IJCNS  Vol.5 No.11 , November 2012
Deterministic Algorithm Computing All Generators: Application in Cryptographic Systems Design
Abstract: 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.