This paper presents lower bounds on the computational complexity of the discrete logarithm and related problems in the context of "generic algorithms"—algorithms that do not exploit special properties of group element encodings, other than their uniqueness as binary strings. The results show that any generic algorithm must perform Ω(p^{1/2}) group operations, where p is the largest prime dividing the group order. These bounds match known upper bounds for these problems. The paper also introduces a new method for correcting a faulty Diffie-Hellman oracle. The discrete logarithm problem involves finding x given g^x in a cyclic group G. The Diffie-Hellman problem involves finding g^{xy} given g^x and g^y. The paper analyzes the computational power of generic algorithms for these problems, showing that they cannot substantially improve upon the Pohlig-Hellman algorithm for elliptic curves without exploiting specific group element representations. The paper proves that for the discrete logarithm problem in non-cyclic groups, any generic algorithm must perform Ω(p^{r/2}) group operations, where p is the largest prime dividing the group order and r is the number of cyclic components. For the Diffie-Hellman problem, the paper shows that any generic algorithm must perform Ω(p) group operations. It also shows that when the group order is divisible by only large primes, it is hard to determine which of two possible solutions is correct. The paper also considers the security of an identification scheme based on the discrete logarithm problem. It shows that this scheme is secure against active attacks when the adversary is a generic algorithm. Additionally, the paper presents a method for correcting a faulty Diffie-Hellman oracle, which is useful in cryptographic reductions from the discrete logarithm problem to the Diffie-Hellman problem. The method allows for constructing a probabilistic algorithm that outputs a correct result with high probability, even when the oracle is occasionally incorrect.This paper presents lower bounds on the computational complexity of the discrete logarithm and related problems in the context of "generic algorithms"—algorithms that do not exploit special properties of group element encodings, other than their uniqueness as binary strings. The results show that any generic algorithm must perform Ω(p^{1/2}) group operations, where p is the largest prime dividing the group order. These bounds match known upper bounds for these problems. The paper also introduces a new method for correcting a faulty Diffie-Hellman oracle. The discrete logarithm problem involves finding x given g^x in a cyclic group G. The Diffie-Hellman problem involves finding g^{xy} given g^x and g^y. The paper analyzes the computational power of generic algorithms for these problems, showing that they cannot substantially improve upon the Pohlig-Hellman algorithm for elliptic curves without exploiting specific group element representations. The paper proves that for the discrete logarithm problem in non-cyclic groups, any generic algorithm must perform Ω(p^{r/2}) group operations, where p is the largest prime dividing the group order and r is the number of cyclic components. For the Diffie-Hellman problem, the paper shows that any generic algorithm must perform Ω(p) group operations. It also shows that when the group order is divisible by only large primes, it is hard to determine which of two possible solutions is correct. The paper also considers the security of an identification scheme based on the discrete logarithm problem. It shows that this scheme is secure against active attacks when the adversary is a generic algorithm. Additionally, the paper presents a method for correcting a faulty Diffie-Hellman oracle, which is useful in cryptographic reductions from the discrete logarithm problem to the Diffie-Hellman problem. The method allows for constructing a probabilistic algorithm that outputs a correct result with high probability, even when the oracle is occasionally incorrect.