c++ - 使用 GMP 库 C++ 的大素数循环
问题描述
这是我第一次使用 gmp 库,所以我真的迷路了,我找到了一个在 c++ 中实现“miller rabin primality test”的代码,但我希望能够将它应用于具有任意精度的整数,所以我安装GMP库。
问题是,我不知道 GMP 库实际上是如何工作的(我已经阅读了几页手册,但我对它的了解也很少,因为我什至没有学习过面向对象编程),我想要为了使素数测试能够输入大约 1000-2000 位的整数“num”,代码如下:
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <gmpxx.h>
#include <gmp.h>
#define ll long long
using namespace std;
/*
* calculates (a * b) % c taking into account that a * b might overflow
*/
ll mulmod(ll a, ll b, ll mod)
{
ll x = 0,y = a % mod;
while (b > 0)
{
if (b % 2 == 1)
{
x = (x + y) % mod;
}
y = (y * 2) % mod;
b /= 2;
}
return x % mod;
}
/*
* modular exponentiation
*/
ll modulo(ll base, ll exponent, ll mod)
{
ll x = 1;
ll y = base;
while (exponent > 0)
{
if (exponent % 2 == 1)
x = (x * y) % mod;
y = (y * y) % mod;
exponent = exponent / 2;
}
return x % mod;
}
/*
* Miller-Rabin primality test, iteration signifies the accuracy
*/
bool Miller(ll p,int iteration)
{
if (p < 2)
{
return false;
}
if (p != 2 && p % 2==0)
{
return false;
}
ll s = p - 1;
while (s % 2 == 0)
{
s /= 2;
}
for (int i = 0; i < iteration; i++)
{
ll a = rand() % (p - 1) + 1, temp = s;
ll mod = modulo(a, temp, p);
while (temp != p - 1 && mod != 1 && mod != p - 1)
{
mod = mulmod(mod, mod, p);
temp *= 2;
}
if (mod != p - 1 && temp % 2 == 0)
{
return false;
}
}
return true;
}
//Main
int main()
{
int w=0;
int iteration = 5;
mpz_t num;
cout<<"Enter integer to loop: ";
cin>>num;
if (num % 2 == 0)
num=num+1;
while (w==0) {
if (Miller(num, iteration)) {
cout<<num<<" is prime"<<endl;
w=1;
}
else
num=num+2;
}
system ("PAUSE");
return 0;
}
(如果我将 num 定义为 'long long' 程序工作得很好,但我不知道我应该如何调整整个事情以“匹配” num 被定义为 'mpz_t',我也没有提到它但是该程序基本上取一个初始整数值,如果整数是复合的,则通过添加 2 来循环它,直到它变成一个素数)
解决方案
推荐阅读
- xml - 将 Google Analytics 集成到 VAST Preroll XML
- php - PHP __DIR__ 在本地工作但不在生产环境中
- postgresql - 使用 pg:push 到 Heroku PostgreSQL 数据库时出错
- ios - API 未在 Swift for iOS 中显示数据
- css - 如何在没有任何样式问题的情况下链接到另一个页面中的位置?
- python - 告诉 Flask 仅将上传内容存储在内存中,而不使用临时文件
- wordpress - 想在 wordpress 上显示我的世界玩家统计数据吗?
- python - 无法在用户函数上使用 np.where() 在熊猫数据框中创建新列
- go - 具有通用功能但功能参数不同的 API 的通用接口
- shell - 如何使用 GitHub API 在 GitHub 组织中检索 1000 多个存储库的列表