Deterministic Algorithm Computing All Generators: Application in Cryptographic Systems Design
- 1 Computer Science Department, New Jersey Institute of Technology, University Heights, Newark, USA
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(log 2 p ) 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.
- 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
- 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
- D. Knuth, “The Art of Computer Programming, Vol. 2: Seminumerical Algorithms”, 3rd Edition, Addison-Wesley, Reading, 1998, pp. 18-21.
- C. F. Gauss, “Disquisitiones Arithmeticae”, 2nd Edition, Springer, New York, 1986.
- P. Ribenboim, “The New Book of Prime Number Records”, Springer, New York, 1996. Hdoi:10.1007/978-1-4612-0759-7
- E. Bach and J. Shallit, “Algorithmic Number Theory: Vol. 1: Efficient Algorithms”, MIT Press, Cambridge, 1996.
- V. S. Miller, “Use of Elliptic Curves in Cryptography”, Advances in Cryptography-CRYPTO (LNCS 218), 1986, pp. 417-426.
- 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
- A. Menezes, P. van Oorschot and S. Vanstone, “Handbook of Applied Cryptography”, CRC Press, Boca Raton, 1997, pp. 162-164.
- 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.