長男の熱が下がらず、仕事を休んで家で看病をしています。ちょっと眠ったので、素因数分解をするプログラムを作成してみました。授業でRSAを取り扱おうと思っているからです。C言語で作成したかったのですが、多倍長整数についての取り扱いが面倒だったので、Javaで作成してみました。
「擬似乱数周期を使った素因数分解」については、結城浩さんより教えていただきました。
import java.math.*; import java.util.*; public class Prime { static void factor_two(BigInteger n){ BigInteger one = rho(n); BigInteger another = n.divide(one); System.out.println(n + " = " + one + " * " + another); } /* 「擬似乱数周期を使った素因数分解」 あるいは「Pollardのρヒューリスティック」と呼ばれる方法 */ static BigInteger rho(BigInteger n){ BigInteger i = new BigInteger("1"); BigInteger x = new BigInteger(n.bitLength(),new Random()); BigInteger y = x; BigInteger k = new BigInteger("2"); BigInteger f; while (true){ i = i.add(BigInteger.ONE); x = ((x.pow(2)).subtract(BigInteger.ONE)).mod(n); f = (y.subtract(x)).gcd(n); if (f.compareTo(BigInteger.ONE) != 0 && f.compareTo(n) != 0){ return f; } else if (i.compareTo(k) == 0){ y = x; k = k.pow(2); } } } public static void main(String[] args){ long start,end,time; // 36桁 BigInteger n = new BigInteger("134502404035572884331085302462570091"); start = System.currentTimeMillis(); factor_two(n); end = System.currentTimeMillis(); time = end - start; System.out.println("Time : " + time + "[ms]"); // 46桁 /*n = new BigInteger("5589808186334383050291570992756471405633041387"); start = System.currentTimeMillis(); factor_two(n); end = System.currentTimeMillis(); time = end - start; System.out.println("Time : " + time + "[ms]");*/ } }
実行結果は、以下です。
134502404035572884331085302462570091 = 695361131 * 193428131138340667952988161 Time : 6249[ms]