剰余位数の分布の一性質について Ⅱ共同研究７131

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

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

これは，産業経済研究所共同研究 『整数論と暗号理論に関する共同研究』の報告記事である。研究期間は二年で，一年目終了時に中間報告を書いた（研究所年報18号，文献 [10]）。本記
事では，二年目の成果およびこの二年で得られた結果の概観をしたい。
今回の研究はあくまでも解析整数論的なものであるが，現在の『公開鍵暗号』特に『RSA 暗号』とよばれるものは，整数を法とする剰余位数と深いかかわりがある。そのため，我々は『代数学と計算』シンポジウム（2001年秋，於都立大学）―――この集会では計算量の理論や暗号に関する講演が多い―――などで結果を発表してきた。ただ，今回の結果が暗号に直接応用をもつといった状況ではないように思う。

１．はじめに問題の背景については『中間報告』にかなり詳しく記したのでここでは省略する。
まず，引き続いて使う記号を再録しておきたい。
p は常に奇素数を表わすものとする。p で割れない自然数 a に対し，によって，a の剰余指数，剰余位数を定義する。我々の問題は，剰余位数 Da (p) を更に t を法とする剰余類によって分類し，その分布状態を調べようというものであった。つまり，任意の剰余類 u (mod t) をとって素数の部分集合
Qa (x ; u (mod t)) = { p _<_ x; Da (p) ∫ u (mod t)}を考え，これの自然密度を求めるのが目的である。そして，前回の『中間報告』では，t として特に４をとったとき，かなり一般的な自然数 a に対してこの密度が求まることを報告した（定理４）。
今年度に得られた主な改良点は次の３点である。
① 法 t をかなり一般的にすることができた。
②a として，一般の有理数（負も許す）まで考察できるようになった。

研 究 所 年 報132③

Qa (x ; u (mod t)) を更に細分化して考察した。
本研究は大阪工業大学の知念宏司氏との共同研究である。
これは報告記事なので，証明は載せていない。興味ある方は，準備中の本論文（[１] [２] あるいは [３]，[４]）等を参照していただきたい。また，我々の結果はかなり一般的な t に対して得られているのだが，ここでは『中間報告』との比較の意味もあるので，t ＝4の場合を中心にして結果を略述していきたい。

２．今回の結果
今後は a として有理数を考えるので，a ＝ a1/a2を a の既約分数表示とする。積 a1 a2が p で割れなければ，上と同じく，a の剰余位数や剰余指数を定義することができる。そして a は完全 h'乗数であるとする (a = a h と書ける最大の h のこと）
。我々の結果は h についても一般化してあるのだが，結論がさらに煩雑になるので，この記事ではつねに h=1としておく。
Kr,s に よ っ て， 代 数 体[K:(ζr , a1/s) を 表 わ す。ζr ＝ exp (1/2πr √-￣1 ) の 意 味 で あ る。 ま た，] によって体 K の拡大次数を表わす。

ここで新たに次の記号を導入する。これは上記の Qa (x ; u (mod t)) を更に細分したものである。
Ra (x ; l (mod m) ; u (mod t)) = { p ∈ Qa (x ; u (mod t)) ; p ≡ l (mod m)}
これについて，次の定理が成り立つ。s は任意の自然数である。
定理１ ( p≡1 (mod 4) なる素数に対する定理）(1) j ＝0 または 2 のとき，

(xx log log x
Ra (x ; 1 (mod 2s) ; j (mod 4)) = δa (1 , 2s ; j , 4) ̶ + O ̶log xlog2 x)ここで

Σ{1—— —1——s———δa (1 , 2 ; 0 , 4) = 21−s −,− ——r, r-1 :r+1, r-1 :
K
K
[]
[]
2222_＞_sr

Σ{ [ K ,δa (1 , 2s ; 2 , 4) =
__sr＞

}

1—
—
—
——

r r-1
2 2:]

1——
１１—
—
——
——
—
—
——
−—
− —
+ —
[ K2r+1, 2r-1 : ][ K2r, 2r : ][ K2r+1, 2r : ](2) j ＝1 または 3 のとき。一般リーマン予想を仮定する。
1xx
Ra (x ; 1 (mod 2s) ; j (mod 4)) = —δa (1 , 2s ; 1 , 2) ̶ + O log |a1 a2| ̶log x2(log x) 3/2(ここで)}

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

Σ{13311——s————— − ———
δa (1 , 2 ; 1 , 2) =r, r :r+1, r :K
K[][] .
2 222__sr＞}

p≡3 (mod 4) なる素数に対しても同様な結果が得られるが，それには次の記号が必要である。
法４の乗法群の Dirichlet 指標のうち，principal でない方をψとし，これを用いて次の数論的関数を定義する。μは Möbius の関数である。

Σμ(d)ψ( d )hψ (v) =v—d|v

定理２ （ p≡3 (mod 4) なる素数に対する定理̶̶詳細は文献［12］を参照）(1) Ra (x ; 3 (mod 4) ; 0 (mod 4)) = 0
Ra (x ; 3 (mod 4) ; 2 (mod 4)) = # { px ; p ≡3 (mod 4), ψ( p) =−1}

(2) j ＝1 または 3 のとき。一般リーマン予想を仮定する。
1Ra (x ; 3 (mod 4) ; j (mod 4)) = ̶ #{ p2(j-1x ; p ≡ 3 (mod 4), ψ( p) =1}

̶ 1
x— ＋ O log |a a | —x————+ (−1) 2 —∆ ———4 a log x(log x)3/2
12)

ただし
∆a =

Σ [K , : ] − Σ [K , : ]
hψ(v)

hψ(v)

————√-￣2∈K2v,2vv : odd2v2v————√￣2 ∈K2v,2vv : odd2v2v

上の二つの定理の要点は，① すべての場合に自然密度の存在が証明されている。ただし場合によっては一般リーマン予想が必要になる。なお，文献［７］も参照。
② 定理１では，j ＝1, 3 の場合の式が共通であり，その自然密度を表わす式には拡大次数しか出てきていない。つまり j による特殊性がないのである。これに対して，定理２の j ＝1, 3の場合，∆a を含む部分が j によって変化するため，密度が違っていることが読み取れる。
Qa (x ; u (mod t)) を更に細分して Ra (x ; l (mod m), u (mod t)) を考察したのは，こうした現象が明らかになるからである（モレー氏の注意による）。
なお，定理１，定理２では素数全体を次のように分割して結果が述べてある：{ p≡1 (mod 24)}
{ p≡1 (mod 23)}
{ p≡1 (mod 4)}{ p≡9 (mod 24)}3

素数全体

{ p≡5 (mod 2 )}{ p≡3 (mod 4)}

研 究 所 年 報134

そして太文字にした集合の密度だけが定理では述べられていた。しかし差をとってやれば，他の様々な集合の密度も求めることができる。たとえば，
Ra (x ; 9 (mod 24) ; j (mod 4))=Ra (x ; 1 (mod 23) ; j (mod 4)) − (Ra (x ; 1 (mod 24) ; j (mod 4))など。
さて，上の二つの定理は自然密度を体の拡大次数などによって書き表しているだけなので，実際に密度がどのくらいなのか知ろうと思ったら，級数に現われた拡大次数などを正確に求めておかなくてはならない。一般的に言って，拡大体の次数計算はそんなに難しくはない（ j ＝0, 2 の場合は拡大次数の計算だけで済むので，その点でも幾分易しい）。これに対し，p ≡3 (mod 4) の場合に現われた ∆a の計算はかなり厄介である。
途中の計算は省略して，結果のみ述べると次のようになる。
なお，以下では D は二次体( √a￣0 ) の判別式を表わすものとする（a0は a の square freepart）。また sgn (a) は単に a の符号を表す。
定理３ 一般リーマン予想を仮定する。s は今まで通り，任意の自然数である。
D が２のべき乗でない場合，われわれの求めていた密度は次のようになる。
Ï221−s − ̶ 41−s3

ÍÍ 141−s6
δa (1 , 2 ; j , 4) =Ì
1 1−s̶43
1 1−s̶4Ó 6j=1̶sj=0

ÍÍj=2j=3p ≡3 (mod 4) なる素数に対する結果は，少し複雑である。
定理４ 一般リーマン予想を仮定する。
(1)8 | D かつ D が q ≡1 (mod 4) なる素因子 q を持たない場合，
j+111̶δa (3 , 4 ; j , 4) = ̶ ＋ ̶ C sgn (a) (–1) 2 Ba
88

ただしC =p∏ ( 1 − ( p +12p) ( p−1) ) ≈ 0.643650...

≡3 (mod 4)

Ba =(2)∏p|Dp≡3 (mod 4)

̶̶
̶
̶
̶̶
̶
̶

22pp3−p2−p−1̶̶̶̶

8 /| D ，または D が q ≡1 (mod 4) なる素因子 q を持っている場合，

剰余位数の分布の一性質について Ⅱ1351
δa (3 , 4 ; 1 , 4) =δa (3 , 4 ; 3 , 4) = ̶8

定理４に現われた定数 C, Ba は『中間報告』にも既にあらわれた定数である。このうち，Cは絶対定数，そして Ba は有限積なので有理数になることに注意しておく。定理３，４により，
Qa (x ; u (mod t)) の密度は必ずα＋βC, α, β∈の形に書けることが分かる。
さて，ここで定理１〜４を使って得られる結論を幾つか列挙してみたい。
上述したように，今回考察した Ra (x ; l (mod m) ; u (mod t)) は，Qa (x ; u (mod t)) を細分化したものであるから，Qa (x ; j (mod 4)) を求めようと思ったら，Ra (x ; l (mod m) ; j (mod 4)) を足し合わせてやればよい。
例１

1
1
11
我々が今回の問題に注目するきっかけになった，／3 ，／6 ，／3 ，／6という綺麗な分布は，定理３，４で s ＝２とおいてみれば得られる。例えば a が square-free で法４で１に合同な自然数の場合，
Ï 1ÍÍ̶

j=0124j=1112j=23̶̶

δa (1 , 4 ; j , 4) =Ì

ÍÍ

̶
̶

1̶̶

j=3

Ï 01̶Í 8
δa (3 , 4 ; j , 4) =Ì 1j=0

Ó 24Í

ÍÍ

̶

41

̶Ó 8

j=1j=2j=3が容易に計算できるので，この両者を足してやれば，確かに例の分布が得られている。
例２a = 6 ととって，Q6 (x ; 1 (mod 4)) を考えよう。
『中間報告』の定理４で，この自然密度は13̶ C ≈ 0.13219... ，−̶（C は定理４の C と同じ）
656̶になることが分かっていた。

研 究 所 年 報136

今回の結果を使ってこれを再確認する。
Q6 (x ; 1 (mod 4)) = R6 (x ; 1 (mod 4) ; 1 (mod 4)) + R6 (x ; 3 (mod 4) ; 1 (mod 4))
そして1
̶
δ6 (1 , 4 ; 1 , 4) = ̶24
さらに（定理３，s=2の場合）
j+1̶

sgn (6) ＝＋１，( −１) 2 ＝−１，D ＝24より
1
1313
̶C
δ6 (3 , 4 ; 1 , 4) = ̶ + ̶ ·1· (−1) ̶ C = ̶ − ̶
88785611313
̶ C =̶−̶̶ C+ ̶−̶
24
856
656

̶
̶

以上の計算によって，同じ結論が得られた。
これ以外の例は，後で数値例を出すときに一緒に述べる。

３．４以外の法について『中間報告』にも一部書いたことだが，我々の Qa (x ; u (mod t)) に関する問題は，剰余 t を法とする加法群 ／t の構造と深い関わりがある。t ＝４の場合，この加法群は次のような構造になっていて，２つの部分群をもっている：{ 0, 1, 2, 3} = ／4∪
{0, 2}∪{0}

ここで，一番下の部分群を使って得られるのが Qa (x ; 0 (mod 4)) に関する結果であり，これは仮定なしで得られる。中央の部分群を使って得られるのが Qa (x ; 0 (mod 2)) = Qa (x ; 0 (mod 4)) +Qa (x ; 2 (mod 4)) に関する結果で，これにも仮定は不要である。両者を差し引くと，Qa (x ; 2 (mod 4))に関する結果が，やはり仮定なしで得られるのである。ところが部分群はこの二つしかないため，１の類と３の類を分離することができず，これを分離しようとしたら一般リーマン予想が必要になるということであろう。
では，t ＝3の場合はどうなるであろうか。この場合，法３の加法群は次のようになっている。

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

137

mod 3の加法群

mod 5の加法群{0, 1, 2} = ／3

{0, 1, 2, 3, 4} = ／5∪∪{0}{0}

そこで期待できるのは，一番下の部分群を使って得られる Qa (x ; 0 (mod 3)) は仮定なしで得られ，１の類と２の類の分離にはリーマン予想が必要になる，ということであろう。そして実際にその通りなのである。
これも結果のみを書くことにする（［12］）。
定理５j ＝0 に対しては無条件，j ＝1 , 2に対しては一般リーマン予想を仮定する。また s は任意の自然数。
(1) Ra (x ; 1 (mod 3 ) ; j (mod 3)) や Ra (x ; 2 (mod 3)) ; j (mod 3) は自然密度をもつ。
sss(2) Ra (x ; 1 (mod 3 ) ; j (mod 3)) の自然密度をδa (1 , 3 ; j , 3) とすれば，これは次で与えられる：

Ï 1Í

̶

2

131−s− ̶ 32−2s
8j=01s̶ 2−2sδa (1 , 3 ; j , 3) =Ì ̶3
16j=1

1 2−2s
316Ó

j=2Í

̶
̶

(3) Ra (x ; 2 (mod 3) ; j (mod 3)) の自然密度をδa (2 , 3 ; j , 3) とすれば，これは次のように与えられる。法３の Dirichlet 指標のうち，principal な方をχ0 ，principal でない方をψとする。ま'た絶対定数 C を次で定義する：'C =p∏ ( 1− ( p +1)2p( p−1) ) ≈ 0.173977...

≡2 (mod 3)

̶̶
̶
̶̶̶
—̶—̶

2

すると，
D が q ≡1 (mod 3) なる素因子 q を持つ場合，'11
δa (2 , 3 ; j , 3) = ̶ χ0 ( j ) + ̶ψ( j ) C
4
4''

D が q ≡1 (mod 3) なる素因子 q を持たない場合，D = 2d D （D は奇数）とすれば，∏'{'2p11
Ω (D )+1 2̶̶̶(i) d=0 のとき，δa (2 , 3 ; j , 3) = ̶ χ0 ( j ) + ̶ψ( j ) C 1+ (−1)
2 p|D ̶3−p2−p−1p44p>3∏

112p
Ω (D) 4-2d̶̶̶̶(ii) d>0 のとき，δa (2 , 3 ; j , 3)= ̶ χ0 ( j ) + ̶ψ( j ) C 1+ (−1)
2p|D3244p>3 p −p −p−1'{}}

研 究 所 年 報138''

ただし，Ω (D ) は D を割る素因子の個数（重複度もこめたもの）である。
1111
この定理によれば，t ＝4のときに ／3 ，／6 ，／3 ，／6 が一番自然だったように，t ＝3の場合

''

35C5C
̶ ＋ ̶ ，̶̶ − ̶ が一番自然な分布状態であることが分かる。
は ̶ ，̶
8 16
4 164

最後に t ＝5の場合について略述する。
法５の加法群は法３の場合とほとんど同じ構造を持っているので（前ページの図参照），t ＝3の場合と同様，Qa (x ; 0 (mod 5)) は仮定なしで得られ，１の類から４の類までの四つの類の分離にはリーマン予想が必要になることが予想される。そしてそれはその通りなのだが，我々の計算によれば，ここに今ひとつ興味深い現象がある。結果のみ挙げてみよう。
定理６a は square free で a ≡1 (mod 4) とする（これが一番簡単な場合である）。

5
̶π(x)(1) ＃Qa (x ; 0 , 5) 〜 ̶
24(2) ここでは一般リーマン予想を仮定する。次の四つの定数を定義する：
E0 =∏ (1 − p (p1– 1) ) ≈ 0.37395...

（Artin の定数）————

pE1 = E0 p∏ (1 − (p +1)2p(p–1) ) ≈ 0.12931————————

2≡2,3 (mod 5)√–￣1 )p∏ (1 − (p +1)2p(p–1) )∏ (1 − (p(1–– √√￣–1–￣1) (p) p–1) ) ∏ (1 − (p(1++ √￣–1) (p–1) )E2 = E0 p

—
—
—
—
—
—
—
—
—

≡2 (5)

2p≡3 (5)

———
—
—
—
—
—
—

2

p≡4 (5)

—
—
—
—
—
—
—
—

2

≈ 0.36469 + 0.22404 √–￣
1E3 = E2の複素共役
すると次の漸近式が得られる：
Ï 19ÍÍ̶̶

961
̶
−̶(E −E2−E3)
16 1191̶−̶(−E1−√–￣
1 E2＋√–￣1 E3 )9616j=2191
̶−̶(−E1＋√–￣
1 E2−√–￣1 E3 )
96
16j=3

̶̶

π(x)

-1

#Qa (x ; j , 5) の主要部〜ÌÍÍj=1̶̶19̶̶Ó 961̶−̶
(E −E2−E3)
16 1j=4

ここで興味深いのは，定数 E2と E3が複素数になっていることである。ところが密度を与える部分ではこの四つの複素定数が巧く虚部が消えるように組み合わさっているので，結果として実定数を与えている（ここでは話を簡単にするため，#Qa (x ; j , 5) の主要部について述べたが，剰余位数の分布の一性質について Ⅱ

139

Qa ( x ; j , 5) の正確な密度に対しても同じ現象がおきている）。我々の考えているのはある素数集合の密度なので，これが（存在するなら）実数値であることは明らかなのだが，それが複素定数の組み合わせによって与えられているところが大変興味深い。この t ＝5のときの現象を見ると，おそらく一般の t を法とした場合には，ϕ(t) 個の複素定数が現われ（その定義式には t を法とする Dirichlet 指標が現れる），その組み合わせによって，問題の素数集合の密度が与えられることになっているのだろう。ただ，その詳しい証明についてはまだ残っている部分がある。

４．数 値 例
最後に，理論値と実測値の比較のため，数値実験の結果をまとめておく。なお，こうした数値実験は，我々の場合，単に理論値の検証というだけでないと思っている。我々の結論は一般リーマン予想を仮定しているので，一般リーマン予想はこうした面でも実際と良く合うといった見方ができるのではないかと考える。
例３t ＝４の場合の例。実測値では小さい方から107個の素数を使って計算してある（x ＝179424673である）。従って一番右の欄には10-7＃Ra (x ; 3 (mod 4); 1 (mod 4)) の値が記入してある。

a の値

δa (3 , 4 ; 1 , 4) の理論値

その実測値

2—

11− — C ≈ 0.044544
880.044580−2—

11＋ — C ≈ 0.090519
880.090605

10—

1= 0.12580.124993

14—

17———−—C ≈ 0.121062
811440.121106

研 究 所 年 報

140

例４

t ＝３の場合の例。一番右の欄は10-7#Ra (x ; 2 (mod 3) ; 1 (mod 3)) である。

a の値

その実測値

—

1= 0.25
40.250011

5

—

167—
—＋—
C ≈ 0.304368
41880.304333

14—

11＋ — C ≈ 0.293494
440.293398'3'

例５δa (2 , 3 ; 1 , 3) の理論値

t ＝５の場合の例。ここでは上と異なり，π (x) ‒1 #Qa (x ; j , 5) を比較してある。密度の理論値は定理６に挙げた近似値を使うとa の値
132142j =10.235543
0.235494
0.235654

j=20.178356
0.176925
0.178146

j=30.234475
0.233715
0.233766

j=40.143292
0.145532
0.144101となる。これを x として108をとって，比較のため実測値を計算してみたのが，次の表である。
a の値
132142j =10.235620
0.235709
0.235541

j=20.178355
0.176875
0.178005

j=30.234440
0.233722
0.234004

j=40.143273
0.145379
0.144144

参考文献[ 1 ] Chinen K., Murata L., On a distribution property of the residual order of a (mod p).
e-print archive,
http://xxx.lanl.gov/archive/math, article number math. NT/0211077[ 2 ] Murata L., Chinen K., On a distribution property of the residual order of a (mod p), II .
e-print archive,
http://xxx.lanl.gov/archive/math, article number math. NT/0211083[ 3 ] 知念宏司 - 村田玲音 : On a distribution property of the residual order of a (mod p). I, 京都大学数理解
析研究所 講究録1219 (2001), 245 - 255.
[ 4 ] 知念宏司 - 村田玲音 : On a distribution property of the residual order of a (mod p). II, 京都大学数理解析研究所 講究録1274 (2002), 62 - 69.
[ 5 ] Hasse H. : Über die Dichte der primzahlen p, für die eine vorgegebene ganzrationale Zahl a > 0 vongerader bzw. ungerader Ordnung mod p ist, Math. Ann. Bd.166 (1966) pp. 19 - 23.
[ 6 ] Hooley C. : On Artin’s Conjecture, J. Reine angew. Math. Bd 225 (1967) pp. 209 - 220.
[ 7 ] Lenstra Jr. H.W. : On Artin’s conjecture and Euclid’s algorithm in global ﬁelds, Invent. Math. Vol.42

剰余位数の分布の一性質について Ⅱ141(1977) pp. 201 - 224.
[ 8 ] Moree P. : On the density of primes in arithmetic progression having a prescribed root, MpI-preprint
57, Bonn 1998.
[ 9 ] Murata L. : A problem analogous to Artin’s conjecture for primitive roots and its applications, Arch.
Math. Vol.57 (1991) pp. 555 - 565.
[ 10 ]

村田玲音 - 石井坦 : 剰余位数の分布の一性質について，明治学院大学産業経済研究所

研究所年報第18号 (2001), 65 - 72.
[ 11 ] Odoni R.W.K. : A conjecture of Krishnamurthy on decimal periods and some allied problems, J. of
Number Theory 13 (1981), 303 - 319.
[ 12 ] Moree P. : On the distribution of the order and index of g(mod p) over residue classes.
e-print archive, http://xxx.lanl.gov/archive/math, archive number math NT/0211259.