素因数分解の方法の一つ。根本的な原理は、ランダムに選ばれた２つの整数a, b(＜N)で GCD(a - b, N)≠1, N となればいいなぁ、ってことで、それ故に「モンテカルロ法」の別名もあるわけです。その「ランダムに選ぶ」方法をアルゴリズムとして定義しましょう。…

N 因数分解する数 p,q 素数 GCD(a,b) aとbの最大公約数。GCD(30,45)=15。