| 网站首页 | 业界新闻 | 群组 | 人才 | 技术文章 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 95 人关注过本帖
标题:一个分解整数的算法
只看楼主 收藏
songls
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2006-4-30
  问题点数:0  回复次数:1   
一个分解整数的算法
一个分解整数的算法

   在介绍算法前,先介绍一下原理。
  ①、设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来求平方,速度会受影响,是否还有其它更好的办法来提高速度,或者更好的建议,希望大家多多提出,本人不胜感激。
2018-01-03 21:32
songls
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2006-4-30
  得分:0 
三、对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原先的判断,而且增加了一段范围的判断。
2018-01-06 16:59







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.080249 second(s), 9 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved