Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

素因数分解

長男の熱が下がらず、仕事を休んで家で看病をしています。ちょっと眠ったので、素因数分解をするプログラムを作成してみました。授業で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]