最近在看 RSA，但是发现大数计算平方再取余结果不对，位数超出了。
用什么算比较好？
比如说 2790^2753 % 3233
阮一峰大大的这个例子
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 3019 days ago, the information mentioned may be changed or developed.
 |
1
快速幂取余？
|
1 |
2
快速幂了解一下，二分即可。a^b % p = a ^ (b/2) % p * a ^ (b/2) % p % p
|
 |
3
快速幂的话可以分治算，比如： https://leetcode.com/problems/powx-n/description/
以及：A * B % MOD = (A % MOD) * (B % MOD) % MOD |
 |
4
```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 取余。 |
 |
pipapaAug 4, 2018 via Android
6
快速幂取模正解
|
 |
7
65^17 ≡ 2790 (mod 3233)
@AlisaDestiny 这个怎么算的不对 |
|
8
@AlisaDestiny 算对了 我打错了。。。。
|
 |
salutonAug 4, 2018
9
质数的时候，费马小定理搞一下
|
 |
atxAug 6, 2018
10
>>> (2790**2753)% 3233
65L python 支持大整数 |
Select Language