この記事は,
旧ブログから移植された記事です. よって, その内容として,
旧ブログに依存した文脈が含まれている可能性があります. 予めご了承下さい.
以前の記事, エルガマル暗号では, エルガマル暗号に関する諸々の前提の説明と, その実装について示した. 同エントリ内で, フェルマーの小定理については取り扱ったものの, その一般形であるオイラーの定理およびカーマイケルの定理について特に触れなかったため, 本エントリでそれらに関してまとめる. しばしば値の確認には, 簡単のため Haskell を使う.
オイラーの定理
いま, フェルマーテストを定義したとき, FTn(a) をパスするには (すなわち, フェルマーの小定理が示す合同式が成り立つには), 要件として, 既約剰余類郡 Zn∗ の各要素と ∃a ∈Z の積が全て異なり, modn の既約代表系のすべての積と合同でなければならない. たとえば, 法 n=8 による合同関係で構成する剰余類の完全代表系は 0,1,2,3,4,5,6,7 であるが, a=2 としてしまうと, 既約剰余類郡が構成できていないので, 次のようにしても完全代表系が得られない(積をわざわざ示していないが, 非合同でないことは, 各要素の積が全て異なっていない時点で明白である).
Prelude> [x * 2 `rem` 8 | x <- [0..7]]
[0,2,4,6,0,2,4,6]
そこで, 先に述べた剰余類の既約代表系を考える. これは ϕ(8)=4 個で, 1,3,5,7 である. これを同じように, {1⋅a, 3⋅a, 5⋅a, 7⋅a} とし, 先の要件を確認すると, この補題2より, mod8 で全体として {1,3,5,7} と一致していて, 1⋅3⋅5⋅7≡1⋅3⋅5⋅7⋅a4(mod8)(1) gcd(1⋅3⋅5⋅7,8)=1 だから, 1⋅3⋅5⋅7 を約して, a4≡1(mod8)(2) これは, gcd(a,n)=1 ということの他に, a および n の値に依存した論ではない. すなわち,
aϕ(n)≡1(modn) (2≤n∈Z+, gcd(a,n)=1)
がいえる.
*Main> euler'sTheorem n = [a `modExp` (totient n) $ n | a <- [2..], gcd a n == 1]
*Main> all (==1) $ take 100 $ euler'sTheorem 8
True
n が素数 p であるとき, ϕ(p)=p−1 で, フェルマーの小定理となる.
ラグランジュの定理
いま述べたオイラーの定理は, ラグランジュの定理を使っても証明できる. ラグランジュの定理は,
有限郡
G の部分郡
H の位数
∣H∣ は,
G の位数
∣G∣ の約数となる.
∣G∣ = ∣G:H∣∣H∣
である.
有限郡 G の部分郡 H による類別が G=i⋃raiH であるとき, ∣G∣=r∣H∣ といえる. この r は r=∣G:H∣ そのものなので, ∣G∣ = ∣G:H∣∣H∣.
ごく直感的な定理である. これを使えば, オイラーの定理は次のように証明できる.
有限郡 G とその元 ∀g∈G に対し, g∣G∣=e. e∈G は単位元.
巡回部分郡 H=<g> の元 g の位数 ∣H∣ は, 巡回して gi=e となる最小の i∈N であるといえる. すなわち g∣H∣=e ここで, 商集合の位数を両辺に次のように与える. (g∣H∣)∣G:H∣=(e)∣G:H∣ 左辺は指数法則により, また右辺は単位元の繰り返しだから, これを次のようにかける. g∣H∣∣G:H∣=e ラグランジュの定理より g∣G∣=e
オイラーの定理を仮定したとき, 脚注より剰余類 a は法 n に関する既約剰余類郡 Zn∗ に含まれる.
∣Zn∗∣=ϕ(n) だから補題 1 より aϕ(n)=aϕ(n)=1.
カーマイケルの定理
オイラーの定理で用いる ϕ 関数は, am≡1(modn) (m∈N,gcd(a,n)=1 を成立させる最小の整数 m を持ち得ない. たとえば, n=8 では, 先の通り確かに m=ϕ(8)=4 で合同式が満足できたが, m=2 としても, これを満足できる.
*Main> all (==1) $ take 100 $ [a `modExp` 2 $ 8 | a <- [2..], gcd a 8 == 1]
True
カーマイケルの λ 関数は, 与えられた整数 n に対して同合同式を満足する最小の m を定義より自明に与える.
扱う文字を全て整数とし,
λ(n) は
λ(1)λ(2)λ(4)λ(2k)λ(2k)λ(ph)λ(2kp1h1p2h2p3h3⋯ptht):=:=:=:=:=:=:=114ϕ(2k) (0≤k≤2)2k−2=2ϕ(2k) (e≥3)ϕ(ph)=(p−1)⋅ph−1 (p is an odd prime,h≥1)lcm(λ(2k),λ(p1h1),λ(p2h2),λ(p3h3),⋯,λ(ptht)) (pn is an odd prime,k≥0,hn≥1) と定義する.
aλ(n)≡1(modn) (2≤n∈Z+, gcd(a,n)=1)
実装して確かめてみる.
*Main> let carmichael'sLambda n = head [k | k <- [1..], and [(m `modExp` k $ n) < 2 | m <- [1..n] gcd m n < 2]]
*Main> let carmichael'sTheorem n = [a `modExp` (carmichael'sLambda n) $ n | a <- [2..], gcd a n == 1]
*Main> all (==1) $ take 100 $ carmichael'sTheorem 8
True