I'm recently started learning modular mathematics as part of an advanced cryptology unit. It's relatively new to me. I'm trying to find out how to express/determine a,b given $a^b\pmod p\equiv x$ , where p is prime
Any help/feedback would be great.
Cheers!
On
The only thing you can say for sure is that $x^1\equiv x \pmod p$. If you want to say more, this will depend strongly on $x,p,\,$ e.g. for a specific $p$ some $x$ are squares, i.e. there exist some $a$ with $a^2\equiv x \pmod p$, and some are no squares.
Most $x$ will have an inverse $a$ with $a^{-1}\equiv x \pmod p.$
On
Without giving a complete solution, I give a trick that is useful for such equations with one unknown. The idea is to use the following theorem of Fermat :
Theorem : Let $p>2$ be a prime number. Then for all $n$ prime with $p$, one has $$n^{p-1} \equiv 1 \pmod{p}.$$
Hence, the solutions of $$a^x \equiv 1 \pmod{p}$$ ($x$ is the unknown) are the multiples of divisors of $p-1$. So it is enough to try each divisor.
Another example is the equation $$x^a \equiv b \pmod{p}$$ with $a-1$ and $b$ prime with $p$. Thanks to Bezout, we find $u$ and $v$ such that $$ua+v(p-1)= 1.$$ Hence $$b^u \equiv x^{ua} \equiv x \pmod{p},$$ and the equation is solved.
In the general case with two unknown the problem gets really more complicated, I guess you can just try to find methods in very particular cases.
The answer is a=x and b=1. This comes from the equation $a^b = x^1$.