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.