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