読み書きプログラミング

日常のプログラミングで気づいたことを綴っています

(16) 素数テスト

Maximaには素数テストの組み込み関数primepがあります。これはMiller-Rabinの確率的アルゴリズムを用いたものです。


決定的アルゴリズムであるLucasの素数テストを実装して、素数性を証明しましょう。

/* 4.3.15m */
p : (10^23 - 1)/9$
factors : ifactors(p - 1)$
print(factors)$
a : 11$
isPseudo : power_mod(a, p - 1, p) = 1$
isPrime : true$
if isPseudo then
  for j : 1 thru length(factors) do
    if power_mod(a, (p-1)/factors[j][1], p) = 1 then (isPrime : false, return())$
if not isPseudo then print("p is composite.")
elseif isPrime then print("Proof complete, p is prime.")
else print("unresolved.")$

Proof complete, p is prime.

使用した機能


Lucas-Lehmerの素数テストを実装して、1279番目のMersenne数の素数性を証明しましょう。

/* 4.3.17m */
q : 1279$
p : 2 ^ q - 1$
x : 4$
for j : 1 thru q - 2 do x : mod(x ^ 2 - 2, p)$
print(p)$
if x # 0 then print("is composite.") else print("is prime.")$

is prime.