대수에 대한 C 코드와 Pollard의 rho 알고리즘에 대한 질문

Question

이 코드는 대수 (wiki의)에 대한 pollard의 rho 알고리즘에서 C로 작성되었습니다. 이 코드에서 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입니다. 참고로 Wikipedia 기사의 세 줄을 다음과 같습니다.

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;