Maximaは素因数分解を実行する関数が用意されています。使ってみましょう。
/* 4.3.1m */ factor(54444439);
使用した機能
マニュアルによると、factorはデフォルトでは、Berlekampのアルゴリズムというものを使うそうです。
組み込み関数を使う代わりに、Pollardのロー(ρ)素因数分解アルゴリズムを実装してみます。
Pollardのアルゴリズムは、擬似乱数で素因数を探す乱択アルゴリズムです。Floydの循環検出法を使い、検出条件と素因数を同じ計算(最大公約数)で済ませるところがミソのアルゴリズムです。
Floydの循環検出法は、数列上をウサギとカメに進ませて、カメがウサギに周回遅れで追いつかれたら循環検出というものです。擬似乱数の軌跡がρに見えるから、ローアルゴリズムと呼ばれているのでしょうか？
では、実装してみましょう。
を素因数分解してみます。
/* 4.3.4m */ /* n: objective to be factered, g: generator for pseudo-random fuction */ /* pseudo-random function := g mod n */ pollard_rho(n, gen) := block([x : 3, w : 3, g : 1], local(prf), prf(x) := mod(gen(x), n), while g = 1 do ( x : prf(x), w : prf(prf(w)), g : gcd(n, w - x) ), if g # n then g else false /* g = n means the end of randomness */ )$ n : 11111111111111111$ f(x) := x^2 + 1$ g : pollard_rho(n, f)$ print(n, "=", g, " ", n / g)$
使用した機能
擬似乱数には、
乱択アルゴリズムなので、擬似乱数によっては素因数発見に失敗することがあることに注意してください。
組み込み関数を使う代わりに、Pollardのp-1素因数分解アルゴリズムを実装して、103番目のMersenne数が合成数であることを調べてみましょう。
/* 4.3.8m */ pollard_pminus1(n, B) := ([logc : log(sqrt(n)), x : 3], for p : 2 next next_prime(p) while p < B do block([d], d : ceiling(logc/log(p)), x : power_mod(x, p^d, n)), g : gcd(x - 1, n), if g = 1 or g = n then return(false), g )$ n : 2^103 -1$ g : pollard_pminus1(n, 600)$ if g # false then print(n, "=", g, " ", n/g) else print("failed.")$
