擬素数

擬素数 (pseudoprime) について。

※ MathJax を使用しています。数式を表示するためには、JavaScript をオンにする必要があります。

擬素数

擬素数 (pseudoprime) とは, 広い意味では, すべての (奇) 素数に対して成り立つ性質を満たす合成数の総称である.

擬素数

$n$ を合成数, $a$ を整数とする. $n$ が底 $a$ に関する擬素数 (あるいは, Fermat 擬素数) であるとは, 合同式 $$ a^{n-1}\equiv 1\pmod{n} $$ が成り立つときにいう.

底 $2$ に関する擬素数は Poulet 数と呼ばれる.

単に擬素数という場合, 狭い意味では, 底 $a$ に関する擬素数を指すことが多い.

Euler 擬素数

$n$ を奇数の合成数, $a$ を整数とし, $\gcd(a, n)=1$ であるとする. $n$ が底 $a$ に関する Euler 擬素数であるとは, 合同式 $$ \left(\frac{a}{n}\right) \equiv a^{(n-1)/2} \pmod{n} $$ が成り立つときにいう. ただし, 左辺は Jacobi 記号である.

底 $a$ に関する Euler 擬素数はすべて底 $a$ に関する擬素数である.

強擬素数

$n$ を奇数の合成数とし, $n-1=2^{s}t$ ($s\geq 1$ は整数, $t\geq 1$ は奇数) とする. また, $a$ を整数とし, $\gcd(a, n)=1$ であるとする. $n$ が底 $a$ に関する強擬素数であるとは, $$ a^{t}\equiv 1\pmod{n} $$ が成り立つか, または, ある整数 $r$ が存在して, $0\leq r<s$ であり, $$ a^{2^{r}t}\equiv -1\pmod{n} $$ が成り立つときにいう.

底 $a$ に関する強擬素数はすべて底 $a$ に関する Euler 擬素数であることが知られている.

Carmichael 数

$n$ を合成数とする. $n$ が Carmichael 数であるとは, 任意の整数 $a$ に対して, $\gcd(a, n)=1$ ならば, 合同式 $$ a^{n-1}\equiv 1\pmod{n} $$ が成り立つ (すなわち, $n$ が底 $a$ に関する擬素数である) ときにいう.

最小の Carmichael 数は $561=3\times 11\times 17$ である. Carmichael 数は無限に多く存在することが知られている (Alford, Granville, and Pomerance, 1994).

概素数

概素数 (probable prime) とは, 広い意味では, すべての (奇) 素数に対して成り立つ性質を満たす整数の総称である. 端的にいえば, (概素数) $=$ ((奇)素数) $\cup$ (擬素数). ある概素数が, もし合成数だと判定されたら, その数は擬素数である.

具体的には, 今までの「○○擬素数」の定義において, 合成数という条件を外したものが「○○概素数」である. 例えば, 底 $a$ に関する擬素数の定義において「$n$ が合成数である」という条件を「$n$ が正の整数である」という条件に置き換えたものを, 底 $a$ に関する概素数という.

参考文献

  • Ribenboim (著), 吾郷孝視 (訳): 素数の世界 その探索と発見, 共立出版, 1995.
  • Crandall (著), Pomerance (著), 和田秀男 (監訳): 素数全書 計算からのアプローチ, 朝倉書店, 2010.

関連記事

素数に関する用語集
Lucas擬素数

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示