原始根
著者:梅谷 武
語句:ウィルソン,原始根,離散指数,底,離散対数,直積分解,n冪剰余,n冪非剰余,平方剰余,平方非剰余
原始根について述べる。
作成:2006-06-16
更新:2013-06-14
 オイラーは『数論研究』において、素数pを法として考える場合、
{ 1=r0,r,r2,⋯,rp-1 }
がすべて異なるような数rφ(p-1)個存在することを発見し、これを原始根と呼びました。これは既約剰余類群(ℤ/pℤ)×が位数p-1の巡回群になっていて、その生成元がφ(p-1)個存在するということです。オイラー自身は任意の素数についてその原始根の存在を証明することができませんでしたが、ガウスは『整数論』でこれを証明し、さらに任意の奇素数の冪を法とする場合も原始根が存在すること、そして2の冪が法の場合は原始根が存在しないことを示しました。この節では、まず、この原始根がどのように役に立つかを例を使って説明し、その後で任意の素数冪を法とする既約剰余類群の構造について解説します。
5を法として2の冪乗を計算してみます。
20 ≡ 1, 21 ≡ 2, 22 ≡ 4, 23 ≡ 3, 24 ≡ 1
となり、既約剰余類群(ℤ/5ℤ)×={1,2,3,4}2で生成される巡回群になっています。これは2は法5の原始根であることを示しています。2c≡aであるときab2を底とする指数といい、これを
log2 a = c
と書くことにします。ガウスは『整数論』で
Ind. a = c
高木貞治は『初等整数論講義』で
Ind2 a = c
と書いていましたが、本書では暗号理論で一般的に使われている記号を採用することにします。
 指数に関して一般に次の性質が成り立ちます。
a ≡ b (mod p) ⇔ logr a ≡ logr b (mod p-1)
また、離散対数と呼ばれるlogr関数には対数と同じような性質があります。
logr(ab)
=
logr(a) + logr(b)
logr(ak)
=
klogr(a)
これらの性質から、既約剰余類の計算を指数計算に変換することができます。

例題5.6.4

3X ≡ 4 (mod 5)
 この一次合同式は暗算でも簡単に解けますが、離散対数を使って解いてみます。この場合、原始根2とそれを底とする指数表が与えられていることが必要です。
 まず、両辺の2を底とする離散対数をとります。
log2 3 + log2 X ≡ log2 4 (mod 4)
指数表を参照して値を代入すると
3 + log2 X
2 (mod 4)
log2 X
-1 ≡ 3 (mod 4)
となり、また指数表を参照することで解X≡3(mod 5)を得ます。

例題5.6.8

X3 ≡ 2 (mod 5)
 両辺の離散対数をとると
3 log2 X ≡ log2 2 ≡ 1 (mod 4)
となりますが、法43倍して1と合同になるものは3しかありませんから、log2X≡3(mod 4)より、解X≡3(mod 5)を得ます。

例題5.6.10

3X2 - X + 1 ≡ 0 (mod 5)
 両辺に2をかけると
X2 - 2X + 2
0 (mod 5)
(X-1)2
-1 ≡ 4 (mod 5)
ここで両辺の離散対数をとると、
2 log2 (X-1) ≡ log2 4 ≡ 2 (mod 4)
42倍して2と合同になるものは13ですから、
log2 (X-1)
1 または 3 (mod 4)
X-1
2 または 3 (mod 5)
となり、解はX≡3または4(mod 5)となります。

既約剰余類群の構造

 任意の法mに対して、その素因数分解をm=p1e1 ⋯ pkekとすれば系5.4.66より、
(ℤ/mℤ)× ≅ (ℤ/p1e1ℤ)× × ⋯ × (ℤ/pkekℤ)×
と素数冪を法とする既約剰余類群の直積に分解されますから、素数冪を法とする既約剰余類群の構造がわかればすべての法の既約剰余類群の構造がわかります。
 素数冪を法とする既約剰余類群の構造は次の4種類に分類されます。
(1) p, p:素数の場合
(ℤ/pℤ)× ≅ <r>, rp-1 ≡ 1 (mod p)
(2) pe, p:奇素数, e>1の場合
(ℤ/peℤ)× ≅ <r>, rpe-1(p-1) ≡ 1 (mod pe)
(3) 22=4の場合
(ℤ/22ℤ)× ≅ <-1>, (-1)2 ≡ 1 (mod 4)
(4) 2e, e>2の場合
(ℤ/2eℤ)× ≅ <-1> × <5>, (-1)2 ≡  52e-2 ≡ 1 (mod 2e)
(1),(2),(3)の場合は巡回群になり、(4)の場合だけ2個の巡回群の直積になります。(1),(2)の場合、既約剰余類群の生成元を原始根げんしこん, primitive rootと呼びます。

巡回群

 有理整数環を加法群と考えたとき、その部分群Hは加法に関して閉じているので、任意のn∈ℤ, h∈Hに対して、
nh = h + h + ⋯ + h (n個の和)
を満たしますから、Hのイデアルになっています。したがって、の部分群全体の集合はイデアル全体の集合ℑ(ℤ)と一致し、定理2.4.32より、包含関係に関して(ℕ,|)と双対な束を成します。
Gが巡回群であるとしましょう。巡回群とは一個の元aで生成される群のことでした。
G = <a> = { ak | k∈ℤ }
このとき、加法群からGへの写像を
ea:ℤ → G, k ↦ ak
と定めると、
ea(k+l) = ak+l = ak al = ea(k)ea(l)
となり、加法群から乗法群への全射準同型写像になります。巡回群Gとその生成元aによって定まるこの写像を離散指数りさんしすう, discrete exponentioalといいます。この写像の核はGの位数が無限の場合は{ 0 }、位数がnの場合は(n)=nℤですから、群の準同型定理から、
(1) Gの位数が無限の場合、ℤ ≅ G
(2) Gの位数がnの場合、ℤ/nℤ ≅ G
となり、すべての巡回群は加法群としてのℤ/nℤと同型になることがわかります。
 この同型写像の逆写像は位数が無限の場合、
loga:G → ℤ, ak ↦ k
位数がnの場合、
loga:G → ℤ/nℤ, akk
となりますが、これをaてい, baseとする離散対数りさんたいすう, discrete logarithmといいます。

命題5.6.18 対数法則

 巡回群G上で定義された離散対数に関して次が成り立つ。
(i) loga(bc) = loga(b) + loga(c)
(ii) loga(bk) = kloga(b)
(iii) bが生成元のとき、loga(b)logb(c) = loga(c)

証明

 (i),(ii)は定義より。(iii)はloga(b)=k,logb(c)=lとすればb=ak,c=blであるからc=(ak)l= akl.
 巡回群がℤ/nℤと同型になることから、巡回群がもつ特別な性質がいろいろとわかってきます。すぐにわかることは
(C1) 巡回群は可換である。
(C2) 巡回群の部分群は巡回群である。
ということです。
 次に巡回群Gの位数nが有限の場合を考えます。の部分群全体の集合は自然数の整除関係に関する束と双対になりますが、ℤ/nℤの部分群全体の集合はどのような構造を持つのでしょうか。
 大雑把に言えばℤ/nℤの部分群全体の集合は、の部分群全体の集合が成す束をnℤで割ってできる有限束になります。例としてn=6の場合を図示しておきます。
一般にℤ/nℤの部分群の成す束は次のような集合です。
{ dℤ/nℤ ≅ ℤ/(n/d)ℤ | d | n }
nの約数dの集合と一対一に対応し、dに対応する部分群はℤ/(n/d)ℤと同型になります。このことを次のようにまとめておきます。
(C3) 位数nの巡回群にはnの各約数dに対してn/dを位数とする部分群が唯一つだけ存在し、それが部分群のすべてである。
 巡回群G=<a>の位数が無限の場合は、その生成元はaa-1の二つしかありませんが、位数nが有限の場合は様子が違ってきます。

補題5.6.27

 群Gの元aの位数がnであるとする。任意の正の整数mについてd=(m,n)とするとamの位数はn/dである。

証明

amの位数をkとし、n'=n/dとおく。amk=1よりn|mkであるから、n'|k.一方、n|mn'よりamn'=1であるからk|n'.したがってn'=k.
 この補題から次のことがわかります。
(C4) 位数nの巡回群G=<a>において、amの位数がnとなることと(m,n)=1となることは同等である。
したがって、位数nの巡回群の生成元の個数はφ(n)に等しくなります。
 位数nの巡回群Gの元をその位数で分類することを考えます。Gの元の位数はnの約数ですから、Odで位数dの元の集合を表わすとG
G = ∪d|n Od
と分割されます。Odの各元は位数dの部分群を生成しますが、それは(C3)から唯一つしか存在しませんから、Odは位数dの部分群の生成元全体の集合に他なりません。これはφ(d)と等しくなりますから、結局
n =
 

d|n
φ(d)
が成り立つことがわかります。これは命題5.5.36の別証明になっています。
 次の補題は(ℤ/pℤ)×における原始根の存在を証明するために使われます。

補題5.6.32

 有限群Gにおいて、任意の正の整数dに対してxd=1を満たす元が高々d個しか含まれないとき、Gは巡回群である。

証明

Gの位数をnとする。位数nの元が存在することを示せばよい。正の整数dに対して位数がdであるようなGの元の個数をψ(d)とする。ラグランジュの定理からGの元の位数はnの約数であるから、Odで位数dの元の集合を表わすとG
G = ∪d|n Od
と分割され、
n =
 

d|n
ψ(d)
が成り立つ。aを位数dの元とすると、aが生成する部分群<a>={1,a,a2,⋯,ad-1}の元はすべてxd=1を満たすので、仮定より位数dの元はこれ以外には存在しない。したがって、
ψ(d) = lc48
φ(d),
位数dの元が存在するとき
0,
位数dの元が存在しないとき
となるが、一方で
n =
 

d|n
ψ(d)
=
 

d|n
φ(d)
が成り立っていることから、nの任意の約数dについてψ(d) = φ(d)であり、特にψ(n) = φ(n)>1となり、位数nの元が存在する。■

ℤ/pℤの既約剰余類群の構造

 任意の素数pについて、Fp=ℤ/pℤは標数pの有限体です。系3.6.57より、任意の正の整数dについてd次の一元代数方程式
Xd - 1 = 0
の根は高々d個ですから、補題5.6.32より既約剰余類群(ℤ/pℤ)×は位数p-1の巡回群です。

ℤ/peℤの既約剰余類群の構造

 まず、次の補題を準備しておきます。

補題5.6.36

pを奇素数としたときに、(k,p)=1なる整数kと、m≧1なる整数mについて、
(1+kpm)p = 1 + k'pm+1, (k',p) = 1
なる整数k'が存在する。

証明

 二項定理より、
(1+kpm)p
=
1 +
(p
1
)
kpm +
(p
2
)
k2p2m + ⋯ + kpppm
=
1 + kpm+1 +
p!
(p-2)!2!
k2p2m + ⋯ + kpppm
=
1 + pm+1 ( k +
(p-1)!
(p-2)!2!
k2p2m + ⋯ + kp ppm - m + 1 )
であるから、右辺の括弧の中をk'とおけばk≡k'(mod p)であり、(k',p)=1が成り立つ。■
 奇素数pe>1なる整数eについて、既約剰余類群(ℤ/peℤ)×は位数pe-1(p-1)の巡回群になることを示します。
rを既約剰余類群(ℤ/pℤ)×の原始根とすると、ある整数kによって
rp-1 = 1 + k p
と書くことができます。まず、(k,p)=1と仮定しましょう。そうすると 上の補題から、
(1+kp)p
=
1 + k1p2, (k1,p)=1
(1+kp)p2
=
1 + k2p3, (k2,p)=1
(1+kp)pe-2
=
1 + ke-2pe-1, (ke-2,p)=1
(1+kp)pe-1
=
1 + ke-1pe, (ke-1,p)=1
となり、
rps(p-1)
1 (mod pe), s<e-1
rpe-1(p-1)
1 (mod pe)
であることから、(ℤ/peℤ)×におけるrの位数はpe-1(p-1)となり、r(ℤ/peℤ)×の原始根になっていることがわかります。
(k,p)≠1の場合は、ある整数kt≧1によって
rp-1 = 1 + k pt
と書くことができます。ここでr'=r+pとおくと、
r'p-1 = 1 + k'p, (k',p)=1
となり、(k,p)=1の場合に帰着することができます。これは二項定理より、
(r+p)p-1
=
rp-1 +
(p-1
1
)
rp-2p +
(p-1
2
)
rp-3p2 + ⋯ + pp-1
1 + (p-1)rp-2p (mod p2)
1 - rp-2p (mod p2)
となり、
(r+p)p-1 = 1 + (kp - rp-2)p, k∈ℤ
と書け、ここで(kp - rp-2,p)=(rp-2,p)=1となっています。

ℤ/2eℤの既約剰余類群の構造

ℤ/4ℤの乗算表を次に示します。
 この表から(ℤ/22ℤ)× = { 1,3 }は位数2の巡回群となることがわかります。計算の都合上、この既約剰余系として{ 1,-1 }をとることにします。
e>2のとき、既約剰余類群(ℤ/2eℤ)×は、奇素数pに対する既約剰余類群(ℤ/peℤ)×とは異なり、巡回群にはなりません。しかし、二つの巡回群の直積として表現することができます。
 一般に群の直積G=G1 × G2 × ⋯ × Gkは自然な埋め込み写像
Gi → G1 × ⋯ Gi × ⋯ × Gk, ai ↦ (1,⋯,ai,⋯,1)
によって、その各因子Giを正規部分群として含んでいるとみなすことができ、さらに次の条件を満たしています。
(a) i≠jならばGiGjの元は可換である。
(b) Gの任意の元はa1a2⋯akと一意的に表わすことができる。
逆に、Gの部分群G1,G2,⋯,Gkが(a),(b)を満たすとすれば、写像
G1 × G2 × ⋯ × Gk → G, (a1,a2,⋯,ak) ↦ a1 a2 ⋯ ak
は群の同型写像となります。このときG1×G2×⋯×GkG直積分解ちょくせきぶんかい, direct product decompositionといいます。
 次の補題は部分群の積が直積分解になっているかどうかを判断する条件を与えています。

補題5.6.47

 群Gがその部分群G1,G2,⋯,GkによってG=G1×G2×⋯×Gkと直積分解されることと次の三つの条件が必要十分である。
(i) Gi,i=1,⋯,kGの正規部分群である。
(ii) G=G1 G2 ⋯ Gk
(iii) (G1 ⋯ Gi) ∩Gi+1 = {1}, i=1,⋯,k-1

証明

[⇒](i),(ii)は条件(a),(b)から。(iii)a1 ⋯ ai = ai+1とするとa1⋯aiai+1-1=1であり、分解の一意性からak=1, k=1,⋯,i+1.[⇐](a) i≠jとし、任意のai∈Gi, aj∈Gjについてaiaj=ajaiを示す。aiajai-1aj-1=(aiajai-1)aj-1=ai(ajai-1aj-1)Gi,Gjが正規部分群であることからGi,Gjに含まれ、Gi∩Gj={1}に含まれる。よってaiajai-1aj-1=1よりaiaj=ajai.(b) (ii)より任意のGの元はa1a2⋯akと分解される。a1a2⋯ak=b1b2⋯bkという二つの分解があったとする。i≠jなる元の可換性から、
(b1-1a1) (b2-1a2) ⋯ (bk-1-1ak-1) = bk ak-1
となり、(iii)よりbk ak-1=1となり、ak=bkであることがわかる。同じようにしてi=1,⋯,k-1なるiについてai=biが成り立つ。■
 群の直積分解に関する準備が整ったので、e>2のときの既約剰余類群(ℤ/2eℤ)×の構造を調べることにしましょう。
p=2のとき補題5.6.36は成り立ちませんが、その証明からわかるようにm>1という条件にすれば成り立ちます。

補題5.6.51

(k,2)=1なる整数kと、m>1なる整数mについて、
(1+k2m)2 = 1 + k'2m+1, (k',2) = 1
なる整数k'が存在する。

証明

 演習とする。■
 この補題をk=1,m=2に適用すると5=1+22ですから、
52
=
1 + k1 23, (k1,2)=1
522
=
1 + k2 24, (k2,2)=1
52e-3
=
1 + ke-3 2e-1, (ke-2,2)=1
52e-2
=
1 + ke-2 2e, (ke-1,2)=1
となり、法2eで考えると5の位数は2e-2です。ϕ(2e)=2e-1ですから、<5>={ 5i | i = 0,1,⋯,2e-2-1 }(ℤ/2eℤ)×の指数2の部分群になっています。
(ℤ/2eℤ)× ≅ <-1> × <5>
であることを示します。5≡1(mod 4)より、正の整数iについて5i≡1(mod 4)ですから、-1∉<5>であることがわかります。既約剰余類群は可換ですから、任意の部分群は正規部分群になり、特に<-1><5>は正規部分群で、<-1>∩<5>={1}が成り立っていますから、両辺の位数が等しいことから同型であることがわかります。

冪剰余

pを素数とするとき、正の整数に対して
Xn ≡ a (mod p)
が解をもつとき、apn冪剰余nべきじょうよ, residue of n-th powerであるといい、解をもたないとき、n冪非剰余nべきひじょうよ, non-residue of n-th powerであると いいます。
 素数を法とする原始根の存在が保証されたことによって、冪剰余の判定条件に関する次の定理を容易に証明することができます。

定理5.6.56

pを素数とするとき、正の整数に対して
Xn ≡ a (mod p)
が解をもつ必要十分条件は、d=(n,p-1)としたとき
a(p-1)/d ≡ 1 (mod p)
となることである。このとき解の個数はd個である。

証明

pを法とする原始根をrとすると、Xn≡a(mod p)
n logr X ≡ logr a (mod p-1)
と同等であり、命題5.2.3より、d|lograのとき、p-1を法としてd個の解をもつことがわかっている。[]d|lograであるとする。logra=m, m=m'dとおくと、
a(p-1)/d ≡ rm(p-1)/d ≡ rm'(p-1) ≡ 1 (mod p)
となり、aは解である。[]
a(p-1)/d ≡ rm(p-1)/d ≡ 1 (mod p)
より、p-1|m(p-1)/dであるから、d|mが成り立つことがわかる。■

系5.6.58

 素数pを法とするn冪剰余は、d=(n,p-1)としたときp-1個ある既約剰余類の中にp-1/d個存在する。
 法13においていくつかの例を見てみます。

例題5.6.61

X3 ≡ a (mod 13)
 両辺の離散対数をとると、
3 log2 X ≡ log2 a (mod 12)
(3,12)=3より、3冪剰余となるaに対応する指数log2a0,3,6,9の4個で、それに対応する既約剰余類、すなわち3冪剰余は1,5,8,12の4個です。
 特にn=2,p≠2のとき、pを法とする2冪剰余を平方剰余へいほうじょうよ, quadratic residue2冪非剰余を平方非剰余へいほうひじょうよ, quadratic non-residueといいます。

例題5.6.64

X2 ≡ a (mod 13)
 両辺の離散対数をとると、
2 log2 X ≡ log2 a (mod 12)
(2,12)=2より、平方剰余となるaに対応する指数log2a0,2,4,6,8,10の6個で、それに対応する既約剰余類、すなわち平方剰余は1,3,4,9,10,12の6個です。

ウィルソンの定理

 次の定理はガウスの『整数論』によればウェアリングによって最初に公表されたものですが、ウィルソンWilson, John, 1741-1793の功績とされ、1771年にラグランジュによって始めて証明されました。このとき、オイラーがラグランジュからウィルソンの定理に関する二種類の証明を受け取ったときに、オイラーは原始根を使った証明をラグランジュに返送しました。ここではそのオイラーの証明を紹介することにします。

定理5.6.67 ウィルソンの定理

pを素数とするとき、
(p-1)! ≡ -1 (mod p)

証明

 法pの原始根をrとすれば、
(p-1)! ≡ r1+2+ ⋯ + (p-2) ≡ r(p-1)(p-2)/2 (mod p)
ここで、rの位数はp-1であるから、(r(p-1)/2)2≡1(mod p), r(p-1)/2≢1(mod p)となり、r(p-1)/2の位数は2である。法pの既約剰余類群は位数p-1の巡回群であるから、位数2の元はϕ(2)=1個しか存在せず、-1は位数2であるからr(p-1)/2≡-1(mod p)であり、
(p-1)! ≡ (-1)p-2 ≡ -1 (mod p)
nが合成数であるときn=ab, a > 1, b > 1と書けます。このとき、
a | (n-1)!, b | (n-1)!
であり、一般にm>1のとき(m,m+1)=1ですから、
a ∤ (n-1)!+1, b ∤ (n-1)!+1
から
n ∤ (n-1)! +1 ⇔ (n-1)! ≢ -1 (mod n)
が成り立ちます。これを素数判定法としてまとめておきます。

命題5.6.70 ウィルソンの素数判定法

nが素数である必要十分条件は、
(n-1)! ≡ -1 (mod n)
 この条件で素数であるかどうか判定するには階乗の計算が必要になるため、実際にはあまり使われません。

参考文献

[1] カール・フリードリヒ ガウス(高瀬正仁訳), ガウス 整数論, 朝倉書店, 1995
img
 
 
[2] 高木 貞治, 初等整数論講義 第2版, 共立出版, 1971
img
 
 
[3] 遠山 啓, 初等整数論, 日本評論社, 1972
[4] 河田 敬義, 数論―古典数論から類体論へ, 岩波書店, 1992
img
 
 
[5] アンドレ ヴェイユ, 数論―歴史からのアプローチ, 日本評論社, 1987
img
 
 
人  物
ウィルソン Wilson, John, 1741-1793
 
数  学
原始根 げんしこん, primitive root
離散指数 りさんしすう, discrete exponentioal
てい, base
離散対数 りさんたいすう, discrete logarithm
直積分解 ちょくせきぶんかい, direct product decomposition
n冪剰余 nべきじょうよ, residue of n-th power
n冪非剰余 nべきひじょうよ, non-residue of n-th power
平方剰余 へいほうじょうよ, quadratic residue
平方非剰余 へいほうひじょうよ, quadratic non-residue
 
Published by SANENSYA Co.,Ltd.