给我一个使用Miller-Rabin算法生成随机大素数的c++代码,要求生成大素数的时间尽量少
时间: 2023-06-09 10:05:10 浏览: 174
以下是使用Miller-Rabin算法生成随机大素数的C++代码:
```c++
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;
LL n;
// 快速幂
LL qpow(LL a, LL b, LL mod) {
LL ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
// Miller-Rabin 素性测试
bool Miller_Rabin(LL p) {
if (p < 2) return false;
if (p != 2 && p % 2 == 0) return false;
LL d = p - 1;
while (d % 2 == 0) d >>= 1;
for (int i = 0; i < 10; i++) {
LL a = rand() % (p - 1) + 1;
LL t = d;
LL y = qpow(a, t, p);
while (t != p - 1 && y != 1 && y != p - 1) {
y = y * y % p;
t <<= 1;
}
if (y != p - 1 && t % 2 == 0) return false;
}
return true;
}
// 生成随机大素数
LL Prime_Generator(LL bit) {
while (true) {
n = rand() & ((1LL << bit) - 1);
n |= 1LL << (bit - 1); // 随机生成 bit 位数字
if (Miller_Rabin(n)) return n; // 如果是素数就返回
}
}
int main () {
srand(time(NULL));
LL P = Prime_Generator(1024); // 生成 1024 位的素数
printf("%lld\n", P);
return 0;
}
```
此代码使用Miller-Rabin算法进行素性测试,随机生成一些a值进行测试,根据Miller-Rabin算法的特性,如果p是合数,则有至少三分之一的a不满足龟速算法的条件,若进行10次随机测试均满足则p极大可能为素数。编写中对于大素数的生成,使用了左移操作,及按照要求随机生成2^n位的数字。
阅读全文