The naive solution goes through all possible values of k and takes $O(n)$ time.
The baby-step, giant-step algorithm solves the problem more efficiently using the meet in the middle trick.

Let's write k = $i([sqrt(n)] + 1) + j$

Let's write k = $i[sqrt(n)] + j$

Notice that $i <= sqrt(n)$ and $j <= sqrt(n)$.

Replacing k in the equality we get $p^(i ([sqrt(n)] + 1) + j)^ = q (mod n)$.
Dividing by $p^j^$ we get $p^(i[sqrt(n)] + 1)^ = qp^-j^ (mod n)$.

Replacing k in the equality we get $p^(i[sqrt(n)] + j)^ = q (mod n)$.
Dividing by $p^j^$ we get $p^i[sqrt(n)]^ = qp^-j^ (mod n)$.

At this point we can brute force through the numbers on each side of the equality and find a colision.
The algorithm takes $O(sqrt(n))$ space and $O(sqrt(n))$ time.

public

protected