This paper presents a new public-key signature scheme and authentication scheme based on discrete logarithms in a subgroup of units in Z_p, where p is a sufficiently large prime (e.g., p ≥ 2^512). The scheme uses a base α in Z_p such that the order of α is a sufficiently large prime q (e.g., q ≥ 2^140). This improves the ElGamal signature scheme in terms of speed and signature length. The scheme includes an efficient algorithm for preprocessing the exponentiation of a random residue modulo p. The new signature scheme minimizes the message-dependent computation required for signature generation, which is important due to the limited computational power of smart cards. The main computation for signature generation is independent of the message and can be done during idle time. The message-dependent part involves multiplying a 140-bit integer with a 72-bit integer. The scheme is based on an interactive protocol by Chaum et al. (1988) that proves possession of a discrete logarithm. It combines ideas from ElGamal (1985) and Fiat and Shamir (1987). The scheme replaces the verifier's challenge with a hash value. The scheme's novel features include preprocessing of signature generation, which is independent of the message and can be done during idle time. It also uses a prime modulus p with p-1 having a prime factor q of appropriate size and a base α for the discrete logarithm such that α^q = 1 mod p. The length of signatures is about 212 bits, which is less than half the length of RSA signatures. The number of communication bits for the authentication scheme is also less than half that of other schemes. An efficient algorithm is proposed for simulating the exponentiation of random numbers. This algorithm reduces the computation required for generating random exponentiated residues by using additional memory to store some statistically independent exponentiated residues. The security of the scheme relies on the one-way property of the exponentiation y → α^y mod p. The paper presents the scheme, its performance, and the efficient algorithm for simulating exponentiation.This paper presents a new public-key signature scheme and authentication scheme based on discrete logarithms in a subgroup of units in Z_p, where p is a sufficiently large prime (e.g., p ≥ 2^512). The scheme uses a base α in Z_p such that the order of α is a sufficiently large prime q (e.g., q ≥ 2^140). This improves the ElGamal signature scheme in terms of speed and signature length. The scheme includes an efficient algorithm for preprocessing the exponentiation of a random residue modulo p. The new signature scheme minimizes the message-dependent computation required for signature generation, which is important due to the limited computational power of smart cards. The main computation for signature generation is independent of the message and can be done during idle time. The message-dependent part involves multiplying a 140-bit integer with a 72-bit integer. The scheme is based on an interactive protocol by Chaum et al. (1988) that proves possession of a discrete logarithm. It combines ideas from ElGamal (1985) and Fiat and Shamir (1987). The scheme replaces the verifier's challenge with a hash value. The scheme's novel features include preprocessing of signature generation, which is independent of the message and can be done during idle time. It also uses a prime modulus p with p-1 having a prime factor q of appropriate size and a base α for the discrete logarithm such that α^q = 1 mod p. The length of signatures is about 212 bits, which is less than half the length of RSA signatures. The number of communication bits for the authentication scheme is also less than half that of other schemes. An efficient algorithm is proposed for simulating the exponentiation of random numbers. This algorithm reduces the computation required for generating random exponentiated residues by using additional memory to store some statistically independent exponentiated residues. The security of the scheme relies on the one-way property of the exponentiation y → α^y mod p. The paper presents the scheme, its performance, and the efficient algorithm for simulating exponentiation.