Menu
I want to code for calculating the value of pow(a,b)%MOD. I use C++ to code.
But the problem is the value of b can be very large. I know the log(b) time complexity method. But, the value of b might not fit in the data type "long long" of C++. For example b can be 1000000000 th Fibonacci number. Exact calculation of such a big number is itself, not possible (in time limits).
P.S. :
430
Let's look at how this relates to calculating modulus. As we said, a mod b is simply an expression representing the remainder when we divide a by b. Therefore, if a / b = q remainder r, then a mod b = r.
The first was defined in a previous lecture: a mod b denotes the remainder when we divide a by b. The "mod m" in a ≡ b (mod m) is a note on the side of the equation indicating what we mean when we say "≡" Fact: These two uses of "mod" are quite related: a ≡ b (mod m) if and only if a mod m = b mod m.
For a positive integer n, two integers a and b are said to be congruent modulo n (or a is congruent to b modulo n), if a and b have the same remainder when divided by n (or equivalently if a − b is divisible by n ). It can be expressed as a ≡ b mod n. n is called the modulus.
That's a typical task. Please (or, really, PLEASE!) read about the Euler's totient function.
And then the Euler's theorem.
The thing is you can dramatically reduce a^b to a^(b % phi(MOD)). Yes, you will need some kind of an integer factorization method, but still, no crazy ideas about actually calculating the power needed.
We did such samples by hand in my youth :) Even when the numbers where far beyond 32/64 bit range.
EDIT: Well, you live and learn. In 2008 the result is obtained:
"The totient is the discrete Fourier transform of the gcd: (Schramm (2008))"
So to calculate phi(b) one does not need to know its factors.
EDIT(2):
And the Carmichael's function is what you need to calculate to get the correct answer for any a, b and MOD.
56
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
