この記事は,
旧ブログ から移植された記事です. よって, その内容として,
旧ブログ に依存した文脈が含まれている可能性があります. 予めご了承下さい.
以前の記事, エルガマル暗号 では, エルガマル暗号に関する諸々の前提の説明と, その実装について示した. 同エントリ内で, フェルマーの小定理については取り扱ったものの, その一般形であるオイラーの定理およびカーマイケルの定理について特に触れなかった ため, 本エントリでそれらに関してまとめる. しばしば値の確認には, 簡単のため Haskell を使う.
オイラーの定理
いま, フェルマーテスト を定義したとき, F T n ( a ) FT_n(a) F T n ( a ) をパスするには (すなわち, フェルマーの小定理が示す合同式が成り立つには), 要件として, 既約剰余類郡 Z n ∗ \mathbb{Z}^{\ast}_n Z n ∗ の各要素と ∃ a ∈ Z ^\exists a\ \in\mathbb{Z} ∃ a ∈ Z の積が全て異なり, m o d n \bmod n mod n の既約代表系のすべての積と合同でなければならない. たとえば, 法 n = 8 n=8 n = 8 による合同関係で構成する剰余類の完全代表系は 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 0,1,2,3,4,5,6,7 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 であるが, a = 2 a=2 a = 2 としてしまうと, 既約剰余類郡が構成できていないので, 次のようにしても完全代表系が得られない(積をわざわざ示していないが, 非合同でないことは, 各要素の積が全て異なっていない時点で明白である).
Prelude > [x * 2 `rem` 8 | x <- [0 .. 7 ]]
[0 ,2 ,4 ,6 ,0 ,2 ,4 ,6 ]
そこで, 先に述べた剰余類の既約代表系を考える. これは ϕ ( 8 ) = 4 \phi(8)=4 ϕ ( 8 ) = 4 個で, 1 , 3 , 5 , 7 1,3,5,7 1 , 3 , 5 , 7 である. これを同じように, { 1 ⋅ a , 3 ⋅ a , 5 ⋅ a , 7 ⋅ a } \left\{1\cdot a,\ 3\cdot a,\ 5\cdot a,\ 7\cdot a\right\} { 1 ⋅ a , 3 ⋅ a , 5 ⋅ a , 7 ⋅ a } とし, 先の要件を確認すると, この補題2 より, m o d 8 \bmod 8 mod 8 で全体として { 1 , 3 , 5 , 7 } \left\{1,3,5,7\right\} { 1 , 3 , 5 , 7 } と一致していて, 1 ⋅ 3 ⋅ 5 ⋅ 7 ≡ 1 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ a 4 ( m o d 8 ) (1) 1\cdot 3\cdot 5\cdot 7\equiv 1\cdot 3\cdot 5\cdot 7\cdot a^4\pmod{8}\tag{1} 1 ⋅ 3 ⋅ 5 ⋅ 7 ≡ 1 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ a 4 ( mod 8 ) ( 1 ) gcd ( 1 ⋅ 3 ⋅ 5 ⋅ 7 , 8 ) = 1 \gcd(1\cdot 3\cdot 5\cdot 7,8)=1 g cd( 1 ⋅ 3 ⋅ 5 ⋅ 7 , 8 ) = 1 だから, 1 ⋅ 3 ⋅ 5 ⋅ 7 1\cdot 3\cdot 5\cdot 7 1 ⋅ 3 ⋅ 5 ⋅ 7 を約して, a 4 ≡ 1 ( m o d 8 ) (2) a^4\equiv 1\pmod{8}\tag{2} a 4 ≡ 1 ( mod 8 ) ( 2 ) これは, gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 ということの他に, a a a および n n n の値に依存した論ではない. すなわち,
a ϕ ( n ) ≡ 1 ( m o d n ) ( 2 ≤ n ∈ Z + , gcd ( a , n ) = 1 ) a^{\phi(n)}\equiv 1\pmod{n}\ (2\leq n\in\mathbb{Z}^{+},\ \gcd(a,n)=1) a ϕ ( n ) ≡ 1 ( mod n ) ( 2 ≤ n ∈ Z + , g cd( 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 n n が素数 p p p であるとき, ϕ ( p ) = p − 1 \phi(p)=p-1 ϕ ( p ) = p − 1 で, フェルマーの小定理となる.
ラグランジュの定理
いま述べたオイラーの定理 は, ラグランジュの定理を使っても証明できる. ラグランジュの定理は,
有限郡
G G G の部分郡
H H H の位数
∣ H ∣ \mid H\mid ∣ H ∣ は,
G G G の位数
∣ G ∣ \mid G\mid ∣ G ∣ の約数となる.
∣ G ∣ = ∣ G : H ∣ ∣ H ∣ \mid G\mid\ =\ \mid G:H\mid \mid H\mid ∣ G ∣ = ∣ G : H ∣∣ H ∣
である.
有限郡 G G G の部分郡 H H H による類別が G = ⋃ i r a i H \displaystyle G=\bigcup_i^r a_iH G = i ⋃ r a i H であるとき, ∣ G ∣ = r ∣ H ∣ \mid G\mid=r\mid H\mid ∣ G ∣= r ∣ H ∣ といえる. この r r r は r = ∣ G : H ∣ r=\mid G:H\mid r =∣ G : H ∣ そのものなので, ∣ G ∣ = ∣ G : H ∣ ∣ H ∣ \mid G\mid\ =\ \mid G:H\mid\mid H\mid ∣ G ∣ = ∣ G : H ∣∣ H ∣ .
ごく直感的な定理である. これを使えば, オイラーの定理 は次のように証明できる.
有限郡 G G G とその元 ∀ g ∈ G ^\forall g\in G ∀ g ∈ G に対し, g ∣ G ∣ = e g^{\mid G\mid}=e g ∣ G ∣ = e . e ∈ G e\in G e ∈ G は単位元.
巡回部分郡 H = < g > H=\lt g\gt H =< g > の元 g g g の位数 ∣ H ∣ \mid H\mid ∣ H ∣ は, 巡回して g i = e g^i=e g i = e となる最小の i ∈ N i\in\mathbb{N} i ∈ N であるといえる. すなわち g ∣ H ∣ = e g^{\mid H\mid}=e g ∣ H ∣ = e ここで, 商集合の位数を両辺に次のように与える. ( g ∣ H ∣ ) ∣ G : H ∣ = ( e ) ∣ G : H ∣ (g^{\mid H\mid})^{\mid G:H\mid}=(e)^{\mid G:H\mid} ( g ∣ H ∣ ) ∣ G : H ∣ = ( e ) ∣ G : H ∣ 左辺は指数法則により, また右辺は単位元の繰り返しだから, これを次のようにかける. g ∣ H ∣ ∣ G : H ∣ = e g^{\mid H\mid\mid G:H\mid}=e g ∣ H ∣∣ G : H ∣ = e ラグランジュの定理より g ∣ G ∣ = e g^{\mid G\mid}=e g ∣ G ∣ = e
オイラーの定理 を仮定したとき, 脚注より剰余類 a ‾ \overline{a} a は法 n n n に関する既約剰余類郡 Z n ∗ \mathbb{Z}^{\ast}_{n} Z n ∗ に含まれる.
∣ Z n ∗ ∣ = ϕ ( n ) \mid\mathbb{Z}^{\ast}_{n}\mid=\phi(n) ∣ Z n ∗ ∣= ϕ ( n ) だから補題 1 より a ‾ ϕ ( n ) = a ϕ ( n ) ‾ = 1 ‾ \overline{a}^{\phi(n)}=\overline{a^{\phi(n)}}=\overline{1} a ϕ ( n ) = a ϕ ( n ) = 1 .
カーマイケルの定理
オイラーの定理 で用いる ϕ \phi ϕ 関数は, a m ≡ 1 ( m o d n ) ( m ∈ N , gcd ( a , n ) = 1 a^{m}\equiv 1\pmod{n}\ (m\in{N}, \gcd(a,n)=1 a m ≡ 1 ( mod n ) ( m ∈ N , g cd( a , n ) = 1 を成立させる最小の整数 m m m を持ち得ない. たとえば, n = 8 n=8 n = 8 では, 先の通り確かに m = ϕ ( 8 ) = 4 m=\phi(8)=4 m = ϕ ( 8 ) = 4 で合同式が満足できたが, m = 2 m=2 m = 2 としても, これを満足できる.
* Main > all (== 1 ) $ take 100 $ [a `modExp` 2 $ 8 | a <- [2 .. ], gcd a 8 == 1 ]
True
カーマイケルの λ \lambda λ 関数は, 与えられた整数 n n n に対して同合同式を満足する最小の m m m を定義より自明に与える.
扱う文字を全て整数とし,
λ ( n ) \lambda(n) λ ( n ) は
λ ( 1 ) : = 1 λ ( 2 ) : = 1 λ ( 4 ) : = 4 λ ( 2 k ) : = ϕ ( 2 k ) ( 0 ≤ k ≤ 2 ) λ ( 2 k ) : = 2 k − 2 = ϕ ( 2 k ) 2 ( e ≥ 3 ) λ ( p h ) : = ϕ ( p h ) = ( p − 1 ) ⋅ p h − 1 ( p i s a n o d d p r i m e , h ≥ 1 ) λ ( 2 k p 1 h 1 p 2 h 2 p 3 h 3 ⋯ p t h t ) : = l c m ( λ ( 2 k ) , λ ( p 1 h 1 ) , λ ( p 2 h 2 ) , λ ( p 3 h 3 ) , ⋯ , λ ( p t h t ) ) ( p n i s a n o d d p r i m e , k ≥ 0 , h n ≥ 1 )
\begin{array}{lcl}
\lambda(1)&:=&1\\
\lambda(2)&:=&1\\
\lambda(4)&:=&4\\
\lambda(2^k)&:=&\phi(2^k)\ (0\leq k\leq 2)\\
\lambda(2^k)&:=&2^{k-2}=\dfrac{\phi(2^k)}{2}\ (e\geq 3)\\
\lambda(p^h)&:=&\phi(p^h)=(p-1)\cdot p^{h-1}\ (p\ is\ an\ odd\ prime, h\geq 1)\\
\lambda(2^kp_1^{h_1}p_2^{h_2}p_3^{h_3}\cdots p_t^{h_t})&:=&\mathrm{lcm}(\lambda(2^k),\lambda(p_1^{h_1}),\lambda(p_2^{h_2}),\lambda(p_3^{h_3}),\cdots,\lambda(p_t^{h_t}))\ (p_n\ is\ an\ odd\ prime, k\geq 0, h_n\geq 1)
\end{array}
λ ( 1 ) λ ( 2 ) λ ( 4 ) λ ( 2 k ) λ ( 2 k ) λ ( p h ) λ ( 2 k p 1 h 1 p 2 h 2 p 3 h 3 ⋯ p t h t ) := := := := := := := 1 1 4 ϕ ( 2 k ) ( 0 ≤ k ≤ 2 ) 2 k − 2 = 2 ϕ ( 2 k ) ( e ≥ 3 ) ϕ ( p h ) = ( p − 1 ) ⋅ p h − 1 ( p i s an o dd p r im e , h ≥ 1 ) lcm ( λ ( 2 k ) , λ ( p 1 h 1 ) , λ ( p 2 h 2 ) , λ ( p 3 h 3 ) , ⋯ , λ ( p t h t )) ( p n i s an o dd p r im e , k ≥ 0 , h n ≥ 1 ) と定義する.
a λ ( n ) ≡ 1 ( m o d n ) ( 2 ≤ n ∈ Z + , gcd ( a , n ) = 1 ) a^{\lambda(n)}\equiv 1\pmod{n}\ (2\leq n\in\mathbb{Z}^{+},\ \gcd(a,n)=1) a λ ( n ) ≡ 1 ( mod n ) ( 2 ≤ n ∈ Z + , g cd( 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