Solution to $a^k \equiv b \pmod c$

Question

I was trying to find the smallest solution for $k$ to the following equation. $ a^k = b\bmod c$. The problem is, the $'k'$ I get may not be the smallest. To find the smallest such $k$, I need to compute $O_c(a)$. I was only able to find resources that say that $O_c(a)|\phi(c)\ or \ \lambda(c)$ when $a$ and $c$ are coprime. Is there any such relation when $a$ and $c$ are non-coprime?

Answer 1

Modulo prime powers $p^m$, the problem becomes much easier: either $p$ divides $a$, in which case we're just looking at the powers of $p$ dividing $a$ and $b$, or else $p$ doesn't divide $a$, in which case your procedure using the order works. Indeed, modulo prime powers, it's pretty easy to find not just a particular $k$ but actually all positive integers $k$ that satisfy $a^k\equiv b\pmod{p^m}$ (it will consist either of a finite set or a full arithmetic progression).

Therefore: factor $c$ into its prime power factors, find the corresponding set of positive integers $k$ for each prime power factor, and then find the smallest integer $k$ that is in the intersection of all those sets. This last task boils down to a Chinese remainder theorem calculation, due to the structure of the individual sets.

Answer 2

Solving $a^k \equiv b \:(\mathrm{mod}\:n)$ is called the discrete logarithm problem (see article for list of special case algorithms), and modular exponentiation for groups whose minimum order is high* is a classic example of a one-way function. Such functions are the foundation of modern cryptography, such as can be seen in Diffie–Hellman key exchange and the RSA asymmetric encryption scheme.

If the discrete logarithm problem can be solved in polynomial time — which it can be with sufficient quantum computational power; see Shor's algorithm — then such schemes are not secure.

With classical computation, the only known feasible way to solve the problem in all cases is to enumerate $a^k \mathrm{mod}\: n$ for all $k$ between 1 and $n$.

---

*particularly when the modulus $n$ is a large prime (though I understand you're not interested in that), so that $n$ is near minimal for a given level of security, and a generator $g$ of the group exists, whence we like to choose $a=g$ for maximal security.