Baillie-PSW素数判定法

Baillie-PSW素数判定法はフェルマーテスト、Solovay-Strassen素数判定法、ミラー・ラビン素数判定法などとは少し変わった素数判定アルゴリズムである。

リュカ数列

リュカ数列 $\scriptstyle{\{U_n(P,Q)\},\{V_n(P,Q)\}}$ は
整数 $\scriptstyle{P,Q(D=P^2-4Q\neq0)}$ に対して、次のように定義される。

${\displaystyle U_0(P,Q)=0 \\ U_1(P,Q)=1 \\ U_n(P,Q)=PU_{n-1}(P,Q)-QU_{n-2}(P,Q) \ {\rm for} \ n>1 \\ V_0(P,Q)=2 \\ V_1(P,Q)=P \\ V_n(P,Q)=PV_{n-1}(P,Q)-QV_{n-2}(P,Q) \ {\rm for} \ n>1 }$

この数列の一般項は、a,b(a,bは $\scriptstyle{x^2-Px+Q=0}$ の解)を用いて

${\displaystyle U_n(P,Q)=\frac{a^n-b^n}{a-b} \\ V_n(P,Q)=a^n+b^n }$

と表される。ちなみに、P=1,Q=-1のとき、つまり $\scriptstyle{\{U_n(1,-1)\}}$ がフィボナッチ数、 $\scriptstyle{\{V_n(1,-1)\}}$ がリュカ数となる。
このリュカ数列について、次の等式が成立する。
pをDと互いに素な素数とするとき、

${\displaystyle U_{p-\varepsilon}(P,Q)\equiv 0 \pmod p \\ \varepsilon = \left(\frac{D}{p}\right) \nonumber }$

( $\scriptstyle{\left(\frac{D}{p}\right)}$ は平方剰余記号)

リュカ数列の計算

地道に一項ずつ計算すると時間がかかりすぎ、
一般項の形では、a,bが無理数になって計算が大変になることがあるが、次の方法でもリュカ数列の計算ができ、バイナリ法を用いるとかなり高速である。

$\dispalystyle \left(\begin{array}{c} V_n(P,Q) \\ U_n(P,Q) \\ \end{array}\right) =\frac{1}{2^n} \left( \begin{array}{cc} P&D\\ 1&P\\ \end{array}\right)^n \left(\begin{array}{c} 2\\0\\ \end{array}\right) }$

また、 $\scriptstyle{\frac{1}{2^n}}$ の計算については、 $\scriptstyle{2^{-1}\equiv \frac{n+1}{2} \pmod m}$ (mは奇数)であることを用いるか、Baille-PSW素数判定法を用いる。

リュカ擬素数テスト(Lucas pseudoprime test)

リュカ擬素数テストでは、先の等式の対偶をとって、
奇数nに対して、

${\displaystyle U_{n-\varepsilon}(P,Q)\not \equiv 0 \pmod n \\ \left(\frac{D}{n}\right) = \varepsilon }$

( $\scriptstyle{\left(\frac{D}{n}\right)}$ はヤコビ記号)
が成立するとき、nは合成数であると判定する。また、合成数であるのに先の等式を満たすようなnをリュカ擬素数(Lucas pseudoprime)と呼ぶ。
(リュカ擬素数となる条件として $\scriptstyle{\varepsilon = -1}$ を加えることもある。)

Baillie-PSW素数判定法のアルゴリズムは次のようになる。
入力:素数判定する奇数 n
出力:合成数だとわかれば「nは合成数である」、わからなければ「nは確率的素数である」と出力する。
ステップ1
2を底としてミラー・ラビンテストを行う。
失敗すれば「nは合成数である」と出力して終了する。
ステップ2
a=5,-7,9,-11…のなかで最初に $\scriptstyle{\varepsilon = \left(\frac{a}{n}\right) = -1}$ を満たすようなaを探す。
ステップ3
D=aとなるようなP,Qでリュカ擬素数テストを行う。
失敗すれば「nは合成数である」と出力して終了する。
そうでないとき「nは確率的素数である」と出力して終了する。

最初に2を底としてミラー・ラビンテストを行うことで、もし失敗すれはnは合成数であるし、成功すれば $\scriptstyle{\frac{1}{2^{n+1}}\equiv\frac{1}{2^2} \pmod n}$ という等式が成立するので計算が楽になるのである。

ある底aに対してフェルマーテスト、Solovay-Strassen素数判定法、ミラー・ラビン素数判定法を通過してしまう合成数の集合をそれぞれ $\scriptstyle{F,S,M}$ とすると、 $\scriptstyle{F\supset S\supset M}$ という関係が成り立つため、ミラー・ラビン素数判定法に対して前者２つは優位性を持たない。(その上、多くの場合実行速度もミラー・ラビン素数判定法と大差がない.)しかし、Baillie-PSW素数判定法に対する擬素数の集合とはこのような包含関係を持たない。そのため、ミラー・ラビン素数判定法とBaillie-PSW素数判定法を併用することで、かなりの精度で素数判定をすることが可能となる。じっさい、ほとんどの擬素数はこの２つのテストのどちらかで合成数と判定できる。