情報数学1 第1-3章 - Tominaga Lab, Chausson

情報数学１第2-1章
合同式の性質と計算
香川大学工学部富永浩之
[email protected]
概
要
■ 合同式の定義
法と合同
剰余の一致
差の整除
除法等式
■ 合同式の加減乗算
加減算
乗算
累乗
除算
■ 剰余系と代表元
除法等式
剰余条件
整商と剰余
■ 合同式の応用
正剰余
負剰余
■ 二分累乗法
切捨整商
切上整商
最小剰余
第01節 [1] 合同式の定義
合同式 ‥ 整数の性質を剰余で捉えた、
離散で有限な数の世界
整数 n, a, b ; n≧2 において、
法nでaとbは合同
a ≡ b ; mod n
○ 剰余の一致
a と b は n で割った余りが等しい
○ 差の整除
a－b が n の倍数
○ 除法等式
整数パラメタ t で
a＝n×t＋b と表せる
上記の3つの定義は同値
第01節 [2] 整除演算との関係
■ 整除演算との関係
a ÷ b ＝ q ‥ r ; b＞0 のとき
a≡r ; mod b
整数に関する計算や証明が簡単になる
暗号生成、符号訂正、乱数発生、データ圧縮など
情報科学への応用
法12 で 19≡7≡-5
19時は7時で、0時まで後5時間
法360 で 120≡480≡-240
一般角
第02節 [1] 合同式の四則演算
a≡a', b≡b'; mod n のとき
○ 加減算 a±b ≡ a'±b'
○ 乗算
a×b ≡ a'×b'
○ 累乗
a↑c ≡ a'↑c
・合同な数(主に最小剰余)に置き換えながら計算する
・除算は一般にはできない！
第02節 [2] 代表元と剰余系
法3で考えることは、
整数を3で割った余りで、3つのグループに分けて捉えること。
各グループから1つずつ数を選んで代表元とする
一般形
3k
3k+1
3k+2
正剰余
0
1
2
最小剰余
0
+1
-1
{ ‥ -6, -3, 0, +3, +6, ‥ }
{ ‥ -5, -2, +1, +4, +7, ‥ }
{ ‥ -4, -1, +2, +5, +8, ‥ }
代表元の性質が、同じグループの他の元の性質も表している
代表元の集合を剰余系という
正剰余 {0,1,2} や、最小剰余 {-1, 0, +1} などが使われる
第03節 [1] 合同式の加減算
＋ 0
1
＋ 0
1
2
＋ 0
1
2
3
＋ 0
1
2
3
4
5
6
7
0
0
1
0
0
1
2
0
0
1
2
3
0
0
1
2
3
4
5
6
7
1
1
0
1
1
2
0
1
1
2
3
0
1
1
2
3
4
5
6
7
0
2
2
0
1
2
2
3
0
1
2
2
3
4
5
6
7
0
1
3
3
0
1
2
3
3
4
0
1
2
3
4
5
4
4
5
6
7
0
1
2
3
5
5
6
7
0
1
2
3
4
6
6
7
0
1
2
3
4
5
7
7
0
1
2
3
4
5
6
＋ 0
1
2
3
4
－ 0
1
2
3
4
0
0
1
2
3
4
0
0
4
3
2
1
1
1
2
3
4
0
1
1
0
4
3
2
2
2
3
4
0
5
2
2
1
0
4
3
3
3
4
0
1
2
3
3
2
1
0
4
4
4
0
1
2
3
4
4
3
2
1
0
第04節 [1] 合同式の乗算
× 0
1
× 0
1
2
3
4
5
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
1
2
3
4
5
2
0
2
4
0
2
4
× 0
1
2
3
0
3
0
3
0
3
0
0
0
0
4
0
4
2
0
4
2
1
0
1
2
5
0
5
4
3
2
1
2
0
2
1
× 0
1
2
3
0
0
0
0
0
1
0
1
2
3
2
0
2
0
2
3
0
3
2
1
× 0
1 2
3
4
0
0
0 0
0
0
1
0
1 2
3
4
2
0
2 4
1
3
3
0
3 1
4
2
4
0
4 3
2
1
× 0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
7
2
0
2
4
6
0
2
4
6
3
0
3
6
1
4
7
2
5
4
0
4
0
4
0
4
0
4
5
0
5
2
7
4
1
6
3
6
0
6
4
2
0
6
4
2
7
0
7
6
5
4
3
2
1
第05節 [1] 二分累乗法
● 累乗の素朴な計算
a↑n ＝ a×‥×a
乗算n-1回
● 冪が2の累乗のときの効率的な計算
a↑8 ＝ ((a↑2)↑2)↑2 n＝2↑k のとき、二乗k回で済む
● 一般のときの効率的な計算
a↑13 ＝ a×(a↑6)↑2 ＝ a×((a↑3)↑2)↑2 ＝ a×((a×(a↑2))↑2)↑2
● 二分累乗法
a↑0 ＝ 1, a↑1 ＝ a
a↑(2m) ＝ (a↑m)↑2
a↑(2m+1) ＝ a×(a↑m)↑2
素朴な方法に比べて超高速
計算回数は 2log2(n) 程度
n≒10億でも 30～60回 (1億倍弱)
第05節 [2] 二分累乗法の再帰的定義
● 再帰的定義(トップダウン)
a↑n ＝ {
{
{
{
1
a
(a↑(n/2))↑2
a×a↑(n-1)
;
;
;
;
n＝0
n＝1
nが偶数
nが奇数
● 反復計算(ボトムアップ)
2↑13 ＝ 8192
2
2
1
13
4
×
0
6
16 256
aの二乗、その二乗、‥
16×256 ＝ 8192 剰余が1のときだけ乗算
1
1
下列での剰余(nの二進表記)
3
1
2による整商列
第06節 [1] 累乗の剰余の周期性
実用上は、大きな累乗の値は必要ないし、そもそも計算できない
合同式における累乗すなわち剰余が重要である
法7で
2↑1000 ≡ 2×(2↑3)↑333 ≡ 2×1↑333 ≡ 2
累乗の剰余の計算は、乱数発生や暗号生成に必要
● 累乗の剰余の周期性
法7で、5の累乗は周期6
法21で、6の累乗は周期2
5↑1
5↑2
5↑3
5↑4
5↑5
5↑6
6↑1 ≡
6
6↑2 ≡ 36 ≡ -6
6↑3 ≡ -36 ≡ 6
≡
≡
≡
≡
≡
≡
5
4
6
2
3
1
≡ -1
第06節 [2] 累乗の剰余の効率的な計算
○ 指数法則(和・積)
○ 二分累乗法
○ 累乗の剰余の周期性
【例題】 5の1000乗を7で割った余り
5↑6 ≡ 1 と 1000＝6×166＋4 より
5↑1000 ＝ 5↑4×(5↑6)↑166 ≡ 5↑4×1 ≡ 2
【例題】 72の100乗の下2桁
72↑2 ≡ 5184 ≡ -16, 72↑4 ≡ (-16)↑2 ≡ 56
56↑2 ≡ 1936 ≡ 36, 56↑4 ≡ 36↑2 ≡ 1296 ≡ -4
72↑100 ＝ (72↑4)↑25 ≡ 56↑25 ≡ 56×(56↑4)↑6
≡ 56×(-4)↑6 ≡ 56×16↑3 ≡ 56×(-4) ≡ -24 ≡ 76

Download Report