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

2018-08-04 14:37:52 +08:00
 channg

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

用什么算比较好?

比如说 2790^2753 % 3233

阮一峰大大的这个例子

2698 次点击
所在节点    程序员
10 条回复
luob
2018-08-04 14:47:17 +08:00
快速幂取余?
hguandl
2018-08-04 14:48:33 +08:00
快速幂了解一下,二分即可。a^b % p = a ^ (b/2) % p * a ^ (b/2) % p % p
ihainan
2018-08-04 14:52:18 +08:00
快速幂的话可以分治算,比如: https://leetcode.com/problems/powx-n/description/

以及:A * B % MOD = (A % MOD) * (B % MOD) % MOD
AlisaDestiny
2018-08-04 15:08:34 +08:00
```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
2018-08-04 15:15:55 +08:00
pipapa
2018-08-04 15:25:09 +08:00
快速幂取模正解
channg
2018-08-04 16:37:59 +08:00
65^17 ≡ 2790 (mod 3233)
@AlisaDestiny 这个怎么算的不对
channg
2018-08-04 16:39:31 +08:00
@AlisaDestiny 算对了 我打错了。。。。
saluton
2018-08-04 17:12:38 +08:00
质数的时候,费马小定理搞一下
lc1450
2018-08-06 11:41:40 +08:00
>>> (2790**2753)% 3233
65L

python 支持大整数

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/476844

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX