三、对pollard  rho改造
      由于pollrad  rho分解算法只对一个数进行判断是否存在n的因子，可以使用上述算法对pollrad  rho进行改造，让其在一段范围内进行查找n的因子，提高一定的效率，当然如果改造有什么问题，欢迎大家指正，谢谢！
        先看一下，原始的pollrad  rho算法：
        long  Pollard_rho(long  n,  int  c)
      {
                  long  i,  k,  x,  y,  d;
                srand(time(NULL));
                i  =  1;
              k  =  2;
            x  =  rand()  %  n;
            y  =  x;
          while  (true)  {
                  i++;
                x  =  (mod_mult(x,  x,  n)  +  c)  %  n;
                d  =  gcd(y  -  x,  n);
                if  (d  >  1  &&  d  <  n)
                          return  d;
              if  (y  ==  x)  /*该数已经出现过,直接返回即可  */
                          return  n;
              if  (i  ==  k)  {
                        y  =  x;
                        k  =  k  <<  1;
              }
      }
}

主要改造在：    d  =  gcd(y  -  x,  n);

先按上述算法写一个函数“
long  getfac(  long  a,  long  n,int  num)
{
      long  t;
      long  res,b;
      int  i,m;

      b=(a*a)%n;
      t=sqrt(b);
      if(  (t*t)==b  &&  (b*b)  !=  a  )
              return  gcd(a+b,n);
      res=b;
      m=1;
      for(  i=0  ;  i<num  ;  i++)
      {
            b=b-m;
            res=(res*b)%n;
            if(  res  ==  0  )
                  return  gcd(  b  ,  n  );
            m=m+2;
      }
      return  gcd(res,n);
}

long  Pollard_rho(long  n,  int  c,  int  num)
{
    long  i,  k,  x,  y,  d;
    srand(time(NULL));
    i  =  1;
    k  =  2;
    x  =  rand()  %  n;
    y  =  x;
    while  (true)  {
            i++;
            x  =  (mod_mult(x,  x,  n)  +  c)  %  n;
            /*d  =  gcd(y  -  x,  n);*/
            d=getfac(  y-x,n,num);
            if  (d  >  1  &&  d  <  n)
                    return  d;
            if  (y  ==  x)  /*该数已经出现过,直接返回即可  */
                    return  n;
            if  (i  ==  k)  {
                    y  =  x;
                    k  =  k  <<  1;
            }
    }
}

在Pollard_rho函数中，加入一个次数的传入值，把d  =  gcd(y  -  x,  n);修改为d=getfac(  y-x,n,num);，既不改变Pollrad  rho原先的判断，而且加大了一段范围的判断。

给你N个球，将其排成方形，长宽各多少个球？这就是RSA因式分解问题。
现在换一个思路，将其排成等腰三角形，第n行排2n-1个球，显然，可能排完第n行后，剩下的球不足排第n+1行。
这时，我们改换策略，将其排成等腰梯形，将等腰三角形前m行追加到第n+1行及后续行，以使最后一行恰好排满，不多不少。
现在我们用表达式来看看这个过程的含义：假设排出的等腰三角形有n行，剩余r个球，那么N=n^2+r(初值为1，步进为2的等差数列求和结果是n^2)，假设需要截取三角形前t行刚好将剩余r个球补成梯形，并假设梯形最后一行是第m行，那么m^2=N+t^2，即N=m^2-t^2=(m+t)(m-t)。
这种存在两种“碰运气”的方式：一种是搜索“截取三角形前t行”中的t，一种是搜索“梯形最后一行m”中的m，显然后种方式效率高。
所以，问题可以转化为：给定自然数N，求最小正整数t，使得N+t^2是平方数。
求解方式是，给定N，求出满足a^2<N的最大整数a，遍历判断(a+1)^2-N，(a+2)^2-N，...，找出第一个平方数即可。

当然，上述方法依然是亚指数级的，不足以破解现在普遍使用的RSA。可以考虑使用上述思路，这里只是选取了三角形和梯形，还有很多形状可以考虑，也不限于使用线性递增（等差数列可以看做是线性递增），也不应局限于整数内考虑，只要能找到更快速的遍历方式即可。