How to calculate (a power b) mod p correctly if b is exceeding long long integer limit in c++.
How to calculate (a power b) mod p correctly if b is exceeding long long integer limit in c++.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
O(log2(b))?
yup!
Let b = b1b2.....bn(concatenated) By induction, Let x = a ^ (b1b2...bk) (mod p)
a ^ (b1b2....b(k+1)) = ( a^(b1b2....bk) ) ^ 10 * (a ^ b(k+1)) = x^10 * a^b(k+1)
now you can calculate modulo without overflow
got it! Thanks
first i need to store b. But b is exceeding the integer limit! How can i store b so that i correctly calculate (a power b) mod p. p is prime.
If b is in the form of a string, then we can calculate
with the following code:
Now
assuming that a is nonzero.
EDIT: This is exactly what DongwonShin wrote above. If b is being calculated via a DP table, then you can just take all values mod p - 1 and there won't be overflow.
got it. thanks!
but why p-1?
Fermat's theorem tells us that
if (a, p) = 1. So we can take the power by the modulo.
Thanks man!
In general if you have two co prime integers m and n, then m^p modulo n = m^(p%f(n)) modulo n, where f(n) is Euler totient function This.
For any prime n, f(n)=n-1.So, the Fermat's theorem follows from this.
I am using precomputed factorial and inverse factorial array to calculate b so should i use n-1 as the mod there also?
What if b is being calculated through nCr using precomputed factorial and inverse modulo arrays?Then also we've to use same mod p-1 ?
As long as your base(b) and p are co prime, I don't see why it can't be done. So, yes use same mod (p-1).
I tried but then for example 11*(inv[11)) didn't turn out to be 1 when i used p-1 as mod but while using p as mod it did show 1. here inv[11] = power(11,mod-2,mod) where power is fast exponential function.
What if b is calculated as a-c and c requires division operation?Then while using inverse modulo for division i should use which mod?I am confused.Please help.
Refer https://www.geeksforgeeks.org/find-abm-where-b-is-very-large/