1. Introduction
The concept of a digital signature was introduced in 1976 by Diffie and Hellman. One of the powerful and practical signature schemes was produced by ElGamal [3] in 1985. El-Kassar et al. [4] and El-Kassar and Haraty [5] modified the ElGamal signature schemes from the domain of natural integers, , to two principal ideal domains, namely the domain of Gaussian integers, , and the domain of polynomials over finite fields, , by extending the arithmetic needed for the modifications to these domains. In both cases, it was shown that the same prime modulus used in the classical ElGamal scheme can be used in the new settings to produce larger cyclic groups; hence, the message space, the keyspace and signature set are enlarged without any additional effort. The larger key space makes the new schemes more secure and harder to break. Moreover, it was shown in both cases that the arithmetic is easy and efficient to apply.