香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学１ 第2-1章 合同式の性質と計算 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp

概 要 ■ 合同式の定義 ■ 合同式の加減乗算 ■ 剰余系と代表元 ■ 合同式の応用 ■ 二分累乗法 概 要 ■ 合同式の定義 法と合同 剰余の一致 差の整除 除法等式 ■ 合同式の加減乗算 加減算 乗算 累乗 除算 ■ 剰余系と代表元 除法等式 剰余条件 整商と剰余 ■ 合同式の応用 正剰余 負剰余 切捨整商 切上整商 最小剰余 ■ 二分累乗法

第01節 [1] 合同式の定義 整数 n, a, b ; n≧2 において、 法nでaとbは合同 a ≡ b ; mod n 合同式 ‥ 整数の性質を剰余で捉えた、 離散で有限な数の世界 整数 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↑c ≡ a'↑c ・ 合同な数(主に最小剰余)に置き換えながら計算する ・ 除算は一般にはできない！

第02節 [2] 代表元と剰余系 法3で考えることは、 整数を3で割った余りで、3つのグループに分けて捉えること。 各グループから1つずつ数を選んで代表元とする 一般形 正剰余 最小剰余 3k 0 0 { ‥ -6, -3, 0, +3, +6, ‥ } 3k+1 1 +1 { ‥ -5, -2, +1, +4, +7, ‥ } 3k+2 2 -1 { ‥ -4, -1, +2, +5, +8, ‥ } 代表元の性質が、同じグループの他の元の性質も表している 代表元の集合を剰余系という 正剰余 {0,1,2} や、最小剰余 {-1, 0, +1} などが使われる

第03節 [1] 合同式の加減算 ＋ 1 ＋ 1 2 ＋ 1 2 3 ＋ 1 2 3 4 5 6 7 ＋ 1 2 3 4 5 － 1 2 3 4

第04節 [1] 合同式の乗算 × 1 × 1 2 3 4 5 × 1 2 × 1 2 3 4 5 6 7 × 1 2 3 × 1 2 3 4

第05節 [1] 二分累乗法 ● 累乗の素朴な計算 a↑n ＝ a×‥×a 乗算n-1回 ● 冪が2の累乗のときの効率的な計算 第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 ; n＝0 第05節 [2] 二分累乗法の再帰的定義 ● 再帰的定義(トップダウン) a↑n ＝ { 1 ; n＝0 { a ; n＝1 { (a↑(n/2))↑2 ; nが偶数 { a×a↑(n-1) ; nが奇数 ● 反復計算(ボトムアップ) 2↑13 ＝ 8192 2 4 16 256 aの二乗、その二乗、‥ 2 × 16×256 ＝ 8192 剰余が1のときだけ乗算 1 0 1 1 下列での剰余(nの二進表記) 13 6 3 1 2による整商列

累乗の剰余の計算は、乱数発生や暗号生成に必要 第06節 [1] 累乗の剰余の周期性 実用上は、大きな累乗の値は必要ないし、そもそも計算できない 合同式における累乗すなわち剰余が重要である 法7で 2↑1000 ≡ 2×(2↑3)↑333 ≡ 2×1↑333 ≡ 2 ● 累乗の剰余の周期性 累乗の剰余の計算は、乱数発生や暗号生成に必要 法7で、5の累乗は周期6 5↑1 ≡ 5 5↑2 ≡ 4 5↑3 ≡ 6 ≡ -1 5↑4 ≡ 2 5↑5 ≡ 3 5↑6 ≡ 1 法21で、6の累乗は周期2 6↑1 ≡ 6 6↑2 ≡ 36 ≡ -6 6↑3 ≡ -36 ≡ 6

第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