Recently, I coded to realized RSA algorithm, I was confused by MOD-POWER problem, I couldn't why the equation is true, I can't give the proof of this equation:
'a^b % m = (...((a % m) * a) % m) ......* a) % m'
from mathematical view?
Asked
Active
Viewed 45 times
1
-
I'm voting to close this question as off-topic because it is not about programming. – High Performance Mark Jul 13 '16 at 07:31
-
I'm voting to close this question as off-topic because it is about [math.se] instead of programming or software development. – Pang Jul 14 '16 at 02:10
2 Answers
0
From the basic things we know about multiplication in modular arithmetic.
We know that (a * b) % m == ((a % m) * (b % m)) % m
Vatine
- 20,782
- 4
- 54
- 70
0
As the power is defined recursively as
a^0 = 1, a^b = a^(b-1) * a
you prove the modular formula also per induction, i.e., using
a^b % m = ( ( a^(b-1) % m ) * ( a % m ) ) % m
as step.
Lutz Lehmann
- 25,219
- 2
- 22
- 51