Given
$$ a^n \bmod b = x,$$
how can we find $m$ such that
$$a^m \bmod c = x?$$
Edit: Alternatively, since we know $a$, $c$, and $x$, how you can solve for $m$ directly?
Thanks for your help!
Asked
Active
Viewed 76 times
0
-
Is $c$ a divisor of $b$? – Daniel Fischer Dec 25 '13 at 19:29
-
Not necessarily – user117473 Dec 25 '13 at 19:30
-
Then it's not possible...? – Shahar Dec 25 '13 at 19:32
-
3Then you can't determine the remainder modulo $c$. The best you have is the remainder modulo $\gcd (b,c)$. – Daniel Fischer Dec 25 '13 at 19:32
-
Are $a$, $b$, $c$ and $x$ given? Or are you looking for a general procedure? – user44197 Dec 25 '13 at 19:50
-
Im looking for a general procedure – user117473 Dec 25 '13 at 19:53
-
Even if you know $x$ and $c$ you have to solve $m \log a = \log x$ where all these are calculated modulo $c$. Now it is generally believed that find the $\log$ is difficult (many cryptographic schemes rely on this). You could always write the answer in terms of primitive roots of $c$. – user44197 Dec 25 '13 at 19:55
-
Is it possible when you know $a$, $n$, $b$, $c$, and $x$? – user117473 Dec 25 '13 at 19:58
-
So basically all the variables are constant except $m$ here? – Ethan Splaver Dec 25 '13 at 20:03
-
If you know $a$, $c$ and $x$ you can determine those $m$ such that $a^m \mod c = x$ (e.g. by examining $a^j \mod c$ for positive integers $j$ until you get $1$). But $a^n \mod b$ is irrelevant to this. – Robert Israel Dec 25 '13 at 20:10
-
@Ethan that is correct – user117473 Dec 25 '13 at 20:12
-
@RobertIsrael I'm interested in finding a method other than observation. – user117473 Dec 25 '13 at 20:15
-
@user44197 Then can't you just solve $a^m\equiv x \text{ mod } c$ directly using a discrete logarithm since you know both $a,x,c$? – Ethan Splaver Dec 25 '13 at 20:15
-
How would I go about solving using a discrete logarithm? – user117473 Dec 25 '13 at 20:17
-
Yes, then I don't see the point of $a^n\equiv x \mod b$. It is hard to tease out what is given and what is not. – user44197 Dec 25 '13 at 20:18
-
@user117473 Where did you get this problem from? – Ethan Splaver Dec 25 '13 at 20:20
-
@Ethan It is one I came up with on my own. I was simply curious about it. – user117473 Dec 25 '13 at 20:21
1 Answers
1
Here is a general procedure for solving $$ a^m \equiv x \mod c $$ I will assume that $x$ and $c$ are co-prime and $r$ is primitive root of $c$, i.e $$ r^{\phi(c)} \equiv 1 \mod c ~~\hbox{and} ~~ r^k \not \equiv 1 \mod c, ~1\le k < \phi(c) $$ We can always find an $m$ so that $r^\alpha = x$. $\alpha$ is the discrete logarithm of $x$. Let $a = r^\beta$. Then the original equation becomes
$$ \left(r ^\beta\right)^m=r^\alpha \mod c$$
The solution to this is $$ \beta m = \alpha \mod \phi(c) $$
Hope this helps
user44197
- 9,730
-
But that procedure is not computationally effective in general since computing discrete logs is notoriously difficult. Perhaps the OPs problem has further structure that makes it easier. – Bill Dubuque Dec 25 '13 at 20:37
-
I agree! In one of my comments I said that the difficulty of computing discrete logarithms is the basis of many cryptographic system. However, he wanted a specific procedure and I don't know any general procedure than what I wrote. – user44197 Dec 25 '13 at 20:41