The paper introduces a new public-key signature scheme and an authentication scheme based on discrete logarithms in a subgroup of units in \(\mathbb{Z}_p\), where \(p\) is a large prime (e.g., \(p \geq 2^{512}\)). The key innovation is using an integer \(x\) in \(\mathbb{Z}_p\) with a large prime order \(q\) (e.g., \(q \geq 2^{140}\)) as the base for the discrete logarithm. This approach improves the efficiency of signature generation and verification compared to the ElGamal scheme, reducing the bit length of signatures and minimizing message-dependent computation. The main computational effort for signature generation is done during the idle time of the processor through a preprocessing stage involving the exponentiation of a random residue modulo \(p\). The scheme combines ideas from ElGamal and Fiat-Shamir, and it can be integrated into existing authentication and key distribution schemes. The security of the scheme relies on the one-way property of exponentiation and the difficulty of computing discrete logarithms. The paper includes a detailed description of the authentication and signature scheme, along with an efficient algorithm for simulating random exponentiation.The paper introduces a new public-key signature scheme and an authentication scheme based on discrete logarithms in a subgroup of units in \(\mathbb{Z}_p\), where \(p\) is a large prime (e.g., \(p \geq 2^{512}\)). The key innovation is using an integer \(x\) in \(\mathbb{Z}_p\) with a large prime order \(q\) (e.g., \(q \geq 2^{140}\)) as the base for the discrete logarithm. This approach improves the efficiency of signature generation and verification compared to the ElGamal scheme, reducing the bit length of signatures and minimizing message-dependent computation. The main computational effort for signature generation is done during the idle time of the processor through a preprocessing stage involving the exponentiation of a random residue modulo \(p\). The scheme combines ideas from ElGamal and Fiat-Shamir, and it can be integrated into existing authentication and key distribution schemes. The security of the scheme relies on the one-way property of exponentiation and the difficulty of computing discrete logarithms. The paper includes a detailed description of the authentication and signature scheme, along with an efficient algorithm for simulating random exponentiation.