一个分解整数的算法

   在介绍算法前，先介绍一下原理。
  ①、设a≡b(mod n)，如果(a，n)=c>1，那么(b，n)=c>1，或者如果(b，n)=c>1，则(a，n)=c>1。
  证明: ∵a≡b(mod n)  => a-jn=b，j≥0
      又 ∵(a，n)=c>1 => a=cf，n=cg  (f,g≥1)
       ∴  代入上式得:
      cf-jcg=b => c(f-jg)=b，即(b，n)=c>1
     证毕
     反之也然，证明略。
  ②、对于一组数f1、f2、f3… fm，m≥1，如果其中有一个数fi (i≥1)与n有因子c，即(fi，n)=c≥1，则这组数的乘积:f1*f2*…fi…*fm与n也有因子c，
   这是因为f1*f2*…fi…*fm=f1*f2*…cg…*fm=c(f1*f2*…g…*fm)，这里fi=cg。
  ③、设a^2≡b(mod n)，以a为中心，向两边从1到m进行加减(m≥1)的一组平方剩余可以表示如下:
   (a-m)^2≡dm，…，(a-3)^2≡d3，(a-2)^2≡d2，…(a-1)^2≡d1，a^2≡b，(a+1)^2≡c1，(a+2)^2≡c2，(a+3)^2≡c3，…，(a+m)^2≡cm (mod n)
   这组平方剩余的左边相乘可得:
   (a-m)^2*…*(a-3)^2*(a-2)^2*(a-1)^2*a^2*(a+1)^2*(a+2)^2*(a+3)^2*…*(a+m)^2 (mod n)
   上述乘积中，对a两边的平方剩余进行两两相乘可以得到:
    (a-1)^2*(a+1)^2 (mod n)=(a^2-1)^2 (mod n)≡(b-1)^2 (mod n) =>
    (a-2)^2*(a+2)^2 (mod n)=(a^2-4)^2 (mod n)≡(b-4)^2 (mod n) =>
    (a-3)^2*(a+3)^2 (mod n)=(a^2-9)^2 (mod n)≡(b-9)^2 (mod n) =>
    .
    .
    .
   (a-m)^2*(a+m)^2 (mod n)=(a^2-m^2)^2 (mod n)≡(b-m^2)^2 (mod n)
   即上述平方剩余左边相乘，可以表达如下:
   (a-m)^2*…*(a-3)^2*(a-2)^2*(a-1)^2*a^2*(a+1)^2*(a+2)^2*(a+3)^2*…*(a+m)^2 (mod n)=
   a^2*(a^2-1)^2*(a^2-4)^2*(a^3-9)^2*…*(a^2-m^2)^2 (mod n)≡
   (a(b-1)(b-4)(b-9)…(b-m^2))^2 (mod  
   根据②可得，以a为中心向两边加减m的平方剩余中，如果a-i或者a+i(1≤i≤m)含有n的因子c，则上述平方剩余的乘法也必有n的因子c，也即:
   a(b-1)(b-4)(b-9)…(b-m^2)必有n的因子c  又根据①，上式可表示为:
    b(b-1)(b-4)(b-9)…(b-m^2)
    即该乘积中如果有n的因子，上述平方剩余也必有n的因子，共有2m+1个数。
 ④、对于平方数，可知:
      1^2=1
      2^2=1+3
      3^2=1+3+5
      .
      .
      .
      m^2=1+3+5+…+2m-1  (m≥1)
     该证明请参考其它文章。
二、算法介绍
     根据以上介绍，设计出以下的一个分解算法，供大家参考:
     算法:
     以a^2≡b (mod n)为基础   输入a，b，n，num
     1、if sqrt(b)是平方数  then return gcd(a+sqrt(b)，n)
     2、res=b  乘积结果
     3、m=1   从1开始计算平方
     4、i=1
     5、b=b-m  计算下一个减的平方
     6、res=(res*b)%n  按③中求乘积
     7、if res=0  then return gcd(b，n)   如果为0，b中必有n的因子
     8、m=m+2  按④中求平方
     9、i=i+1
     10、if i<num then goto 5
     11、return gcd(res，n)

      其中gcd为碾转相除法。

     上述算法中，a^2≡b (mod n)选择比较重要，又因算法中使用加2来求平方，速度会受影响，是否还有其它更好的办法来提高速度，或者更好的建议，希望大家多多提出，本人不胜感激。

三、对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);
}

改造后的Porllard_rho算法:
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原先的判断，而且增加了一段范围的判断。