projectpn
projectpn
リュカ-レーマーテストは素数番目のメルセンヌ数(\scriptstyle{2^p-1})が素数であるかを効率的に判定する素数判定アルゴリズムである。

用いている定理

数列\scriptstyle{\{s_i\}}を次のように定義する。
s_i=\begin{cases} 4 & if \ i = 0; \\ s_i^2-2 & \rm otherwise \end{cases}
pを素数とすると、\scriptstyle{s_{p-2} \equiv 0 \pmod {M_p}}が成立するとき、\scriptstyle{M_p=2^p-1}は素数であり、かつその時に限る。

メルセンヌ数での剰余のとり方

メルセンヌ数\scriptstyle{M_p}は\scriptstyle{2^p-1}という形で表されるため、2進数で計算しているコンピューターでは剰余算が非常に簡単にできる。
割られる数をnとすると、nは\scriptstyle{n=k \times 2^p + l \ (0 \leq l < 2^p)}と表すことができる。
\scriptstyle{n \equiv k \times 2^p + l \\ \equiv k+l}より、二進数でp桁以下になるまで最上位からp+1桁目までをpビット右シフトしたものを下位p桁と足しあわせればよい。

「リュカ-レーマーテスト」をウィキ内検索
最終更新：2012年06月30日 18:18