Carmichael 数の確率的判定法

Carmichael 数の確率的判定法

正の整数にたいして、つぎのような判定法が考えられます。

Carmichael 数の判定
次のようなことを繰り返し行う。

$(\mathbb{Z}/n\mathbb{Z})^\times$ の元をランダムにとる。

か否かをチェックする。( $% latex2html id marker 3553 $ x^n \neq x$$ ならばもちろんはCarmichael 数ではない。)

これを例えば100回行って、いつもチェックが成功すれば、がCarmichael 数でも素数でもないのにそんなことが起こる確率は $1/2^{100}$ 以下である。

証明. 群論を用いる。

がもし Carmichael 数ではないならば、 $(\mathbb{Z}/n\mathbb{Z})^\times$ の部分集合

$\displaystyle H= \{x \in(\mathbb{Z}/n\mathbb{Z})^\times ; x^n =x\}$

は $(\mathbb{Z}/n\mathbb{Z})^\times$ の部分群であり、したがって

がもし Carmichael 数ではないならば、 $(\mathbb{Z}/n\mathbb{Z})^\times$ の部分集合

$\displaystyle H= \{x \in(\mathbb{Z}/n\mathbb{Z})^\times ; x^n =x\}$

は $(\mathbb{Z}/n\mathbb{Z})^\times$ の部分群であり、したがって

$\displaystyle \char93 (\mathbb{Z}/n\mathbb{Z}^\times)/\char93 H = \char93 ((\mathbb{Z}/n\mathbb{Z}^\times)/ H)$

は

より大きい整数である。もし、ランダムに $(\mathbb{Z}/n\mathbb{Z})^\times$ の元をとれば、それが

に入る確率は多く見積もっても

以下である。 $% latex2html id marker 3562 $ \qedsymbol$$

上のことから、与えられた数が Carmichael 数であるか否かはすばやく判定できる確率アルゴリズムがありますが、 Carmichael 数は数が少ないため、次のことは問題として残ります。

問題 2.1 与えられた数

に対して、

より大きなCarmichael 数のうち最小のものを ( $\log n$ の多項式程度の時間で)求める確率的アルゴリズムは存在するか?

<a href="https://oeis.org/A002997">オンライン整数列大辞典</a> には、Carmichael 数の最初の数十個が書いてあります。それによれば、最初のCarmichael 数は561 のようです。