c - Pollard Rho 分解方法在 C 中的实现

Question

谁能帮我解决 pollard rho 的实现问题？我已经在 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 ，如果模数较大，可能会发生溢出。模数仅稍大时很少见，但这只会使它不那么明显，如果模数允许溢出的可能性，则不能指望幸运。

如果您选择残基类模 m 的代表，您可以获得两倍的更大范围。绝对值最多m/2或类似的东西:

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

所以这将允许高达 2^33 的模数使用 64 位无符号类型。不是很大的一步。

该问题的推荐解决方案是使用大整数库，例如 GMP 在大多数 Linux 发行版(如果不是全部)上都可以作为分发包使用，并且(相对)也可以轻松地在 Windows 上安装。

如果这不是一个选项(真的，你确定吗？)，你可以使用俄罗斯农民乘法让它为更大的模数工作(对于无符号 64 位整数类型高达 2^63):

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

所以为了计算，你只需要 2*(m-1)不会溢出。

uint64_t mod_mult(uint64_t x, uint64_t y, uint64_t m)
{
    if (y == 0) return 0;
    if (y == 1) return x % m;
    uint64_t temp = mod_mult(x,y/2,m);
    temp = (2*temp) % m;
    if (y % 2 == 1) {
        temp = (temp + x) % m;
    }
    return temp;
}

但是请注意，此算法需要 O(log y) 步，因此在实践中速度相当慢。对于较小的 m你可以加快速度，如果 2^k*(m-1)不溢出，可以按k的步骤进行位而不是单个位 ( x*y = ((x * (y >> k)) << k) + (x * (y & ((1 << k)-1))) )，如果您的模数永远不会大于 48 或 56 位，这是一个很好的改进。

使用模乘法的这种变体，您的算法将适用于更大的数字(但速度会明显变慢)。如果 m < 2^32，您还可以尝试测试模数的大小和/或因素以确定使用哪种方法。或 x < (2^64-1)/y , 简单 (x * y) % m会做的。