リュカ–レーマー・テスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/02 03:03 UTC 版)
「メルセンヌ数」の記事における「リュカ–レーマー・テスト」の解説
p が奇素数のとき、S0 = 4, Sn = Sn−12 − 2 (n ≥ 1) で{Sn} を定義すると、 M p ∤ S k ( 0 ≦ k ≦ p − 2 ) {\displaystyle M_{p}\not \mid S_{k}\ (0\leqq k\leqq p-2)} ならば、Mp は合成数である M p ∣ S p − 2 {\displaystyle M_{p}\mid S_{p-2}} ならば、Mp は素数である 証明については「リュカ–レーマー・テストの証明」を参照 リュカ–レーマー・テストは二進計算機用のアルゴリズムに向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2p ≡ 1 (mod Mp) より、A·2p + B ≡ A + B (mod Mp) が成り立つので、Mp で割る割り算の代わりに、二進法で p 桁のシフト演算と足し算だけで計算できる。
※この「リュカ–レーマー・テスト」の解説は、「メルセンヌ数」の解説の一部です。
「リュカ–レーマー・テスト」を含む「メルセンヌ数」の記事については、「メルセンヌ数」の概要を参照ください。
ウィキペディア小見出し辞書の「リュカ–レーマー・テスト」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- リュカ–レーマー・テストのページへのリンク
