这段代码是用 C 语言根据 pollard 的对数 rho 算法(来自 wiki)编写的。在此代码中,如果我输入 alpha=2、beta=5、N=1019,则必须返回 a=681、b=378、A=301、B=426 和 X=1019。但我运行它,我只得到正确的 X=1019,并且得到 (a,b,A,B)=(672,367,445,706)。你知道问题出在哪里吗?
#include<stdio.h>
#include<math.h>
int alpha, beta, N;
void xab(int *x, int *a, int *b)
{
switch(*x%3){
case 0: *x=((*x)*(*x))%N; *a=((*a)*2)%N; *b=((*b)*2)%N; break;
case 1: *x=(alpha*(*x))%N; *a=((*a)+1)%N; break;
case 2: *x=(beta*(*x))%N; *b=((*b)+1)%N; break;
}
}
int main(void)
{
int x=1; int a=0; int b=0;
int X=1; int A=0; int B=0;
int i;
scanf("%d %d %d", &alpha, &beta, &N);
for(i=1;i<N;i++){
printf("Code #%d\n", i);
xab(&x,&a,&b);
printf("x=%d a=%d b=%d\n", x, a, b);
xab(&X,&A,&B); xab(&X,&A,&B);
printf("X=%d A=%d B=%d\n\n", X, A, B);
if(x==X) break;
}
return 0;
}
最佳答案
您没有正确复制new_xab
函数。请注意,new_xab
函数同时使用 N
和 n
,其中 N=1019
和 n=1018
。作为引用,以下是维基百科文章中的三行内容
case 0: x = x*x % N; a = a*2 % n; b = b*2 % n; break;
case 1: x = x*alpha % N; a = (a+1) % n; break;
case 2: x = x*beta % N; b = (b+1) % n; break;
关于c - 关于 C 代码和 Pollard 对数 rho 算法的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23624828/