Question

Describe a brute force algorithm for solving the discrete logarithm problem and find the worst-case and average-case time complexity of this algorithm.

Short answer

Hence O(p log p) is the complexity during the worst case and average case.

Step-by-step solution

Step: 1

The procedure of this algorithm is such that p: prime

r: primitive root in $zp$and a: positive integer in $zp$.

Now e is the discrete logarithm of a modulo p, when $r^{e}modp=a,e$ such that $0\le e\le p-1$

Determine $r^{k}modp,\text{for}\mathrm{k}=0,1,\dots ,\mathrm{p}-1$, until the resulting gain $r^{k}modp=a$, which yields k.

Hence O(p log p) is the complexity during the worst case and average case.