c - 关于 C 代码和 Pollard 对数 rho 算法的问题

Question

这段代码是用 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)。你知道问题出在哪里吗？

wiki site

#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;
}

Answer 1

您没有正确复制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;