Java中素数分解的Pollard Rho算法

它是对给定整数执行因式分解的算法。以下是实现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