Inverse modular exponentation

51 Views Asked by At

I want to calculate the inverse of a modular exponentation:

$c \equiv b^e \bmod m \qquad \mid c,e,m \in \mathbb{N}$

$c, e \text{ and } m$ are known and are big numbers. I know that I can calculate a "compatible" $b$ using

$b \equiv \sqrt[e]{c}$ but then b is not necessarily in $\mathbb{N}$. Taking the modulus into account one can reformulate the above equation

$b \equiv \sqrt[e]{c + i \cdot m} \qquad \mid i \in \mathbb{N}$

Iterating over $i$ will eventually yield a solution but is computationally expensive since I am working with big numbers. Is there a more efficient way to find $b$?