这是一个创建于 2295 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近在看 RSA，但是发现大数计算平方再取余结果不对，位数超出了。
用什么算比较好？
比如说 2790^2753 % 3233
阮一峰大大的这个例子
 |
1
luob 2018-08-04 14:47:17 +08:00  1
快速幂取余？
|
 |
2
hguandl 2018-08-04 14:48:33 +08:00 1
快速幂了解一下，二分即可。a^b % p = a ^ (b/2) % p * a ^ (b/2) % p % p
|
 |
3
ihainan 2018-08-04 14:52:18 +08:00 1
快速幂的话可以分治算，比如： https://leetcode.com/problems/powx-n/description/
以及：A * B % MOD = (A % MOD) * (B % MOD) % MOD |
 |
4
AlisaDestiny 2018-08-04 15:08:34 +08:00 1
```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 取余。 |
|
5
AlisaDestiny 2018-08-04 15:15:55 +08:00
|
 |
6
pipapa 2018-08-04 15:25:09 +08:00 via Android
快速幂取模正解
|
 |
7
channg OP 65^17 ≡ 2790 (mod 3233)
@AlisaDestiny 这个怎么算的不对 |
|
8
channg OP @AlisaDestiny 算对了 我打错了。。。。
|
 |
9
saluton 2018-08-04 17:12:38 +08:00
质数的时候，费马小定理搞一下
|
 |
10
lc1450 2018-08-06 11:41:40 +08:00
>>> (2790**2753)% 3233
65L python 支持大整数 |
Select Language