Is there a way of calculating the exponent x after a modulo?

27 Views Asked by At

Is it possible to calculate x, knowing all other parameters?

$y = b^x \pmod c$

My intention would be to do this with the logarithm but this brings up a new unkown parameter n:

$y+nc= b^x$

$x = \frac{\ln(y + nc)}{\ln(b)}$

So maybe there is another way of doing this in the world of modular arithmetic?

1

There are 1 best solutions below

0
On BEST ANSWER

The short answer is "there is no quick way".

A longer answer calls for much more number theory than is usually available at the algebra-precalculus level. First you have to figure out for which integers $c$ there is a $b$ for which there is always a solution $x$ for any $y$.

If $c$ is prime then there are values of $b$ that work, but finding them is pretty much trial and error. And once you have a good $b$, finding $x$ when you're told $y$ is also pretty much trial and error. In fact if you could find a fast way to do that you'd be on track to breaking some security measures. Several comments tell you this is the discrete logarithm problem.

So if you have any particular examples you need to work out, all you can do is try all the values of $x$ modulo $c$ and see if you ever get $y$.