C에서의 Pollard Rho 인수 분해 방법 구현

Question

누구나 pollard ρ 구현을 도와 줄 수 있습니까? 나는 이것을 C에서 구현했다. 그것은 10 자리까지의 숫자에 대해서는 잘 작동하지만 더 큰 숫자를 처리 할 수는 없다.

숫자 분해능을 18 자리까지 높이려면 개선을 도와주십시오. 내 코드 this입니다 : 긴 코드에 대한 유감

#include<stdio.h> 
#include<math.h> 
int gcd(int a, int b) 
{ 
    if(b==0) return a ; 
    else 
    return(gcd(b,a%b)) ; 
} 

long long int mod(long long int a , long long int b , long long int n) 
{  
    long long int x=1 , y=a ; 
    while(b>0) 
    { 
     if(b%2==1) x = ((x%n)*(y%n))%n ; 
     y = ((y%n)*(y%n))%n ; 
     b/=2 ; 
    } 
    return x%n ; 
} 

int isprimes(long long int u) 
{ 
    if(u==3) 
    return 1 ; 
    int a = 2 , i ; 
    long long int k , t = 0 , r , p ; 
    k = u-1 ; 
    while(k%2==0) 
    { k/=2 ; t++ ; } 

     while(a<=3)                /*der are no strong pseudoprimes common in base 2 and base 3*/ 
     { 
     r = mod(a,k,u) ; 
      for(i = 1 ; i<=t ; i++) 
      { 
        p = ((r%u)*(r%u))%u ; 
        if((p==1)&&(r!=1)&&(r!=(u-1))) 
        { return 0 ; } 
        r = p ; 
      } 
      if(p!=1) 
      return 0 ; 
     else 
      a++ ; 
     } 

      if(a==4) 
      return 1 ; 

} 

long long int pol(long long int u) 
{ 
    long long int x = 2 , k , i , a , y , c , s; 
    int d = 1 ; 
    k = 2 ; 
    i = 1 ; 
    y = x ; 
    a = u ; 
    if(isprimes(u)==1) 
    { 
    return 1; 
    } 
    c=-1 ; 
    s = 2 ; 
    while(1) 
    { 
    i++; 
    x=((x%u)*(x%u)-1)% u ; 

    d = gcd(abs(y-x),u) ; 

    if(d!=1&&d!=u) 
    { printf("%d ",d); 
     while(a%d==0) { a=a/d; } 

     x = 2 ; 
     k = 2 ; 
     i = 1 ; 
     y = x ; 
     if(a==1) 
     { return 0 ; } 
     if(isprimes(a)!=0) 
     { return a ; } 
     u=a ; 

    } 
    if(i==k) 
    {y = x ; k*=2 ; c = x ;}              /*floyd cycle detection*/ 
     if(c==x)                 
    { x = ++s ; } 
    } 
    return ; 

} 

int main() 
{ 
    long long int t ; 
    long long int i , n , j , k , a , b , u ; 
    while(scanf("%lld",&n)&&n!=0) 
    { u = n ; k = 0 ; 
    while(u%2==0) 
     { u/=2 ; k = 1 ; } 
     if(k==1) printf("2 ") ; 
     if(u!=1) 
     t = pol(u) ; 
     if(u!=1) 
     { 
      if(t==1) 
      { printf("%lld",u) ; } 
      else 
      if(t!=0) 
      { printf("%lld",t) ; } 
     } 
      printf("\n"); 
    } 
    return 0; 
} 

가 ..... 나는 새로운 코더입니다.

Answer 1

모듈 수 m의 두 숫자를 곱하면 중간 제품은 거의 m^2이 될 수 있습니다. 따라서 64 비트 부호없는 정수형을 사용하는 경우 처리 할 수있는 최대 모듈러스는 2^32입니다. 모듈러스가 클 경우 오버플로가 발생할 수 있습니다. 모듈러스가 약간 큰 경우는 드문 경우지만 모듈러가 오버플로 가능성을 허용하면 운이 좋을 수는 없습니다.

uint64_t mod_mul(uint64_t x, uint64_t y, uint64_t m) 
{ 
    int neg = 0; 
    // if x is too large, choose m-x and note that we need one negation for that at the end 
    if (x > m/2) { 
     x = m - x; 
     neg = !neg; 
    } 
    // if y is too large, choose m-y and note that we need one negation for that at the end 
    if (y > m/2) { 
     y = m - y; 
     neg = !neg; 
    } 
    uint64_t prod = (x * y) % m; 
    // if we had negated _one_ factor, and the product isn't 0 (mod m), negate 
    if (neg && prod) { 
     prod = m - prod; 
    } 
    return prod; 
} 

그래서 그 최대의 계수를 허용합니다 : 당신이 가장 m/2 또는 뭔가 동등한에서 절대 값의 잔류 클래스 모듈 m의 대표를 선택하는 경우

는 두 배 더 큰 범위를 얻을 수 있습니다 ~ 2^33은 64 비트 부호없는 유형입니다. 큰 걸음이 아닙니다.

큰 정수형 라이브러리를 사용하는 것이 좋습니다. 예를 들어 GMP는 대부분의 Linux 배포판에서 배포 패키지로 사용할 수 있으며 Windows에서 쉽게 설치할 수 있습니다 (예 : GMP). 그 옵션이없는 경우

(? 정말 확신하는), 당신은 더 큰 계수에 대한 작업을 얻을 수 러시아어 농민 곱셈 사용 (부호없는 64 비트 정수 유형에 대한 2^63까지) :

x * y = 2 * (x * (y/2)) + (x * (y % 2)) 

을

계산을 위해 2*(m-1)은 오버플로가 필요하지 않습니다.

그러나이 알고리즘은 O (log y) 단계가 필요하므로 실제로는 느립니다. m의 경우, 2^k*(m-1)이 오버플로하지 않으면 단일 비트 (x*y = ((x * (y >> k)) << k) + (x * (y & ((1 << k)-1)))) 대신 k 비트의 단계로 진행할 수 있습니다. 모듈 수가 48 또는 56 비트보다 크지 않은 경우 좋은 개선입니다. .

이 모듈러 곱셈을 사용하면 알고리즘이 더 큰 수에 대해 작동하지만 (상당히 느려질 것입니다). 계수의 크기 및/또는 사용하는 방법을 결정하기위한 요인을 테스트 해 볼 수도 있습니다. m < 2^32 또는 x < (2^64-1)/y 인 경우 (x * y) % m을 사용하면됩니다.