素数判定
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/09/29 09:41 UTC 版)
素数判定（そすうはんてい、英: primality test）とは、与えられた自然数が素数か合成数かを判定することである。素数判定を行うアルゴリズムを素数判定法という。
- ^ Adleman, Leonard M.; Huang, Ming-Deh (1992). Primality testing and Abelian varieties over finite field. Lecture notes in mathematics. 1512. Springer-Verlag. ISBN 3-540-55308-8
- ^ E. Allender, M. Saks, and I.E. Shparlinski, A lower bound for primality, J. Comp. Syst. Sci. 62 (2001), pp. 356–366.
素数判定
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/11 10:53 UTC 版)
カレン数の素数判定には、リュカ＝レーマー＝リーゼルの判定法（英語版） (LLR) が有効であり、PrimeGrid もこれを用いている。 また、カレン数の整除性について、以下が成り立つ。カレン素数を探索する際に、これらの事実から自明に合成数であるものを除いておくことができる。 p が 8k ± 5 の形の素数のとき、p は C(p+1)/2 を割り切る。また、p が 8k ± 1 の形の素数のとき、p は C(3p−1)/2 を割り切る。 p を奇素数とする。m(k) = (2k − k)(p − 1) − k とおくと、任意の非負整数 k に対して、p は Cm(k) を割り切る。特に、k = 0, 1 とすると、p は Cp−1 と Cp−2 を割り切る。
※この「素数判定」の解説は、「カレン数」の解説の一部です。
「素数判定」を含む「カレン数」の記事については、「カレン数」の概要を参照ください。
素数判定
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/10 02:29 UTC 版)
これらの数は q の値が 83339 までのときは素数であることが証明されている。2020年12月 (2020-12)現在[ref] q > 83339 のときは確率的素数である。 q = 42737 のときに素数であることの証明は François Morain によって、 Opteron processor上で 743 GHz-days（英語版） 間ワークステーションのいくつかのネットワーク上で動作している分散された ECCP（英語版） を実行することによって、2007 年になされた。それはその発見から2009年3月まででは ECPP による素数の証明では3番目に大きい素数であった。 今のところ知られているアルゴリズムで、ワグスタッフ数が素数であることを最も早く証明できるものは、ECPP である。 Jean Penné による LLR (Lucas-Lehmer-Riesel) ツールは、 Vrba-Reix test の手段でワグスタッフ確率的素数を見つけるために使われる。それはワグスタッフ数を法とした x 2 − 2 {\displaystyle x^{2}-2} のもとでの digraph の周期性に基づいた PRP テストである
※この「素数判定」の解説は、「ワグスタッフ素数」の解説の一部です。
「素数判定」を含む「ワグスタッフ素数」の記事については、「ワグスタッフ素数」の概要を参照ください。
- 素数判定のページへのリンク
