I am dealing with the following question:
Given a,b,c,d, p positive integers, I wanna compute a^(b^(c^d)) mod 2p+1.
Given that p is sophie-germain. That is, 2p+1 is also prime.
Any ideas?
Asked
Active
Viewed 109 times
1
-
Do you know Fermat's little theorem? – Tobias Kildetoft Feb 17 '15 at 09:27
-
Ofcourse. I'm familiar with the field of this sort of algebra. – itaymeller Feb 17 '15 at 09:50
-
Then apply that to the exponents in succession. – Tobias Kildetoft Feb 17 '15 at 09:51
-
I'm not sure I understand. Fermat's little theorem will guarantee that a^2p will be equal to one. Correct me if i'm wrong, but if at any stage b^(c^d) is more than 2p, then we are positive that the result is infact 1? – itaymeller Feb 17 '15 at 09:56
-
Not quite. But it allows you to reduce the exponent mod $2p$ and then use the same on the exponent in the exponent. – Tobias Kildetoft Feb 17 '15 at 09:58
-
Tobias, that solution works for a^(b^c) mod (2p+1) == a^(b^c mod2p) mod2p+1. But how can I compute b^(c^d)? With the same P? – itaymeller Feb 17 '15 at 11:20
-
Very close to this question: http://math.stackexchange.com/q/1151931/24160 – alexwlchan Feb 17 '15 at 13:02
1 Answers
1
Here are my comments in more detail.
Fermat's little theorem allows us too first reduce $b^{(c^d)}$ modulo $2p+ 1 - 1 = 2p$ since $2p+1$ is a prime.
Now, we actually need a slightly stronger result to go further, namely Euler's generalization of the above. This allows us to reduce the new exponent $c^d$ mod $\varphi(2p) = p-1$ (or modulo $2$ if $p=2$), at least when $b$ is coprime to $2p$.
So in the end we need to find $c^d$ modulo $p-1$ which can be done by repeated squaring.
Tobias Kildetoft
- 21,247
-
Brilliant. Much obliged! How can we tell Euler's(2p) is p-1? There's no guarantee that b is coprime to 2p. or is there (Being a Sophie-germain)? – itaymeller Feb 17 '15 at 13:02
-
@Jojo If $p\neq 2$ then $\varphi(2p) = \varphi(2)\varphi(p) = p-1$. And no, $b$ might not be coprime to $2p$, as it might be divisible by either of $2$ or $p$ (if it is divisible by both, then this is of course easy). – Tobias Kildetoft Feb 17 '15 at 13:11
-
-
What if b is not coprime? than it is divisible by 2, or by p. How could that help? – itaymeller Feb 17 '15 at 17:32
-
@TobiasKildetoft But what if $(b,2p)\neq 1$? Meaning $b$ is even. How can we calculate $ b^{c^d} \mod 2p $ then? – Roman Vale Feb 18 '15 at 09:32
-
@RomanVale It need not mean that $b$ is even (it could also be divisible by $p$). One can then try to find the smallest $m$ such that $b^m \equiv b\pmod{2p}$ instead. – Tobias Kildetoft Feb 18 '15 at 10:47
-