怎么计算大整数的平方并取余数？

[usdc]

最近在看 RSA，但是发现大数计算平方再取余结果不对，位数超出了。

用什么算比较好？

比如说 2790^2753 % 3233

阮一峰大大的这个例子

[luob]

快速幂取余？

[hguandl]

快速幂了解一下，二分即可。a^b % p = a ^ (b/2) % p * a ^ (b/2) % p % p

[ihainan]

快速幂的话可以分治算，比如： https://leetcode.com/problems/powx-n/description/

以及：A * B % MOD = (A % MOD) * (B % MOD) % MOD

[AlisaDestiny]

```c
int f(int a, int n, int b) {
int rs = 1;
while(n > 0) {
if(n & 1) rs = rs * a % b;
a = a * a % b;
n >>= 1;
}
return rs;
}
```
a 的 n 次方对 b 取余。

[AlisaDestiny]

https://i.loli.net/2018/08/04/5b65529dd0981.png

[pipapa]

快速幂取模正解

[usdc]

65^17 ≡ 2790 (mod 3233)
@AlisaDestiny 这个怎么算的不对

[usdc]

@AlisaDestiny 算对了 我打错了。。。。

[saluton]

质数的时候，费马小定理搞一下

[atx]

>>> (2790**2753)% 3233
65L

python 支持大整数