情報代数学 I
山内 博 ∗
東京女子大学 数理科学科
2015 年度前期
∗
http://www.math.twcu.ac.jp/~yamauchi
1
目次
1
ユークリッドの互除法
2
素数
11
3
合同式
13
4
オイラー関数
17
5
フェルマーの小定理
19
6
RSA 暗号
21
3
参考文献
楫 元，工科系のための初等整数論入門―公開鍵暗号をめざして，培風館
2
ユークリッドの互除法
1
定義 1.1. a, b ∈ Z, a ̸= 0 とする。b = ak となる k ∈ Z が存在するとき，a は b の約
数もしくは因数，b は a の倍数であるといい，記号で a | b と表す。これを式で書けば
次のようになる。
a | b ⇐⇒ ∃k ∈ Z s.t. b = ak
命題 1.2. 0 でない整数 a, b, c について次が成り立つ。
(1) 任意の整数 k について k | 0
(2) ±1 | a, ±a | a
(3) a | b, b | a =⇒ a = ±b
(4) a | b, b | c =⇒ a | c
【証明】 (1): 0 = 0 · k より k | 0 である。
(2): a = 1 · a = (−1) · (−a) より ±1 | a, ±a | a である。
(3): a | b, b | a とすれば a = bu, b = av (u, v ∈ Z) と表せる。このとき
a = bu = (av)u = auv
より a(1 − uv) = 0 である。a ̸= 0 なので 1 − uv = 0, すなわち uv = 1 である。これは
u = v = ±1 のときのみ成り立つ。よって a = ±b である。
(4): a | b, b | c とすると，b = au, c = bv (u, v ∈ Z) と表せる。このとき
c = bv = (au)v = a(uv)
なので a | c である。
命題 1.3. a1 , . . . , ak , b ∈ Z, b ̸= 0 とする。各 1 ≤ i ≤ k について b | ai ならば任意の
xi ∈ Z (1 ≤ i ≤ k) に対して b | (a1 x1 + · · · + ak xk ) である。
【証明】 b | ai とすると，ai = bti (ti ∈ Z) と表せる。このとき
a1 x1 + · · · + ak xk = bt1 x1 + · · · btk xk = b(t1 x1 + · · · + tk xk )
となるから，a1 x1 + · · · + ak xk は b の倍数である。(他の証明として，まず k = 2 の場合
に主張を示し，帰納法を用いて k ≥ 3 の場合を示してもよい。)
命題 1.4. a, b ∈ Z, a > 0 とする。このとき b = aq + r, 0 ≤ r < a を満たす q, r ∈ Z
がそれぞれ唯一つ存在する。
【証明】 まず条件を満たす q, r ∈ Z が存在することを示す。A = {b − aq | q ∈ Z} とし，
A ∩ (N ∪ {0}) を考える。q ≪ 0 のとき b − aq > 0 となるので，A ∩ (N ∪ {0}) は空でない。
よって r = min A ∩ (N ∪ {0}) が存在する 1 。定義から r = b − aq と表せるので，b = aq + r
1
N ∪ {0} の空でない部分集合には最小元が存在します。
3
が成り立つ。もし r > a ならば r − a = b − a(q − 1) ∈ A ∩ (N ∪ {0}) となり，r の最
小性に矛盾する。よって 0 ≤ r < a である 2 。次に一意性を示す。b = aq + r = aq ′ + r′ ,
0 ≤ r, r′ < a となったとする。このとき r −r′ = a(q ′ −q) は a の倍数である。0 ≤ r′ < a よ
り −a < −r′ ≤ 0 であり，これと 0 ≤ r < a を合わせて −a < r −r′ < a が成り立つ。r −r′
は a の倍数であったので r − r′ = 0 でなければならない。このとき r − r′ = a(q − q ′ ) = 0
から q − q ′ = 0 でもある。よって条件を満たす q, r ∈ Z はそれぞれ唯一つである。
定義 1.5. 命題 1.4 で定まる q および r をそれぞれ b を a で割った商および余りと
いう。また命題 1.4 を (整数における) 除法の原理という。
定義 1.6. a, b をともに 0 ではない整数とする。d ∈ Z が a も b も割り切るとき，a
と b の公約数という。また m ∈ Z が a でも b でも割り切れるとき，a と b の 公倍
数という。これを式で表せば以下のとおりである。
d : a と b の公約数 ⇐⇒ d | a かつ d | b
m : a と b の公倍数 ⇐⇒ a | m かつ b | m
a と b の公約数のうち最大のものを a と b の最大公約数 (Greatest Common Divisor)
といい，gcd(a, b) もしくは単に (a, b) と表す。a, b がともに 0 でないとき，a と b の
正の公倍数のうち最小のものを a と b の最小公約数 (Least Common Multiple) とい
い，lcm(a, b) と表す。
注釈 1.7. a ̸= 0 のときは gcd(a, 0) = |a| であり，また lcm(a, 0) = 0 となる。便宜上，
gcd(0, 0) = lcm(0, 0) = 0 と定める。
次の命題は今後よく使われる。
命題 1.8. 次が成り立つ。
(1) a | m, b | m =⇒ lcm(a, b) | m
(2) n | a, n | b =⇒ n | gcd(a, b)
【証明】 (1): a | m, b | m とする。lcm(a, b) = ℓ とおく。m を ℓ で割った商を q, 余りを r
とすれば，除法の原理より
m = ℓq + r, 0 ≤ r < ℓ
が成り立つ。ここで m, ℓ は a の倍数であるから，命題 1.3 より r = m − ℓq も a の倍数
である。同様に m, ℓ は b の倍数でもあるから，命題 1.3 より r = m − ℓq も b の倍数と
なる。よって r は a, b の公倍数である。もし r ̸= 0 なら最小公倍数 ℓ の最小性に反し矛
盾が生じる。よって r = 0 であり，m は ℓ で割り切れる。
2
次のように示してもよい。a の倍数全体を考える。
. . . , −6a, −5a, −4a, −3a, −2a, −a, 0, a, 2a, 3a, 4a, 5a, 6a, . . .
このとき qa ≤ b < (q + 1)a となる q ∈ Z が存在する。このような q に対し r = b − qa とおけば b = aq + r
であり， 0 ≤ r < a を満たす。
4
(2): n | a, n | b とする。g = gcd(a, b) とおき，n と g の最小公倍数を L とする。a は n, g
の両方で割り切れるので，これらの公倍数である。よって (1) より L | a である。同様に
a も n, g の両方で割り切れるので，これらの公倍数であり，(1) より L | b である。よっ
て L は a, b の公約数となる。このとき g の最大性から L ≤ g が成り立つ。一方，L は
g の倍数であるから g ≤ L が成り立つ。よって L ≤ g ≤ L より L = g となる。L は n
の倍数であるから，n | L = g が成り立つ。
gcd(a, b), lcm(a, b) のいずれか一方が分かればもう一方も次の命題から求まる。
命題 1.9. a, b ∈ N について ab = lcm(a, b) · gcd(a, b) が成り立つ。
【証明】 g = gcd(a, b), ℓ = lcm(a, b) とおく。ab は a, b の公倍数なので命題 1.8 (1)
より ab = ℓk と表せる。ℓ は a, b の公倍数であるから ℓ = au = bv と表せるので，
ab = ℓk = auk = bvk より b = uk, a = vk である。これより k は a, b の公約数である
ことが分かり，命題 1.8 (2) から g = kn と表せる。一方，g は a および b を割り切るの
ab
b
a
で
= a · = · b は a でも b でも割り切れる。よってふたたび命題 1.8 (1) から ℓ は
g
g
g
ab
ℓk
ℓ
ℓ
=
=
を割り切る。すなわち
= ℓm となる m ∈ N が存在するが，このとき
g
kn
n
n
ℓ(1 − mn) = 0 より mn = 1, これより m = n = 1 となり，g = kn = k である。よって
ab = ℓk = ℓg が成り立つ。
定義 1.10. a, b ∈ Z は (a, b) = 1 のとき互いに素 (coprime) であるという。
命題 1.11. 整数 a, b, c について c | ab かつ (a, c) = 1 ならば c | b である。
【証明】 ab は a でも c 割り切れる。よって命題 1.8 (1) より ab は lcm(a, c) で割り切れ
ac
る。(a, c) = 1 なので命題 1.9 より lcm(a, c) =
= ac であるから，b は c で割り切
(a, c)
れる。
命題 1.12. d = (a, b) とすれば
(
a
d
,
b
d
)
= 1 が成り立つ。
a
b
【証明】 正の整数 k について k が と の公約数であることと dk が a, b の公約数で
d
d
あることと同値である。またこのとき d は a と b の最大公約数であるから，dk ≤ d であ
a
b
る。よって k = 1 でなければならない。それゆえ と は互いに素である。
d
d
命題 1.13. 任意の q ∈ Z について (a, b) = (a − bq, b) が成り立つ。
【証明】 k を a, b の公約数とすれば，命題 1.3 より k は a − bq も割り切る。逆に k を
a − bq, b の公約数とすれば，同じく命題 1.3 より a = bq + (a − bq) は k で割り切れる。
以上から k が a, b の公約数であることと a, b − aq の公約数であることは同値である。特
に両者の最大公約数は一致する。
a, b を a > b なる 正の整数とする。a を b で割ったときの商および余りをそれぞれ q0 ,
5
r0 とすると，次が成り立つ。
0 ≤ r0 < b
a = bq0 + r0 ,
r0 ̸= 0 ならば b を r0 で割ったときの商および余りをそれぞれ q1 , r1 とすると，
0 ≤ r1 < r 0
b = r 0 q1 + r 0 ,
が成り立つ。r1 ̸= 0 ならば r0 を r1 で割ったときの商および余りをそれぞれ q2 , r2 とす
ると
r0 = r1 q2 + r2 , 0 ≤ r2 < r1
となる。これを繰り返し，ri+1 ̸= 0 のとき ri を ri+1 で割ったときの商および余りを qi+2
および ri+2 とすると，作り方から余りは b > r0 > r1 > r2 > r3 > · · · を満たすので，あ
る k について rk+1 = 0 となる。
a
=
bq0
+ r0 ,
0 < r0 < b,
b
=
r 0 q1
+ r1 ,
0 < r1 < r0 ,
r0
=
r 1 q2
+ r2 ,
0 < r2 < r1 ,
r1
=
r 2 q3
+ r3 ,
0 < r3 < r2 ,
r2
=
r 3 q4
+ r4 ,
0 < r4 < r3 ,
r3
=
r 4 q5
+ r5 ,
0 < r5 < r4 ,
..
.
..
.
rk−2 = rk−1 qk + rk ,
rk−1 = rk qk+1 +
(1.1)
0.
0 < rk < rk−1 ,
(rk+1 = 0)
上の式において r−2 = a, r−1 = b とおけば −2 ≤ i ≤ k − 1 について ri = ri+1 qi+2 + ri+2
が成り立っている。このとき命題 1.13 より
(ri , ri+1 ) = (ri+1 qi+2 + ri+2 , ri+1 ) = (ri+2 , ri+1 )
が成り立つ。よって最大公約数 (a, b) は
(a, b) = (r−2 , r−1 ) = (r−1 , r0 ) = (r0 , r1 ) = (r1 , r2 ) = · · ·
· · · = (rk−1 , rk ) = (rk , rk+1 ) = (rk , 0) = rk
となることが分かる。(1.1) にある一連の計算は a, b の最大公約数を求める手順を与えて
いる。このアルゴリズムをユークリッドの互除法という。ユークリッドの互除法を応用す
ると，次の定理が証明できる。
定理 1.14. 整数 a, b ∈ Z について ax + by = (a, b) を満たす x, y ∈ Z が存在する。
【証明】 (1.1) における余り ri (0 ≤ i ≤ k) について，ri = axi + byi を満たす xi , yi ∈ Z が
存在することを i に関する帰納法で示す。r0 については a = bq0 + r0 より r0 = a + (−q0 )b
6
と表せるので，主張は成り立つ。次に 0 ≤ j ≤ i について rj = axj + byj と表せたとする
と，ri−1 = ri qi+1 + ri+1 を変形して
ri+1 = ri−1 − qi+1 ri = (axi−1 + byi−1 ) − qi+1 (axi + byi )
= a(xi−1 − qi+1 xi ) + b(yi−1 − qi+1 yi )
と表せるので，ri+1 についても主張は成り立つ。よって i = 0, 1, 2, . . . に対してこの計算
を続けていけば (a, b) = rk も ax + by と表すことができる。
注釈 1.15. 上の証明では (1.1) における余り ri に対し，ri = axi + byi を満たす整数 xi , yi
を順次計算する手続きが与えられている。この計算方法を拡張ユークリッドの互除法とい
う。より理論的に，次のように定理 1.14 を示すこともできる。I = {ax+by ∈ Z | x, y ∈ Z}
とおく。a = a · 1 + b · 0, b = a · 0 + b · 1 より a, b ∈ Z である。よって I ̸= ∅ であり，最小元
d = min I ∩ N がとれる。d = ax0 + by0 とする。勝手な m = ax + by ∈ I をとるとき，m を
d で割ったときの商を q, 余りを n とすると，もし m が d で割り切れなければ m = dq +n,
0 < n < d が成り立つが，このとき n = m − dq = a(x − dx0 ) + b(y − dy0 ) ∈ I ∩ N とな
り，d の最小性に矛盾する。よってすべての I の元は d で割り切れる。特に a, b ∈ I で
あったから，d は a, b の公約数となる。それゆえ a, b の最大公約数を g とすれば，d | g
である。一方，d = ax0 + by0 より，命題 1.3 から g | d でもある。よって d = g であり，
a と b の最大公約数は I に属する。
定理 1.16. 整数 a, b ∈ Z について (a, b) = 1 であることと方程式 ax + by = 1 が整数
解を持つことは同値である。
【証明】 (a, b) = 1 ならば定理 1.14 より ax + by = 1 は整数解をもつ。逆にある整数 x, y
について ax + by = 1 が成り立つとすれば，左辺は最大公約数 (a, b) の倍数なので，(a, b)
は 1 を割り切る。よって (a, b) = 1 となる。
命題 1.17. 整数 a, b, c ∈ Z について (a, c) = (b, c) = 1 と (ab, c) = 1 は同値である。
【証明】 (a, c) = (b, c) = 1 とすると，定理 1.16 より as + ct = 1, bu + cv = 1 を満たす s,
t, u, v ∈ Z が存在する。このとき
1 = (as + ct)(bu + cv) = absu + acsv + bctu + c2 tv = ab · su + c · (asv + btu + ctv)
が成り立つので，定理 1.16 より (ab, c) = 1 である。逆に (ab, c) = 1 とすれば，ふたたび
定理 1.16 より
abx + cy = 1
を満たす整数 x, y がとれる。このとき定理 1.16 より (a, c) = (b, c) = 1 となる。
系 1.18. 整数 a および m1 , . . . , mk について，(a, mi ) = 1 (1 ≤ i ≤ k) であることと
(a, m1 m2 · · · mk ) = 1 は同値である。
【証明】 命題 1.17 を繰り返し用いればよい。
7
命題 1.19. 整数 a, b ∈ Z について，方程式 ax + by = c が整数解を持つための必要
十分条件は (a, b) | c である。
【証明】 g = (a, b) とおく。
(⇒) 整数 c が c = ax + by と表せたとすると，命題 1.3 より c は g の倍数となる。
(⇐) g | c とすると，c = gk, k ∈ Z, と表せる。定理 1.14 より g = ax0 + by0 となる
x0 , y0 ∈ Z がとれる。この両辺を k 倍して c = gk = akx0 + bky0 を得る。よって方程式
ax + by = c は整数解を持つ。
注釈 1.20. 整数 a, b についての方程式 ax + by = c の整数解は以下のようにしてすべて
求められる。g = (a, b) とおくと，g̸ | c ならば ax + by = c は解を持たないので，c = c′ g
と表せる場合のみ考えればよい。a = a′ g, b = b′ g と表し，ax + by = c の両辺を g で
割れば a′ x + b′ y = c′ が得られる。命題 1.12 より (a′ , b′ ) = 1 であるから，はじめから
ax + by = c の両辺を (a, b) で割っておくことで (a, b) = 1 としてよい。以下，(a, b) = 1
の場合に ax + by = c の解法を与える。定理 1.14 より ax0 + by0 = 1 を満たす x0 , y0 ∈ Z
がとれる。この式を c 倍し，ax + by = c との差をとることで次を得る。
a(x − cx0 ) + b(y − cy0 ) = 0
変形して a(x − cx0 ) = b(cy0 − y) を考えると，左辺は a の倍数であるから右辺は a で
割り切れる。仮定から (a, b) = 1 なので，命題 1.11 より a | cy0 − y が成り立つ。よって
k ∈ Z を用いて cy0 − y = ak と表せる。このとき a(x − cx0 ) = b(cy0 − y) = abk より
x − cx0 = bk である。以上から x = bk + cx0 , y = −ak + cy0 (k ∈ Z) が一般解となる。
ここまで二つの整数の約数・倍数を考えてきたが，三つ以上の場合も同様に考えること
ができる。
定義 1.21. 0 でない整数 a1 , . . . , ak に対し，その公約数および公倍数を以下で定める。
d : a1 , . . . , ak の公約数 ⇐⇒ 1 ≤ i ≤ k について d | ai
m : a1 , . . . , ak の公倍数 ⇐⇒ 1 ≤ i ≤ k について ai | m
a1 , . . . , ak の公約数のうち，最大のものを a1 , . . . , ak の最大公約数といい，これを記号で
gcd(a1 , . . . , ak ) と表す。また a1 , . . . , ak の正の公倍数のうち，最小のものを a1 , . . . , ak
の最小公倍数といい，これを記号で lcm(a1 , . . . , ak ) と表す。gcd(a1 , . . . , ak ) = 1 が成
り立つとき，k 個の整数 a1 , . . . , ak は互いに素という。
注釈 1.22. k 個の整数 a1 , . . . , ak が互いに素であっても，その k − 1 個以下の整数が互い
に素とは限らない。例えば，gcd(6, 10, 15) = 1 であるが，gcd(6, 10) = 2, gcd(6, 15) = 3,
gcd(10, 15) = 5 である。
三つ以上の整数の最大公約数・最小公倍数の計算は二つの場合に帰着できる。
8
命題 1.23. 0 でない整数 a1 , . . . , ak (k ≥ 2) について以下が成り立つ。
(1) d | ai (1 ≤ i ≤ k) =⇒ d | gcd(a1 , . . . , ak )
(2) gcd(a1 , . . . , ak ) = gcd(gcd(a1 , . . . , ak−1 ), ak )
(3) ai | m (1 ≤ i ≤ k) =⇒ lcm(a1 , . . . , ak ) | m
(4) lcm(a1 , . . . , ak ) = lcm(lcm(a1 , . . . , ak−1 ), ak )
【証明】 k = 2 の場合，(1), (3) は命題 1.8 で示したことである。(1), (2) と (3), (4) を k
に関する帰納法で同時に証明する。
(1),(2): k ≥ 3 として k − 1 個の整数に対して主張は正しいものとする。d を a1 , . . . , ak の
公約数とすると，d は a1 , . . . , ak−1 の公約数でもあるから，帰納法の仮定より
d | gcd(a1 , . . . , ak−1 )
が成り立つ。よって命題 1.8 (2) より
d | gcd(gcd(a1 , . . . , ak−1 ), ak )
(1.2)
が成り立つ。特に d = gcd(a1 , . . . , ak ) として
gcd(a1 , . . . , ak ) | gcd(gcd(a1 , . . . , ak−1 ), ak )
が成り立つ。約数の大きさを考えることで
gcd(a1 , . . . , ak ) ≤ gcd(gcd(a1 , . . . , ak−1 ), ak )
(1.3)
である。一方，命題 1.2 (4) より gcd(gcd(a1 , . . . , ak−1 ), ak ) は a1 , . . . , ak の公約数である
から，最大性より
gcd(gcd(a1 , . . . , ak−1 ), ak ) ≤ gcd(a1 , . . . , ak )
(1.4)
が成り立つ。よって (1.3), (1.4) から
gcd(a1 , . . . , ak ) ≤ gcd(gcd(a1 , . . . , ak−1 ), ak ) ≤ gcd(a1 , . . . , ak )
となり，これより gcd(a1 , . . . , ak ) = gcd(gcd(a1 , . . . , ak−1 ), ak ) が従う。このとき (1.2) よ
り a1 , . . . , ak の公約数 d について
d | gcd(a1 , . . . , ak ) = gcd(gcd(a1 , . . . , ak−1 ), ak )
が成り立つ。よって k 個の整数についても主張は成り立つので，数学的帰納法よりすべ
ての k ≥ 2 について成り立つ。
(3), (4): k ≥ 3 として k − 1 個の整数に対して主張は正しいものとする。m を a1 , . . . , ak
の公倍数とすると，m は a1 , . . . , ak−1 の公倍数でもあるから，帰納法の仮定より
lcm(a1 , . . . , ak−1 ) | m
が成り立つ。よって命題 1.8 (1) より
lcm(lcm(a1 , . . . , ak−1 ), ak ) | m
9
(1.5)
が成り立つ。特に m = lcm(a1 , . . . , ak ) として
lcm(lcm(a1 , . . . , ak−1 ), ak ) | lcm(a1 , . . . , ak )
が成り立つ。約数の大きさを考えることで
lcm(lcm(a1 , . . . , ak−1 ), ak ) ≤ lcm(a1 , . . . , ak )
(1.6)
である。一方，命題 1.2 (4) より lcm(lcm(a1 , . . . , ak−1 ), ak ) は a1 , . . . , ak の公倍数である
から，最小性より
lcm(a1 , . . . , ak ) ≤ lcm(lcm(a1 , . . . , ak−1 ), ak )
(1.7)
が成り立つ。よって (1.6), (1.7) から
lcm(a1 , . . . , ak ) ≤ lcm(lcm(a1 , . . . , ak−1 ), ak ) ≤ lcm(a1 , . . . , ak )
となり，これより lcm(a1 , . . . , ak ) = lcm(lcm(a1 , . . . , ak−1 ), ak ) が従う。このとき (1.5) よ
り a1 , . . . , ak の公倍数 m について
lcm(lcm(a1 , . . . , ak−1 ), ak ) = lcm(a1 , . . . , ak ) | m
が成り立つ。よって主張は k 個の整数についても成り立つので，数学的帰納法よりすべ
ての k ≥ 2 について成り立つ。
注釈 1.24. 命題 1.9 は三つ以上の整数に対しては成立しない。実際，gcd(6, 10, 15) = 1,
lcm(6, 10, 15) = 30 であるが，6 · 10 · 15 = 900 となってしまう。
定理 1.25. 0 でない整数 a1 , . . . , ak (k ≥ 2) について
a1 x1 + · · · + ak xk = gcd(a1 , . . . , ak )
を満たす整数 x1 , . . . , xk が存在する。
【証明】 k に関する帰納法で証明する。k = 2 の場合は定理 1.14 で示したので，k ≥ 3 と
して k − 1 個の整数について主張が成り立つものとする。すなわち
a1 y1 + a2 y2 + · · · + ak−1 yk−1 = gcd(a1 , . . . , ak−1 )
(1.8)
を満たす整数 y1 , . . . , yk−1 が存在するものとする。定理 1.14 と 命題 1.23 (2) から
gcd(a1 , . . . , ak−1 )z + ak xk = gcd(gcd(a1 , . . . , ak−1 ), ak ) = gcd(a1 , . . . , ak )
(1.9)
を満たす整数 z, xk が存在する。(1.8) を (1.9) に代入することで
a1 y1 z + a2 y2 z + · · · ak−1 yk−1 z + ak xk = gcd(a1 , . . . , ak )
が成り立つ。よって x1 = y1 z, . . . , xk−1 = yk−1 z とすれば k 個の整数についても主張が成
り立つ。
10
素数
2
定義 2.1. (1) 2 以上の整数 p が素数であるとは，p の約数は ±1 および ±p に限る
ことと定める。この条件を式で表せば以下のとおりである。
(∀a ∈ Z)(a | p =⇒ a = ±1 or a = ±p)
(2) 素数でない 2 以上の整数 m を合成数という。これは次の条件と同値である。
∃a, b ∈ Z s.t. 1 < a, b < m and m = ab
合成数 m に対して，このような約数 a, b を m の真の約数という。
定義から 1 は素数でも合成数でもないことに注意しよう。
補題 2.2. p を素数とするとき，任意の整数 a について (a, p) = 1 もしくは (a, p) = p
である。
【証明】 g = (a, p) とすると，g | p より素数の定義から g = 1 もしくは g = p となる。
命題 2.3. 素数 p が m1 · · · mk を割り切るならば，ある mi について p | mi である。
【証明】 まず k = 2 の場合を示す。p | m1 m2 とする。素数の定義から (p, m1 ) = 1 もしく
は (p, m1 ) = p のいずれかが成り立つ。後者の場合，m1 は p で割り切れるので，主張は
成り立つ。前者の場合，命題 1.11 から p | m2 が成り立ち，やはり主張は成り立つ。次に
k > 2 の場合を考える。p | m1 m2 · · · mk とすると，m1 m2 · · · mk = m1 · (m2 · · · mk ) とみ
ることで p | m1 もしくは p | m2 · · · mk が成り立つ。後者について数学的帰納法を適用す
ればある mi について p | mi となる。よってすべての k ≥ 2 について主張が成り立つ。
定理 2.4. 2 以上の整数は素数の積に一意的に分解できる。
【証明】 まず 2 以上の整数 a について，a が素数の積に分解できることを a に関する帰
納法で示す。2 は素数なので，a = 2 の場合は主張は成り立つ。2 以上 a 未満の整数につ
いて主張が成り立つとする。もし a が素数であれば主張は成り立っている。もし a が合
成数であれば a = bc, 1 < b, c < a と表せる。帰納法の仮定から b, c はそれぞれ素数の積
に分解する。よって a = bc も素数の積に分解する。以上から 2 以上の整数は素数の積に
分解できることが示せた。
次に分解の一意性を示す。a を 2 以上の整数として，その素因数分解 a = p1 p2 · · · pn に
おける素数の個数 n に関する帰納法により分解の一意性を示す。n = 1 の場合は明らか
であるから，n > 1 として
a = p1 p2 · · · pn = q1 q2 · · · qm
(2.1)
と二通りの素数への分解があったとする。このとき m = n であり，適当に並べ替えるこ
とにより pi = qi (1 ≤ i ≤ n) となることを示す。p1 | a より p1 | q1 · · · qm であるから，命
題 2.3 より p1 | qi となる qi がある。必要ならば番号をつけかえて，p1 | q1 としてよい。q1
11
は素数でありその正の約数は 1 と q1 のみである。p1 は 1 より大きいので p1 = q1 とな
る。よって (2.2) の辺々を p1 で割って
p2 · · · pn = q2 · · · qm
(2.2)
を得る。この左辺は n − 1 個の素数の積で表せるので，帰納法の仮定からその素因数分解
は一意的である。よって m = n で，適当に並べ替えることにより pi = qi (1 ≤ i ≤ n) と
なる。以上から素因数分解の一意性も証明できた。
系 2.5. p1 , . . . , pk を相異なる素数とする。整数 n が n = pe11 · · · pekk と素因数分解さ
れるならば，n の約数は ±pf11 · · · pfkk , 0 ≤ fi ≤ ei で尽くされる。
【証明】 a を n の約数とし，n = ab と分解したとする。a, b の素因数分解から n の素因
数分解が得られるが，定理 2.4 より素因数分解の一意性が成り立つので，a の素因素因数
の可能性は主張にあるものに限られる。
系 2.6. 正の整数 n が n = pe11 · · · pekk と素因数分解するとき，n のすべての正の約数
の和は次で与えられる。
(1 + p1 + · · · +
pe11 )(1
+ p2 + · · · +
pe22 ) · · · (1
+ pk + · · · +
pekk )
=
k
∏
pei +1 − 1
i
i=1
pi − 1
【証明】 実際に展開してみればよい。
命題 2.7. a, b ∈ Z の素因数分解を
a = pe11 · · · pekk ,
b = pf11 · · · pfkk ,
ei , f i ≥ 0
とするとき，a, b の最大公約数および最小公倍数は次で与えられる。
min(e1 ,f1 )
gcd(a, b) = p1
min(ek ,fk )
· · · pk
max(e1 ,f1 )
,
lcm(a, b) = p1
max(ek ,fk )
· · · pk
【証明】 整除関係 gcd(a, b) | a, gcd(a, b) | b および a | lcm(a, b), b | lcm(a, b) に系 2.5 を適用
すれば gcd(a, b) および lcm(a, b) の素因数分解が主張の通りに定まる。
定理 2.8. 素数は無限個存在する。
【証明】 色々な証明方法が知られているが，ここでは最も基本的な証明を与える。素数が
有限個だったとし，p1 , . . . , pn を相異なるすべての素数とする。N = p1 · · · pn + 1 とおく
と，定理 2.4 より N は素数の積に分解できるが，各 pi について N を pi で割ると 1 余る
ので，N は p1 , . . . , pn では割り切れず，有限個の素数 p1 , . . . , pn の積には分解できない。
これは矛盾である。よって相異なる素数の個数は有限にはなりえず，無限に存在する。
12
合同式
3
定義 3.1. n を 0 でない整数とする。a, b ∈ Z について，a − b が n で割り切れると
き，a と b は n を法として合同であるといい，これを式で次のように表す。
a ≡ b mod n ⇐⇒ n | a − b ⇐⇒ ∃k ∈ Z s.t. a − b = kn
以下，mod n で合同式を考えるときは n は正の整数であるとする。合同式の定義から
a ≡ 0 mod n は n | a と同値であることに注意する。
命題 3.2. 次が成り立つ。
(1) 任意の a ∈ Z について a ≡ a mod n
(2) a ≡ b mod n =⇒ b ≡ a mod n
(3) a ≡ b mod n かつ b ≡ c mod n =⇒ b ≡ a mod n
【証明】 (1): a − a = 0 = 0 · n より a ≡ a mod n が成り立つ。
(2): a ≡ b mod n とすると，ある k ∈ Z があって a − b = kn と書ける。このとき
b − a = −kn であるから，b ≡ a mod n が成り立つ。
(3): a ≡ b mod n, b ≡ c mod n とすると，ある k, ℓ ∈ Z があって a − b = kn, b − c = ℓn
と書ける 3 。このとき a − c = (a − b) + (b − c) = kn + ℓn = (k + ℓ)n となるので，a ≡ c
mod n が成り立つ。
命題 3.3. a ≡ c mod n, b ≡ d mod n であるとき，次が成り立つ。
(1) a ± b ≡ c ± d mod n
(2) ab ≡ cd mod n
(3) ak ≡ ck mod n (k = 1, 2, 3, . . . )
【証明】 a − c = kn, b − d = ℓn とする。
(1): (a ± b) − (c ± d) = (a − c) ± (b − d) = (k ± ℓ)n より a ± b ≡ c ± d mod n である。
(2): ab − cd = ab − cb + cb − cd = (a − c)b + c(b − d) = (bk + cℓ)n より ab ≡ cd mod n
である。
(3): (2) を繰り返し用いればよい。
補題 3.4. a ∈ Z を n で割った余りを r とすれば，a ≡ r mod n である。
【証明】 a を n で割った商を q, 余りを r とすれば，a = nq + r より a − r = nq なので
a ≡ r mod n である。
補題 3.5. 任意の a ∈ Z について a ≡ r mod n となる 0 ≤ r < n が唯一つ存在する。
【証明】 a を n で割った余りを r とすれば補題 3.4 より a ≡ r mod n, 0 ≤ r < n が
成り立つ。他に a ≡ r′ mod n となる 0 ≤ r′ < n があったとすると，命題 3.3 (1) よ
り r − r′ ≡ a − a = 0 mod n となるので，r − r′ は n で割り切れる。0 ≤ r′ < n か
3
同じ k を用いて a − b = kn, b − c = kn となるとは限らないことに注意。
13
ら −n < −r′ ≤ 0 であり，これと 0 ≤ r < n を合わせると −n < r − r′ < n が成り立
つ。r − r′ は n の倍数であるから，r − r′ = nk とかける。このとき −n < nk < n より
−1 < k < 1 であるから，k = 0 でなければならない。よって r − r′ = nk = n · 0 = 0 で
あり，r = r′ となる。以上から a ≡ r mod n となる 0 ≤ r < n は唯一つである。
定義 3.6. 正整数 n を一つ固定する。a ∈ Z を n で割った余りを a と表し，
}
{ } {
Z/nZ := a a ∈ Z = 0, 1, . . . , n − 1
とおく。Z/nZ に和・差・積を
a ± b := a ± b,
a · b := a · b
で定める。Z/nZ を n を法とした剰余環という。
注釈 3.7. 命題 3.2 (3) と補題 3.4 より a = b ⇐⇒ a ≡ b mod n である。また，n を法
としていることを明記したい場合には a = [a]n とも書く。
剰余環 Z/nZ では整数の集合 Z と同様に和・差・積が行える。では商 (割り算) につい
てはどうであろうか。そのためにはまず Z/nZ における逆数を調べる必要がある。
命題 3.8. Z/nZ において ax = b が解をもつ ⇐⇒ (a, n) | b
【証明】 【証明】 Z/nZ において ax = b が解を持つ ⇐⇒ b − ax = 0 ⇐⇒ n | b − ax
⇐⇒ ある y ∈ Z が存在して b − ax = ny となる ⇐⇒ ax + ny = b が整数解を持つ ⇐⇒
(a, n) | b (命題 1.19)。よって主張の同値性が示された。
命題 3.9. Z/nZ において ax = 1 が解を持つための必要十分条件は (a, n) = 1 であ
る。またこのとき解 x は Z/nZ において一意に定まる。
【証明】 命題 3.8 より ax = 1 が解を持つことと (a, n) = 1 は同値である。一意性につい
ては ax = ax′ = 1 となったとすると，ax = 1 の両辺に x′ をかけて axx′ = x′ となるが，
この左辺は axx′ = ax′ · x = ax′ · x = 1 · x = x であるから，x = x′ を得る。よって Z/nZ
において 解は存在すれば一意である。
定義 3.10. a ∈ Z/nZ が可逆元 ⇐⇒ ある x ∈ Z/nZ が存在して ax = 1
可逆元のことを単数ともいう。次の系は命題 3.9 の言い換えである。
系 3.11. a が Z/nZ における可逆元 ⇐⇒ (a, n) = 1
14
定義 3.12. a ∈ Z/nZ が可逆元であるとき，ax = 1 を満たす x ∈ Z/nZ を a の (積
−1
に関する) 逆元といい，x = a
と表す。また，Z/nZ における可逆元全体の集合を
×
(Z/nZ) と書き，これを Z/nZ の単数群という。
(Z/nZ)× = {a ∈ Z/nZ | (a, n) = 1}
a を Z/nZ における可逆元とするとき，命題 3.8 の証明から逆元 a
式 ax + ny = 1 を解くことで得られることが分かる。
−1
は一次不定方程
補題 3.13. (a, n) = 1 のとき，Z/nZ における a の逆元 a
−1
一つとるとき，a = x として得られる。
−1
は ax + ny = 1 の解を
【証明】 ax + ny = 1 とすると，両辺を法 n で考えることにより ax + ny = 1 となるが，
−1
ax + ny = ax + n · y = ax + 0 · y = ax であるから，ax = 1 が成り立つ。よって x = a
である。
命題 3.14. a, b ∈ (Z/nZ)× について，以下が成り立つ。
( −1 )−1
−1
(1) a ∈ (Z/nZ)×
(2) a
=a
(3) ab ∈ (Z/nZ)×
−1
×
(4) ab
−1
=a
−1
·b
−1
−1
【証明】 (1), (2): a ∈ (Z/nZ) より a · a
= 1 が成り立つ。よって a も可逆元であ
り，その逆元は a である。
−1
−1
−1
−1
(3), (4): ab · a · b = a · a · b · b = 1 · 1 = 1 より ab も可逆元であり，その逆元は
−1
−1
a · b である。
命題 3.15. (a, n) = 1 のとき ab ≡ ac mod n =⇒ b ≡ c mod n
【証明】 注釈 3.7 にあるように，合同式 ab ≡ ac mod n は剰余環 Z/nZ において ab = ac
−1
と同値である。(a, n) = 1 より系 3.11 から a ∈ (Z/nZ)× なので，ab = ac の両辺に a
をかけることで b = c が得られる。これを合同式で表せば b ≡ c mod n となる。
定理 3.16. (m, n) = 1 のとき連立合同方程式
x≡a
mod m
x ≡ b mod n
は mn を法として唯一つの解を持つ。
【証明】 (m, n) = 1 より定理 1.16 から mu + nv = 1 となる u, v ∈ Z が存在する。この
とき 1 − nv = mu ≡ 0 mod m, 1 − mu = nv ≡ 0 mod n より
1 ≡ nv mod m
1 ≡ mu mod n
15
が成り立つ。ここで x = anv + bmu とおけば
x = anv + bmu ≡ anv ≡ a · 1 = a mod m
x = anv + bmu ≡ bmu ≡ b · 1 = b mod n
となるので，x は与えられた連立合同方程式の解である。もし他に解 y があったとする。
すなわち
{
{
x ≡ a mod m
y ≡ a mod m
x ≡ b mod n
y ≡ b mod n
が成り立つとする。このとき x ≡ y mod m, x ≡ y mod n より合同式の定義から x − y
は m および n で割り切れるので，命題 1.8 (2) より x − y は m と n の最小公倍数で割
り切れる。仮定より (m, n) = 1 であったから，命題 1.9 より m と n の最小公倍数は mn
である。よって x − y は mn で割り切れるので，x ≡ y mod mn が成り立つ。これより
与えられた連立方程式の整数解は mn を法として一意的である。
系 3.17. m1 , . . . , mk をどの二つも互いに素な正整数とするとき，連立合同方程式
x ≡ a1
..
.
mod m1
..
.
x ≡ ak
mod mk
は m1 · · · mk を法として唯一つの解を持つ。
【証明】 方程式の個数 k に関する帰納法で証明する。k = 2 の場合は定理 3.16 で示した。
k − 1 個の場合に主張が成り立つとすると，以下を満たす整数 b が存在する。
b ≡ a1
..
.
mod m1
..
.
b ≡ ak−1 mod mk−1
仮定より m1 , . . . , mk はどの二つも互いに素だから系 1.18 より (m1 . . . mk−1 , mk ) = 1 で
ある。よって定理 3.16 より
x ≡ b mod m1 · · · mk−1
x ≡ ak mod mk
を満たす整数 x が存在する。このとき x − b は m1 · · · mk−1 で割り切れるので，特に
1 ≤ i ≤ k − 1 について x − b ≡ 0 mod mi が成り立つ。b ≡ ai mod mi であるから，
x ≡ b ≡ ai mod mi (1 ≤ i ≤ k − 1) が成り立つ。よって x は与えられた k 個の連立合
同方程式の解である。一意性については他に解 y があったとすれば，x ≡ y mod mi が
1 ≤ i ≤ k について成り立つので，x − y は mi で割り切れる。よって x − y は m1 , . . . , mk
の最小公倍数で割り切れる。m1 , . . . , mk はどの二つも互いに素であったから，命題 1.9
と命題 1.23 (4) を繰り返し使うことによりその最小公倍数は m1 · · · mk である。よって
x ≡ y mod m1 · · · mk が成り立つ。これより与えられた連立方程式は m1 · · · mk を法と
して唯一つの整数解を持つ。
16
オイラー関数
4
定義 4.1. 2 以上の整数 n に対し Z/nZ における可逆元の個数を φ(n) と表し，これ
をオイラーの φ 関数という。有限集合 A の元の個数を |A| と表すとき，φ(n) は次の
ように定められる。
φ(n) = (Z/nZ)× = |{a ∈ Z | 1 ≤ a ≤ n, (a, n) = 1}|
また，n = 1 に対しては φ(1) = 1 と定める。
以下，φ(n) を求める公式を導出する。
命題 4.2. (m, n) = 1 =⇒ φ(mn) = φ(m)φ(n)
【証明】 1 ≤ x ≤ mn に対し組 ([x]m , [x]n ) を対応させ，以下の写像を考える。
f : Z/mnZ −→ (Z/mZ) × (Z/nZ)
[x]mn 7−→
([x]m , [x]n )
x ≡ y mod mn とすれば x − y は mn で割り切れるので，x − y は m でも n でも割り
切れる。よって x ≡ y mod m かつ x ≡ y mod n となるので，この写像は well-defined
である。勝手な 1 ≤ a ≤ m と 1 ≤ b ≤ n に対して定理 3.16 より x ≡ a mod m かつ
x ≡ b mod n となる x が mn を法として唯一つ存在するので，この写像は全射である。
また，f ([x]mn ) = f ([y]mn ) となったとすれば x ≡ y mod m かつ x ≡ y mod n となり，
x − y は m と n の両方で割り切れる。よって命題 1.8 (1) より x − y は m, n の最小公
倍数で割り切れる。仮定より (m, n) = 1 であったから，命題 1.9 より m, n の最小公倍
数は mn である。よって x − y は mn で割り切れ，x ≡ y mod mn が成り立つ。これは
Z/mnZ において [x]mn = [y]mn を意味するので，f は単射でもある。ここで命題 1.17 よ
り (x, mn) = 1 と (x, m) = (x, n) = 1 は同値であるから，[x]mn が Z/mnZ の可逆元であ
ることと，[x]m が Z/mZ の可逆元かつ [x]n が Z/nZ の可逆元であることは同値である。
これより f は Z/mZ の可逆元と Z/nZ の可逆元の組と Z/mnZ の可逆元との間の一対
一対応を与える。前者は φ(m)φ(n) 個の組があり，後者は φ(mn) 個あるので，求める等
式 φ(mn) = φ(m)φ(n) を得る。
命題 4.3. φ(p ) = p − p
e
e
e−1
【証明】素因数分解を考えることで (i, p ) = 1 は (i, p) = 1 と同値である。よって 1 ≤ i ≤ p
のうち p と互いに素なものの個数が φ(pe ) を与える。1 ≤ i ≤ pe のうち p の倍数は
e
e
p, 2p, 3p, 4p, . . . , pe = pe−1 · p
であり，このような整数は kp (1 ≤ k ≤ pe−1 ) という形で pe−1 個ある。よって 1 ≤ i ≤ pe
のうち残りのものが p と互いに素になるので，φ(pe ) = pe − pe−1 である。
17
定理 4.4. n =
pe11
· · · pekk
と素因数分解するならば，
φ(n) =
k
∏
(pei i
−
pei i −1 )
i=1
)
∏ (
1
1−
=n
p
p|n
p:素数
が成り立つ。
【証明】 命題 4.2 と命題 4.3 から
φ(n) = φ(pe11 ) · · · φ(pekk ) = (pe11 − p1e1 −1 ) · · · (pekk − pekk −1 )
である。ここで上の式の各因子を
(pei i
−
pei i −1 )
=
pei i
(
)
1
1−
pi
と変形すれば
φ(n) =
pe11
· · · pekk
(
) (
)
)
∏ (
1
1
1
· 1−
··· 1 −
=n
1−
p1
pk
p
p|n
p:素数
が得られる。
18
フェルマーの小定理
5
定義 5.1. 複素数 a と非負整数 i に対して二項係数を以下で定める。
( )
a
a · (a − 1) · (a − 2) · · · (a − i + 1)
:=
i
i!
注釈 5.2. 整数 n と |x| > |y| なる複素数 x, y について
∞ ( )
∑
n n−i i
n
(x + y) =
x y
i
i=0
( )
n
が成り立つ。n が非負整数ならば n ≥ i のとき
= n Ci ∈ Z であり，0 ≤ n < i のとき
i
( )
n
= 0 であるから，上の和は 0 ≤ i ≤ n の範囲に収まり，通常の二項定理と一致する。
i
( )
p
補題 5.3. p を素数とするとき，1 ≤ i ≤ p − 1 について
≡ 0 mod p が成り立つ。
i
【証明】 1 ≤ i ≤ p − 1 のとき i! = 1 × 2 × · · · × i は p で割り切れない。よって
( )
p
p · (p − 1) · · · (p − i + 1)
=
i
i!
( )
p
において分子の p は約分されないので，
≡ 0 mod p が成り立つ。
i
命題 5.4. (a ± b)p ≡ ap ± bp mod p
( )
p
【証明】 補題 5.3 より 1 ≤ i ≤ p − 1 のとき
≡ 0 mod p なので
i
( )
( )
(
)
( )
p p
p p−1
p
p 0
0
1
1
p−1
p
(a ± b) =
a (±b) +
a (±b) + · · · +
a (±b)
+
a (±b)p
0
i
p−1
p
≡ ap + (±1)p bp
mod p
が成り立つ。p > 2 の場合，p は奇数であるから，(−1)p = −1 より (a ± b)p ≡ ap ± bp
mod p である。p = 2 の場合，−1 ≡ 1 mod 2 であるから，この場合も (a ± b)p ≡ ap ± bp
mod p は成り立つ。
定理 5.5. p を素数とするとき，任意の整数 a について a ≡ a mod p が成り立つ。
特に (a, p) = 1 ならば ap−1 ≡ 1 mod p が成り立つ。
p
【証明】 まず非負整数 a について a ≡ a mod p を証明する。a = 0 のときは成り立つ。
ap ≡ a mod p が成り立つとすると，補題 5.3 より
( )
( )
p ( )
∑
p p−i i
p p 0
p 0 p
p
(a + 1) =
a ·1 ≡
a ·1 +
a · 1 = ap + 1 ≡ a + 1 mod p
i
0
p
i=0
p
19
となり，(a + 1)p ≡ a + 1 mod p も成り立つ。よって数学的帰納法よりすべての非負整数
に対して ap ≡ a mod p が成り立つ。次に a を正整数として (−a)p を考える。p > 2 の
ときは p は奇素数であるから (−1)p = −1 である。よってこのときは (−a)p = (−1)p ap =
−ap ≡ −a mod p である。p = 2 のときは −1 ≡ 1 mod 2 より −a ≡ a mod 2 なので
(−a)p ≡ ap ≡ a ≡ −a mod p となり，やはり成り立つ。よってすべての整数 a につい
て ap ≡ a mod p が成り立つ。(a, p) = 1 であるとき a は Z/pZ において可逆元なので，
−1
ap = a の両辺に逆元 a
をかけて ap−1 = 1 を得る。これを合同式で表せば ap−1 ≡ 1
mod p となる。
定理 5.5 は一般の n に対して次のように拡張できる。
定理 5.6. (a, n) = 1 =⇒ aφ(n) ≡ 1 mod n
【証明】 (a, n) = 1 とすると，Z/nZ において a は可逆元を与える。可逆元の集合を
{
}
(Z/nZ)× = x1 , . . . , xφ(n) とするとき，命題 3.14 (3) より axi もまた (Z/nZ)× に属す
る。ここで axi = axj とすると，両辺に a
xi = a
−1
−1
をかけることで
· axi = a
−1
· axj = xj
より xi = xj となる。よって 1 ≤ i ≤ φ(n) について axi はすべて相異なる。これより
{
} {
}
(Z/nZ)× = x1 , . . . , xφ(n) = ax1 , . . . , axφ(n)
が成り立つ。よって Z/nZ の可逆元すべての積として次の等式が成り立つ。
∏
φ(n)
i=1
ふたたび命題 3.14 (3) より
φ(n)
∏
∏
φ(n)
xi =
∏
φ(n)
axi = a
φ(n)
i=1
xi
i=1
xi ∈ (Z/nZ)× となるので，上の式の両辺に
i=1
( φ(n)
∏
xi
)−1
i=1
をかければ
a
φ(n)
=1
が得られる。これを合同式でかけば aφ(n) ≡ 1 mod n となる。
系 5.7. (a, n) = 1 のとき一次方程式 ax ≡ b mod n の解は x ≡ aφ(n)−1 b mod n で
与えられる。
φ(n)
【証明】 定理 5.6 より (a, n) = 1 のとき a
=a·a
φ(n)−1
≡ 1 mod n であるから，
ax ≡ b mod n
の両辺に aφ(n)−1 をかけることで x ≡ aφ(n)−1 b mod n となる。
20
RSA 暗号
6
RSA 暗号 4 では次の命題を用いる。
定理 6.1. p, q を相異なる素数として，n = pq と正整数 t について以下が成り立つ。
(1) t ≡ 1 mod p − 1, t ≡ 1 mod q − 1 =⇒ ∀a ∈ Z at ≡ a mod n
(2) t ≡ 1 mod φ(n) =⇒ ∀a ∈ Z at ≡ a mod n
【証明】 (1): p | a のとき a − a = a(a − 1) は p で割り切れるので a ≡ a mod p であ
る。(a, p) = 1 のときは定理 5.5 より ap−1 ≡ 1 mod p となる。仮定から t = (p − 1)k + 1
と表せるので，
at = a(p−1)k+1 = (ap−1 )k · a ≡ 1k · a = a mod p
t
t−1
t
が成り立つ。よっていずれの場合も at ≡ a mod p が成り立つ。p と q を入れ替えて同
様に議論することで at ≡ a mod q も成り立つ。よって at − a は p および q で割り切れ
る。p, q は相異なる素数だから at − a は n = pq で割り切れる。よって at ≡ a mod n が
成り立つ。
(2): 定理 4.4 より φ(n) = φ(pq) = φ(p)φ(q) = (p − 1)(q − 1) であるから，t ≡ 1
mod φ(n) ならば t − 1 は p − 1 および q − 1 で割り切れるので t ≡ 1 mod p − 1 および
t ≡ 1 mod q − 1 が成り立つ。よって (1) より任意の整数 a について at ≡ a mod n が
成り立つ。
鍵生成
RSA 暗号について解説しよう。以下の要領で自然数 n, e, d を用意する。
1◦ 相異なる二つの素数 p, q を用意し n = pq とおく。このとき φ(n) = (p − 1)(q − 1)
である。
2◦ φ(n) と互いに素な e を 1 < e < φ(n) の範囲で一つとる。
3◦ 上の e に対し ed ≡ 1 mod φ(n) を満たす d を 1 < d < φ(n) の範囲で求める。
このように選んだ n, e を暗号化鍵もしくは公開鍵，d を復号化鍵もしくは秘密鍵という。
RSA 暗号では暗号化鍵である n および e は他人に公開してしまう。一方，復号化鍵 d は
秘密にしておかなければならない。
暗号化 送信を行う文を n を法として x < n を満たす自然数で表現する。この数 x を
ひらぶん
平文という。
平文 x に対し y ≡ xe mod n を計算し，0 ≤ y < n を満たすようとった y を暗号
文とする。
4
R.L. Rivest, A. Shamir, L. Adleman の三人が提唱した暗号形式。
21
復号化
受け取った暗号文を以下の手順で解読する。
暗号文 y に対して z ≡ y d mod n を計算し，0 ≤ z < n を満たすように z をとる。
このとき次が成り立つ。
定理 6.2. (RSA 暗号)
x=z
【証明】作り方から z ≡ y d ≡ (xe )d ≡ xed mod n であるが，ed ≡ 1 mod φ(n) なので
t = ed, a = x として定理 6.1 を用いると xed ≡ x mod n が成り立つ。よって z ≡ x
mod n である。取り方から 0 ≤ x, z < n より z = x となる。
何故暗号になるのか？
RSA 暗号が暗号として機能する理由は次の計算量の非対称性による。
(
)
(
)
p と q から n = pq
n を所与としてその素因数分解
1.
≪
を求める計算量
n = pq を求める計算量
(
)
(
)
x mod n から xe mod n
e を所与として xe mod n から
2.
≪
を求める計算量
x を求める計算量
では，実際に具体例で計算してみよう。本来 RSA 暗号では n = pq を大きくとって平
文をまるごと暗号文に変換するが，以下の例では簡単のため一文字ずつ暗号化している。
例１：n = 34 = 2 × 17 この場合 φ(34) = φ(2 × 17) = (2 − 1)(17 − 1) = 16 である。
(e, 16) = 1 となる e として e = 3 の場合を考えよう。このとき 3u + 16v = 1 の整数解を
求めることで 3 · 11 ≡ 1 mod 16 となることが分かる。よってこの場合 d = 11 となる。
以上の準備のもとで文 MATH を暗号化してみよう。ここでは以下の対応表を用いることに
する。(ただし 34 = 0 とし，35 以上は無視する。)
01 02
A B
21 22
U V
03
C
23
W
04 05 06
D E F
24 25 26
X Y Z
07
G
27
0
08
H
28
1
09
I
29
2
10
J
30
3
11
K
31
4
12
L
32
5
13
M
33
6
14
N
34
7
15
O
35
8
16
P
36
9
17
Q
37
?
18
R
38
@
19
S
39
Y
=
20
T
n = 34, e = 3 として暗号化を行う。まず MATH を数字の列に直すと 13 01 20 08 となる。
それぞれの数字を暗号化すると
⇝ 13 7−→ 133 ≡ 21 mod 34
A ⇝ 01 7−→ 13 ≡ 1 mod 34
T ⇝ 20 7−→ 203 ≡ 10 mod 34
H ⇝ 08 7−→ 83 ≡ 2 mod 34
より MATH ⇝ 13 01 20 08 7−→ 21 01 10 02 が暗号文となる。これを復号してみると
21 7−→ 2111 ≡ 13 mod 34 ⇝ M
01 7−→ 111 ≡ 1 mod 34 ⇝ A
10 7−→ 1011 ≡ 20 mod 34 ⇝ T
02 7−→ 211 ≡ 8 mod 34 ⇝ H
M
となり，確かに元の平文である MATH が解読できる。
22
例２：n = 39 = 3 × 13 この場合 φ(39) = φ(3 × 13) = (3 − 1)(13 − 1) = 24 である。
(e, 24) = 1 となる e として e = 7 の場合を考えよう。この場合 7u + 24v = 1 の整数解を
求めることで 7 · 7 ≡ 1 mod 24 より d = 7 となる。この場合，暗号文 03 24 33 33 08 08
を解読してみよう。
03 7−→ 37 ≡ 3 mod 39
33 7−→ 337 ≡ 6 mod 39
⇝C
⇝F
24 7−→ 247 ≡ 15 mod 39
08 7−→ 87 ≡ 5 mod 39
⇝O
⇝E
より 03 24 33 33 08 08 7−→ 03 15 06 06 05 05 と解読でき，対応表から元の平文は COFFEE
であることが分かる。(ただし上の対応表において 39 = 0 とする。)
問題１：n = 38 = 2 × 19 この場合 φ(38) = φ(2 × 19) = (2 − 1)(19 − 1) = 18 である。
(e, 18) = 1 となる e として e = 11 を考える。このとき d = あ である。また，暗号
文 20 03 32 14 03 を解読すると元の平文は
38 = 0 とし，39 は無視する。)
い
である。(ここでは上の対応表において
問題２ 例２において公開鍵 e = 5 の場合に自分の学籍番号 (英数合わせて 7 or 8 桁) を
上の対応表を用いて暗号化せよ。また e = 5 とした場合の復号化鍵 d を求め，暗号化し
た学籍番号を実際に復号せよ。
23
© Copyright 2024 ExpyDoc
