bq. Given n a prime number and p, q two integers between 0 and n-1, find k such that  p^k^ = q (mod n).

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$

This problem can be solved using the baby step, giant step algorithm which uses the meet in the middle trick.
We can write k = $i([sqrt(n)] + 1) + 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)$.

At this point we can brute force through the numbers on each side of the equality and find a colision.
 

Using meet in the middle becomes obvious. 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.
h2. Bidirectional search