剰余位数の分布の一性質について
共同研究６65

整数論と暗号理論に関する共同研究

剰余位数の分布の一性質について
村田 玲音
石井坦

１．問題とその背景
a を一般に自然数とし，p を奇素数とする。p を法とする既約剰余類群は p −１次の巡回群になるが，その中で a (mod p) の類を考えると，p が a を割らなければ，次の二つの数を定義することができる：

ただし，は p を法とする既約剰余類群，＜ a (mod p) ＞は，この群の中で a (mod p) の類が生成する部分群，［ ： ］は部分群の指数，そして集合の前に＃をつけると，その集合の元の個数をあらわすものとする。
これから先，Ia (p) のことを剰余指数，Da (p) のことを剰余次数と呼ぶことにする。この両者の間には，⑴

Ia (p)・Da (p) = p−1という関係が成り立っている。

こうした数に最初に注目したのは C.F.Gauss で，今から200年くらい前のことである。彼は aを固定し p を動かして，この二つの数を当時としてはかなり先まで計算した。そして，剰余次数の方はかなり激しく変動すること，剰余指数の方にはかなり頻繁に１が出現すること，等を観察した。さらに剰余指数の方を詳しく考察して，「a ＝10 のとき，剰余指数が１になるような素数 p は無限にあるだろう」という予想を立てたと言われている。これは現在我々が『原始根に関する Artin 予想』とよんでいる予想の特殊な場合にあたる。ちなみに a ＝５ととって，100以上200以下の21個の素数に対して，剰余指数・剰余位数の値を列挙してみよう。Gauss の観察した現象が多少お分かりいただけるであろう。

p101103107109113

127131137139149151157

Ia (p)

411413212421Da (p)25102106271124265136693775156

研 究 所 年 報66p163167173179181191193197199…

Ia (p)

31121210116…

Da (p)

54166172891519192

19633…

なお，a＝10のとき Ia (p) =１が成立することは，「 1/p を10進法で無限小数展開したときの循環節の長さがちょうど p −１になる」ことと同値である。Gauss はこの方面から「 Ia (p) =１」という条件に注目したらしい。
この Gauss の研究はある意味で，以後の剰余指数・剰余次数の研究の方向を大きく決めることになった。つまり，彼以後の研究はほとんど剰余指数の方に向けられたのである。しかしこれは非常に賢明な選択であったと思われる。後でもう少し詳しく述べるように，剰余位数の方の分布状態は，これがかなり激しく変動するため大変調べにくく，当時これに関して意味のある方向を見出すことは至難だったと思われるからである。
Gauss 自身はこの Gauss の予想に関して何一つ結果を得ることができなかった。他の数論的な問題や手段との関連が見つからず，全く手掛かりがつかめなかったのだろうと思う。ところが1927年に E.Artin, H.Heilbronn の両氏が，全く別の方向からこの予想を再発見し，以後この予想は『原始根に関する Artin 予想』と呼ばれることになった（［１］）
。a が条件 Ia (p) =１を満たすとき，「a は p を法とする原始根である」という言い方をするからである。
「a が p を法とする原始根である」ということは，a の類からべき乗だけで p を法とする既約剰余類群全体が作られていることを意味し，ここに原始根の重要性がある。
『原始根に関する Artin 予想』に関しては，まず Heilbronn が確率を用いて予想の本質がどこにあるかを明らかにし，一変数代数関数体の場合のアナロジーが1938年に Birharz によって解決され（［２］），そして1967年には，イギリスの解析数論学者 C.Hooley が次の定理を証明して，予想に一つの区切りをつけた（［４］）：
定理１（C.Hooley, 1967）一般リーマン予想を仮定する。このとき，x を正数として，とおけば，次の漸近式が成り立つ。ただし Ca とは a だけから計算可能な絶対定数である。
⑵
ただし，π（x）は x 以下の素数の個数を表わす。
Ca は多くの a に対して一定値 C ＝0.37395…になることが知られている（この C をこの問題にちなんで，Artin の定数と呼んでいる）。
これは一般リーマン予想という未解決の結果を仮定した下での結果なので，勿論予想の解決に剰余位数の分布の一性質について67はなっていないが，次の二点により，Artin 予想にとって非常に重要な結果だと高い評価を得ている。
i)

比較的孤立した問題だった『Artin 予想』を，一般リーマン予想など解析数論の中心的な方法と結びつけ，問題の意味や広がりを明確にした。
この結果は Gauss が予想した「無限個ある」より更に強く，「素数全体の C 倍程度たくさii)

んある」ことを示している（つまり定量的な結果である）。
Hooley は解析的整数論と呼ばれる分野の研究者で，リーマン予想，素イデアルの分解，誤差項の評価，といった解析数論で多用される手段を幾つか組み合わせて上の結果を証明したが，学問としての解析数論は Gauss の弟子の Dirichlet が19世紀前半に創始したもので，やはり Gaussの時代にはあの予想を解く手段は揃っていなかったと見るべきであろう。
この Hooley の結果が突破口になって，これ以後色々な人によって幾つかの重要な結果が得られた。以後の話に重要なのは次の結果である：
定理２ （Lenstra Jr.（［６］），L. Murata（［７］）一般に n を自然数とする。一般リーマン予想を仮定する。定理１の Na (x) を一般化してNa (x ; n)={p ≦ x ; I a (p) =n}とおけば，⑵と同様の漸近式が得られる。ここでも定数 Ca, n は，a と n だけから計算可能な絶対定数である。
定理２によれば定数 Ca, n は必ず Artin の定数 C の有理数倍になり，しかもほとんどの場合Ca, n ＞ 0 になることが分かっている。つまり Ia (p) = n を満たす素数も無限個存在するのである。
ここで素数全体の集合を P ，自然数全体の集合を N と書くことにしよう。上で定義した剰余指数・剰余次数は共に，集合 P から N への写像と見ることができる。さて，この定理２は，例
外的な場合を除いて，写像としての剰余指数は P から N への全射になっていることを主張している。
そして，写像としての剰余位数に関しても次の結果が知られている（［５］など）：
定理３ （Ihara, 1992）有限個の例外を除いて，写像 Da は P から N への全射である。
この定理３は unconditional な結果である。

68

研 究 所 年 報

「P から N への全射である」という点で二つの写像 Ia ，Da は共通しているが，詳しく見てみると両者の全射には大きな違いのあることが分かる。剰余指数の場合，自然数 n の原像を見てみると，定理２がこれに関して定量的な結果を与えている。そして上でも述べたように，通常これは無限集合になる：
ところが剰余位数の場合，同じように n の原像を見ると，Da-1 (n) は常に有限集合になってしまうのである。実際，Da (p) = n が成り立つなら
n+1

p< anが成立する（左の不等式は n ≦ p −1から得られ，右の不等式は p|an −１から得られる）。つまり，剰余指数の方は様々な値をランダムにとりながら最終的には N を分厚く覆ってゆくのに対し，剰余位数の方は自然数を小さい方から薄く覆いながら結果的には N 全体を覆ってゆくのである。剰
余位数の変動が激しいことも勿論だが，この「薄く覆う」ことが剰余位数の研究を難しくした一番大きな原因であると思う。
そこで我々は剰余位数の値分布に関して定量的な結果を得るための試みとしてまず自然数 t を別にとり，剰余位数の値の分布を�mod� t で分類することを考えた。つまり法 t の任意の剰余類s（mod t）に対して，集合を考え，この集合の自然密度を考察するのである。
この問題は大まかに言って，t が複雑な数になるほど難しさが増してしまう。t ＝２の場合が一番易しく，t ＝奇素数，t ＝素数のベキ，と難度が上がって，一番難しいのは勿論，t ＝一般の自然数の場合である。現時点で我々が結果を得ることができているのは，だいたい t が素数のベキの場合までである。
本稿では中間結果の報告という性質上，途中のプロセスや証明は一切省略し，かつ t ＝４と限定して，得られた結果とコンピュータによる数値実験の結果を提示し，我々の結果を紹介したい。
なお，以下の結果は知念宏司氏（大阪工業大学）との共同研究である。
剰余位数とは「素数 p を法とする既約剰余類で a(mod p) の類をべき乗していったときの周期の長さ」に他ならない。この剰余位数も剰余指数同様，重要な数である。例えば，周知のように近年急速に発展した「公開鍵暗号」は整数論の中に見られる循環現象を利用して作られており，中でも一番広く使われている「ＲＳＡ暗号」では「剰余類をべき乗した時に生じる循環現象」を用いている。ＲＳＡ暗号の場合，剰余類の法は素数 p ではなくて二つの異なる素数の積を使うのだが，おそらく我々の結果に見られたような「剰余類による偏り現象」はそこでも見られることと思う。

剰余位数の分布の一性質について

69

２．結果の紹介
歴史的に見ると，この問題を考えたのは我々が最初ではない。1960年頃，Sierpinski が，我々の記号で #Qa (x ; 0 (mod q) ) を考え，1966年に H.Hasse がこの集合の Dirichlet 密度を計算している（［３］）
。この結果は1981年に W.Odoni によって改良され（［９］），この時点で自然密度が求まっている。しかし，彼等が考えたのは s ＝０の場合だけであった。後で挙げる我々の結果を見ても分かるとおり，s ＝０というのは例外的に簡単な場合なのである。つまり，我々の場合，「任意の剰余類 s (mod t) を考えた」ところが重要な点である。
我々の結果は次の通りである。
まず初めにとる自然数 a に，次のような仮定をおくことにする。これは以後の計算が不必要に複雑になるのを避けるためのもので，本質的な仮定ではない。
a は完全 h 乗数ではないとする（h ２）。さらに a = a1・a22, a1 : square-free と分解しておく。
a が偶数のときには a1も偶数になるが，その場合 a1 = 2・a1́と更に分解しておく。また次のような特殊な数を定義する：

定理４（［８］） Ｉ） s ＝０，１，２，３に対して，漸近式が成り立つ。ただし s ＝０，２のときは unconditional ，s ＝１，３のときは一般リーマン予想を仮定する。
II） 自然密度 d s の値は次で与えられる：

d0d1d2d3① a1≡1, 3 (mod 4) のとき，1/31/61/3

1② a1≡2 (mod 4) で，さらに② - ⒤ a1 = 2 のとき，
( i.e. a 1́ =1のとき )② - (ii)

a1́

/125748C
8724/6748

C
8≡1 (mod 4) かつ a1́≠1 ，さらに② - (ii) - a)a1́が mod 4で１に合同な素因子をもつ場合

/3

1/6

1/31/61

研 究 所 年 報

70② - (ii) - b)a1́が mod 4で３に合同な素因子だけで構成されている場合

a② - (iii)a1́

≡3 (mod 4) ， さ ら に② - (iii) - a)a1́が mod 4で１に合同な素因子をもつ場合/31② - (iii) - b)a1́/61/31/61が mod 4で３に合同な素因子だけで構成されている場合

pC
appp以下，この結果について解説したい。
a が偶数の時は，Da (p) の値を分類する t ＝４と a とが共通因子２をもつため，分布に偏りが生じていると考えられるので，剰余位数の分布として正常なのは①の場合であろう。このとき，我々の結果の示すところによれば，x 以下の素数 π(x) は次のような綺麗な分かれ方をするのである。

modmodmodmod
しかも，s に対する式はどれも同じように見えるのに，s ＝０，２の場合には一般リーマン予想を使わずに解くことができ，s ＝１，３の場合には一般リーマン予想を使わないと解くことができない。
a が偶数の場合には上に見られるように，随分複雑な偏り方をする。この中で② - (ii) - b) と② - (iii) - b) に現われる条件，「a′1 が４を法として１に合同な素因子をもつかどうかで密度が大きく変化する」点が珍しい点である。こうした条件で密度が左右される例を私は他には知らない。
なお，計算してみればすぐに分かることだが，d 1と d 3 が異なっている場合には，必ずd 1 ＜d 3となることが証明できる。これもちょっと不思議な現象である。
上に挙げた定理は理論的な結果であるが，これが実際とどの程度まで合致するものなのか，比較のため計算機による数値例を挙げておく。
ここでは x ＝10 7という値を用いた。これ以下の素数の個数は664579個である（つまりπ(10 7)

剰余位数の分布の一性質について71＝664579）。一つの a に対してこの程度まで実際に #Qa (x ; s (mod 4)) を計算するのに，現在のパソコンではだいたい一晩かかってしまう。特に a が大きくなってくると，x の値をもう少し大きく取りたいのだが，そうすると計算時間が飛躍的に長くなってしまう。ただ経験的には，a が二桁くらいの数なら，10 7まで計算してみると実際の密度はだいたい小数点以下３桁くらいまでは理論値と一致するようである。
下の表は s ＝２の場合を省いてある (d 2 = 1− (d 0+ d 1+d 3 ) による ) 。また，a の値はなるべく定理４の各場合から例をとるようにした。なお，d s の実測値とは π (107 ) -1・#Qa (107 ; s (mod 4)) のことである。
d 0, d 1, d 3の実測値

aの値

d 0, d 1, d 3の理論値

d0d1

d3

50.333320

0.166771

0.166810

55=5・110.333175

0.166875

0.166691

20.416687

0.065425

0.226407

10=2・50.3333460.166644

0.166522

d0d1

d3/3
1/3

1/61/61

1/6
1/6

70.41667 48

C
7 + C
48
880.22629
0.06538/3

1512/6

1/3

42=2・3・7

0.333566

0.1651290.168277

16=2・30.333331

0.132179

0.201471

130=2・3・5

0.333255

0.166345

0.166991

1/3/3

161
6C . 38 143
0.16498
3C56
0.13219/61/6

1

1 + C . 3
8 143
60.16835
31+C5660.20115/6

1

最後に，s ＝１，３の場合だけに一般リーマン予想が必要になる理由について，簡単に述べておきたい。
我々は Da (p) の値を mod４で分類して考察したのだが，４を法とする剰余類群を加法群と見た場合，次のような部分群の列があり，しかも部分群はこれで全部である：
一番小さい部分群を使って #Qa (x ; 0 (mod 4)) に関する結果が仮定なしに得られ，真中の部分群を使って #Qa (x ; 0 (mod 2)) に関する結果がやはり仮定なしで得られる。この両者を引き算すると#Qa (x ; 2 (mod 4)) が得られるのである。従ってここまでは unconditional である。ところが部分群はこれだけしかないので，s ＝１，３を分離することができず，無理に分離するためには一般リーマン予想が必要になるということであろう。つまり，一般リーマン予想が必要になるかどうかは，mod t の加法的剰余類群の群構造が深く関わっているらしい。
同じような結果を出すために，一方には仮定が要らず，一方には一般リーマン予想が必要にな研 究 所 年 報72

るのは確かにちょっと不自然ではあるが，現時点で私はこれを外すことは不可能だと思っている。
我々は Da (p) を調べるために式⑴を使うという方法をとった。この式の右辺は素数の分布なので古くから色々なことが調べられている。そして左辺の Ia (p) に関しては『原始根に関する Artin予想』の研究で，Hooley 以来今日までにかなりなことが分かってきた。だからこの二つを組み合わせて Da (p) に関する情報を得よう，というのが方針であった。ただ，Ia (p) に関して詳しいことが分かるのは全て一般リーマン予想の仮定の下での話である。従って今の方針を採る限り，リーマン予想を外すことは無理であろう。

参考文献[1] Artin E. : “ The Collected Papers of Emil Artin”, Addison-Wesley (1965) p.viii.
[2] Bilharz H. : Primdivisoren mit vorgegebner Primitivwurzel, Math. Ann. Bd.114 (1937) pp. 476 - 492.
[3] Hasse H. : Über die Dichte der Primzahlen p, für die eine vorgegebene ganzrationale Zahl a0 von geraderbzw. ungerader Ordnung mod p ist, Math. Ann. Bd.166 (1966) pp. 19 - 23.
[4] Hooley C. : On Artin’s Conjecture, J. Reine angew. Math. Bd. 225 (1967) pp. 209 - 220.
[5] Ihara Y. : On Fermat Quotient and “Differentiation of Numbers”, RIMS Kokyuroku Vol.810, “Algebraic
Analysis and Number Theory” (1992) pp. 324 - 341.
[6] Lenstra Jr. H.W. : On Artin’s conjecture and Euclid’s algorithm in global fields, Invent. Math. Vol.42 (1977)
pp. 201 - 224.
[7] Murata L. : A problem analogous to Artin’s conjecture for primitive roots and its applications, Arch. Math.
Vol.57 (1991) pp. 555 - 565.
[8] Murata L and Chinen K. : On a distribution property of the residual order of a (mod p), I and II (pre-print).
[9] Odoni R.W.K. : A conjecture of Krishnamurthy on decimal periods and some allied problems, J. Number
Theory Vol.13 (1981) pp. 303 - 319.