円分擬素数

{東京都立大学大学院 \atop 松井鉄史} 2000-04-27

1 強擬素数

1.1 定義

最初に記号を整理する。 n: 奇数、 (a, n) = 1 とする。 n = 2^{k}n^{∗} + 1 ただし n^{∗} は奇数。

条件 (S). n が

{a^{n^{∗}} − 1} ∪ {a^{2^{i}n^{∗}} + 1 | i = 0, ⋯, k}

のどれか一つだけを割り切る。定義 1. 合成数 n がある a に対して条件 (S) を満たすとき、 n は

基 a の強擬素数

という。注意. 1 ≤ a < n なる a に対して n が素数ならば常に条件 (S) を満たす。 n が合成数ならば条件 (S) を満たさない a が存在する。

1.2 基の個数 (Monier 1980)

合成数 n について 1 ≤ a < n なる a の内、強擬素数の基になる個数は

B_{S} = (1 + \frac{2^{ω(n)ν(n)} − 1}{2^{ω(n)} − 1}) ∏_{p|n} gcd(n^{∗}, p^{∗})

で与えられる。ただし、 ω(n) : n の素因数の個数 ν(n) = min_{p|n}{v_{2}(p − 1)}

注意. n − 1 に対する割合でいうと、最大 1/4 である。

1.3 Rabin-Miller 判定法

奇数 n に対し以下を k 回繰り返す:

1 < a < n − 1 なる a を無作為に選ぶ

もしn が a に対し条件 (S) を満たさないならば:

n は合成数 n は「素数」

ただし、「素数」が返された時、 4^{−k} の確率で合成数かも知れない。

2 改良 (?)

条件 (S) は、

a^{n−1} − 1 = (a^{n^{∗}} − 1) ∏_{i=0}^{k}(a^{2^{i}n^{∗}} + 1)

という因数分解に対応している。では、

a^{n−1} − 1 = ∏_{d|n−1} Φ_{d}(a)

という円分多項式への分解には何が対応するか？

3 円分擬素数

条件 (C). n が

{Φ_{d}(a) | d | n − 1}

のどれか一つだけを割り切る。定義 2. 合成数 n がある a に対して条件 (C) を満たすとき n は

基 a の円分擬素数

という。命題 1. 奇数 n について次は同値：

1. a に対し条件 (C) を満たす。

2. n = ∏_{i=1}^{ω(n)} p_{i}^{e_{i}} とすると、 a の p_{i}^{e^{i}} を法とする位数は相等しい。

各 p_{i}^{e^{i}} を法とする位数 m の元は φ(m) 個ずつある。従って次が成り立つ。命題 2. 奇数 n = ∏_{i=1}^{ω(n)} p_{i}^{e_{i}} とする。 n が条件 (C) を満たす基 a (1 ≤ a < n) の個数は、

G = gcd(n − 1, p_{1} − 1, ⋯, p_{ω(n)} − 1)

とすると、

B_{C} = ∑_{d|G} φ(d)^{ω(n)}

= ∏_{p|G} (1 + (p − 1)^{ω(n)} \frac{p^{ω(n)v_{p}(G)} − 1}{p^{ω(n)} − 1})

で与えられる。命題 3. 15 以上の奇合成数 n に対し、条件 (C) を満たす基 (1 ≤ a < n) の割合は高々 1/6 である。

10

例１

23*89=2047 (最小の基 2 の強擬素数であり、円分擬素数でもある）

B_{F} (2047) = gcd(2046, 22) gcd(2046, 88)
= 484
B_{E}(2047) = 2 gcd(1023, 22) gcd(1023, 88)
= 242
B_{S}(2047) = (1 + 1) gcd(1023, 11) gcd(1023, 11)
= 242
B_{C}(2047) = (1 + 1)(1 + 10^{2})
= 202

例２

7*13*19=1729 (Carmichael 数)

B_{F} (1729) = gcd(1728, 6) gcd(1728, 12) gcd(1728, 18)
= 1296
B_{E}(1729) = 1/2 gcd(864, 6) gcd(864, 12) gcd(864, 18)
= 648
B_{S}(1729) = (1 + 1) gcd(27, 3) gcd(27, 3) gcd(27, 9)
= 162
B_{C}(1729) = (1 + 1)(1 + 2^{3})
= 18

例３

47*139=6533 (1/6 に近付く系列 (2p+1)(6p+1))

B_{F} (6533) = gcd(6532, 46) gcd(6532, 138)
= 2116
B_{E}(6533) = \frac{1}{2} gcd(3266, 46) gcd(3266, 138)
= 1058
B_{S}(6533) = (1 + 1) gcd(1633, 23) gcd(1633, 69)
= 1058
B_{C}(6553) = (1 + 1)(1 + 22^{2})
= 970

3.1 計算方法

n が条件 (C) を満たすかどうかを確かめるには n を素数だと思って位数を求めればいい。位数が求まれば条件 (C) が満たされており、計算が途中で破綻すれば条件 (C) を満たさず、 n が合成数であることが判る。

4 結論

位数を求める算法は n-1 の因数分解を必要とする。 Rabin-Miller 判定法における条件 (S) を条件 (C) に置き換えると、１回ごとの誤り確率は 1/4 から 1/6 に減るが、因数分解という重い処理が必要になって実用的でない。

たとえ n-1 の部分的な因数分解が判っているとしても、強擬素数判定以上の情報をそこから得ようとしても概ね無駄な努力である。