We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The question is about finding (a^b)mod MOD it can be done simply by using modular exponentiation,I don't under why the editorialist used fermats little theorem and why he calculated b%(MOD-1).Any help would be highly appreciated.
Because exponentiation to power b=10^100000 would require at least 300000 modular multiplications. And just reading b into binary representation might require 100000^2 multiplications, if you do not use BigInteger in Java or some internal very long integers say in Python.
In what language did you solve the problem, and what are the timings?
I dont know if its too late to answer, but this is regarding your question about b % (MOD - 1). Consider Fermat's theorem, a^(p - 1) = 1(mod p) when p is prime. Now the question dictates the calculation to be a^b % p. If b is a multiple of (p - 1) say (p - 1)x, then a^b % p is a^((p - 1)x) % p which is 1 since 1^x(mod p) = 1(mod p). Now if b is not a multiple of (p - 1) say ((p - 1)x + y), then we have a^b % p as (a^(p - 1)x + y) % p. Split this into two terms and take mods to multiply (its a property of mods).
((a^(p - 1)x) % p) * (a^y % p) = 1^(x)*(a^y % p) which is the answer to your question. y = b % (p - 1) = ((p - 1)x + y) % (p - 1). Hope this helps!
Power of large numbers
You are viewing a single comment's thread. Return to all comments →
The question is about finding (a^b)mod MOD it can be done simply by using modular exponentiation,I don't under why the editorialist used fermats little theorem and why he calculated b%(MOD-1).Any help would be highly appreciated.
Because exponentiation to power b=10^100000 would require at least 300000 modular multiplications. And just reading b into binary representation might require 100000^2 multiplications, if you do not use BigInteger in Java or some internal very long integers say in Python.
In what language did you solve the problem, and what are the timings?
I dont know if its too late to answer, but this is regarding your question about b % (MOD - 1). Consider Fermat's theorem, a^(p - 1) = 1(mod p) when p is prime. Now the question dictates the calculation to be a^b % p. If b is a multiple of (p - 1) say (p - 1)x, then a^b % p is a^((p - 1)x) % p which is 1 since 1^x(mod p) = 1(mod p). Now if b is not a multiple of (p - 1) say ((p - 1)x + y), then we have a^b % p as (a^(p - 1)x + y) % p. Split this into two terms and take mods to multiply (its a property of mods). ((a^(p - 1)x) % p) * (a^y % p) = 1^(x)*(a^y % p) which is the answer to your question. y = b % (p - 1) = ((p - 1)x + y) % (p - 1). Hope this helps!
Thanks bro, your comment helped a lot!!
thanku so much :)