Any pointers on this troublesome algorithm?

[chants]

The general number field sieve is faster than a naive brute force, and there are a variety of other techniques to reduce prime checking in DLs. It is sub-exponential but seems to be above polynomial in time to find a solution.

I would suggest studying discrete mathematics, computer algebra, cryptography and algorithms if you want to be great at reversing these types of scenarios. Sitting and looking at assembly code is not so helpful if you are not versed in the algorithms and mathematics behind what is going on. However it is a theoretical and long journey to master. You can known Fermat's little theorem and Carmichael numbers and other useful tools in primality testing and modular exponentiation and so forth.

An example solution which is more efficient than exhaustive brute force is as follows: given b^l=n (mod p) and you want to solve for the smallest l with just normal integer sizes:

		unsigned int c;
		long long an = 1; //x0 = b ^ sqrt(p) % p
		for (c = 0; c * c < p; c++) {
			an = an * b % p;
		}
		unsigned int d = c; //sqrt(p)
		std::map<long long, long long> m;
		long long cur = an; //x(i) = b ^ sqrt(p) % p to b ^ (sqrt(p) ^ sqrt(p)) % p
		for (c = 1; c <= d; c++) {
			if (!m.count(cur))
				m[cur] = c;
			cur = cur * an % p;
		}
		cur = n; //y(i) = nb % p to n(b ^ sqrt(p)) % p
		long long minans = -1;
		for (c = 0; c <= d; c++) {
			if (m.count(cur)) {
				long long ans = m[cur] * d - c;
				if (ans < p) {
					minans = minans == -1 ? ans : (ans < minans ? ans : minans);
				}
			}
			cur = cur * b % p;
		}
		if (minans != -1) std::cout << minans << std::endl;
		else std::cout << "no solution" << std::endl;

If you can explain the mathematics behind it, then you will be at a very good problem solving level in this area.