Pollard 的 Rho 算法用于进行整数质因子分解，java 中的实现如下

它是一种对给定整数进行因式分解的算法。以下程序实现了 Rho 算法以进行质因数分解。

程序

在线演示

public class PollardsRho {
   int num = 65;
   public int gcd(int a, int b) {
      int gcd = 0;
      for(int i = 1; i <= a || i <= b; i++) {
         if( a%i == 0 &amp;&amp; b%i == 0 ) {
            gcd = i;
         }
      }
      return gcd;
   }
   int g(int x) {
      return ((x*x)-1) % num;
   }
   public static void main(String args[]) {
      PollardsRho obj = new PollardsRho();
      int x = 2, y = 2, d = 1;
      while(d==1) {
         x = obj.g(x);
         y = obj.g(obj.g(y));
         d = obj.gcd((x - y), obj.num);
      }
      if (d == obj.num) {
         System.out.println("Cannot calculate GCD for this element");
      } else {
         System.out.println("One of the divisors of given number is "+d);
      }
   }
}

输出

One of the divisors of given number are 5

更新于： 2020 年 6 月 25 日

192 次浏览

开启您的 职业 生涯

完成课程即可获得认证

立即开始
广告