この記事は,
旧ブログ から移植された記事です. よって, その内容として,
旧ブログ に依存した文脈が含まれている可能性があります. 予めご了承下さい.
以前の記事, エルガマル暗号 では, エルガマル暗号に関する諸々の前提の説明と, その実装について示した. 同エントリ内で, フェルマーの小定理については取り扱ったものの, その一般形であるオイラーの定理およびカーマイケルの定理について特に触れなかった ため, 本エントリでそれらに関してまとめる. しばしば値の確認には, 簡単のため 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 ) 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