香川大学創造工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学１ 第2-2章 合同式の逆元と応用 香川大学創造工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp

概 要 ■ 合同式の逆元の定義と性質 ■ 逆元の存在条件と零因子 ■ 複合同式と不定方程式 ■ 合同式の逆元の応用 概 要 ■ 合同式の逆元の定義と性質 逆元の定義 特別な値の逆元 積の逆元 反数の逆元 ■ 逆元の存在条件と零因子 逆元の存在条件 零因子 逆元の一覧 ■ 複合同式と不定方程式 複合同式 中国剰余定理 ユークリッドの拡張互除法 ■ 合同式の逆元の応用 剰余速算法 整除判定法 合同式の漸化式 ■ 合同式の数理パズルや情報処理への応用 ヨセフス問題 公開鍵暗号系 線形合同法による乱数

第01節 [1] 合同式における逆元の定義 法nにおいて、a×b≡1 となるとき、 bはaの逆元といい、a~ と書く。 aとbが互いに逆元であることは a⇔b と書く。 任意の法nにおいて 1×1≡1 より 1~≡1 逆元は必ずしも存在するとは限らない 任意の法nにおいて 0×□≡0 なので、0に逆元は存在しない 法 3 で 2×2≡1 より 2~≡2 法 4 で 2×2≡0, 2×3≡2 より、2 の逆元は存在しない 法 4 で 3×3≡1 より 3~≡3 法 5 で 2×3≡1 より 2~≡3 また 3~≡2 法 5 で 4×4≡1 より 4~≡4

第01節 [2] 逆元の存在条件と零因子 ● 逆元の存在条件 ● 逆元と零因子 a⊥n のとき 法nにおけるaの逆元が存在する a×b≡0 となる、0でないbが存在 このようなaを零因子という ● 逆元と零因子 法nが素数のとき、1～n-1 の全てが、可逆元 法nが合成数のとき、a⊥n のとき、可逆元 a⊥n でないとき、零因子

第01節 [3] 逆元の一覧 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 例えば、法11の行を横に見ると、 1×1≡2×6≡3×4≡5×9≡7×8≡10×10≡1

第02節 [1] 逆元の性質 任意の法 n で、1 の逆元は 1 任意の法 n で、n-1 の逆元は n-1 法 n で、a の逆元が b ならば、-a の逆元は -b 法 2m+1 で、2 の逆元は -m≡m+1 で、m の逆元は -2≡2m-1 法 3m+1 で、3 の逆元は -m で、+m の逆元は -3≡3m-2 法 3m-1 で、3 の逆元は +m で、-m の逆元は -3≡3m-4 法 4m で、2m+1 の逆元は 2m+1 で、2m-1 の逆元は 2m-1 法 35 で、34 の逆元は 34 法 123 で、2 の逆元は 62 で、61 の逆元は -2≡121 法 451 で、3 の逆元は -150≡301 で、150 の逆元は -3≡448 法 449 で、3 の逆元は 150 で、-150≡299 の逆元は -3≡446

第02節 [2] 逆元を求める素朴な方法 法19で8の逆元 法 n において、a の逆元を求めるとき、まず [0] を確認し、 逆元が存在するなら、[1] または [2] の方法を用いる。 [0] 法 n とa が互いに素でなければ、逆元は存在しない。 [1] a の倍数列を列挙し、n による剰余が1になるものを探す。 実際には、a の倍数列は、法 n で考えればよい。 [2] n の倍数列を列挙し、それに 1 を加えて a で割り切れるものを探す。(a＜n なら、こちらの方が効率的) 法19で8の逆元 [1] 8×2≡16, 8×3≡5, 8×4≡13, 8×5≡2, 8×6≡10, 8×7≡18, 8×8≡7, 8×9≡15, 8×10≡4, 8×11≡12, 8×12≡1 より 8~≡12 [2] 19の倍数+1 で考えると、1, 20, 39, 58, 77, 96 で 96%8＝0, 96@8＝12 で 8~≡12

第02節 [3] 互いに逆元となる組の見つけ方 ある法 n において、逆元となる2数の組を見つけるには、 a×b≡1 を満たす2数の組を考えればよい。 ここで、 a×b≡1 のとき、整数パラメタ t を用いて、 a×b＝1＋nt と表せる。 したがって、 n の倍数列に 1 を足した ±n+1, ±2n+1, ‥ を考え、 積の形で表せば、逆元の組を見つけたことになる。 例えば、法 67 において、 1≡67+1≡68≡4×17≡2×34 より、 4 ⇔ 17, 2 ⇔ 34 が見つかる。 また、 1≡-(-4)×(-17)≡63×50 , 1≡(-2)×(-34)≡65×33 に着目すれば、 63 ⇔ 50, 65 ⇔ 33 も見つけることができる。 さらに、 -1≡-67+1≡-66≡3×(-22)≡3×35≡(-3)×22≡64×22 より、 3 ⇔ 45, 64 ⇔ 22 が見つかる。

第02節 [3] 逆元の一覧 法22で逆元の一覧を求める。 22は合成数であり、2と11を素因数に持つ。 0は逆元を持たず、零因子でもない。 0以外で、素因数の倍数である 2,4,6,8,10,11,12,14,16,18,20 は 22と互いに素でないから、零因子であり、逆元が存在しない。 したがって、残りの 1,3,5,7,9,13,15,17,19,21 の10個について 逆元を求めればよい。 まず、1 ⇔ 1, 21 ⇔ 21 は明らかである。 22×1＋1＝23 は素数であるから積の形に表せず、使えない。 22×(-1)＋1＝-21＝(-3)×7＝3×(-7) より、19 ⇔ 7, 3 ⇔ 15 が見つかる。 22×2＋1＝45＝3×15＝9×5＝(-9)×(-5) より、 新たに 9 ⇔ 5, 13 ⇔ 17 が見つかる。 以上で、全ての場合が尽くされている。

第03節 [1] 素因数分解による逆元の求値 法39で29の逆元 法26で15の逆元 法67で59の逆元 a または n-a を素因数分解して、各因数の逆元の積を求める。 逆元の指数法則 (-a)~≡-(a~) と (ab)~≡(a~)(b~) を用いる。 法39で29の逆元 29≡-10 で 10×4≡1 より 10~≡4 で 29~≡(-10)~≡-(10~)≡-4≡35 法26で15の逆元 15≡3×5 で 3×9≡1, 5×5≡-1 より 3~≡9, 5≡-5 よって 15~≡(3~)×(5~)≡9×(-5)≡7 法67で59の逆元 59≡-8≡-(2^3) で 2×34≡1 より 2~≡34≡2×17 よって 59~≡-(8~)≡-(34^3)≡-2×2×2×17×17×17≡-2×17×17≡19

第03節 [2] 倍数列の剰余値による逆元の求値 法26で11の逆元 法73で47の逆元 a の倍数列を組み合わせて、剰余値 1 を作り出す。 法26で11の逆元 11×1≡11≡-15 ‥ ①, 11×2≡22≡-4 ‥ ② ここで ①×(-1)＋②×(-3) を考えると (11)×(-1)＋(-4)×(-3)≡1 すなわち 11×{(1)×(-1)＋(2)×(-3)}≡11×(-7)≡1 より 11~≡-7≡19 法73で47の逆元 47×1≡47≡-26 ‥ ①, 47×2≡21≡-52 ‥ ②, 47×3≡68≡-5 ‥ ③ ここで ①×(-1)＋③×(5) を考えると (-26)×(-1)＋(-5)×(5)≡1 すなわち 47×{(1)×(-1)＋(3)×(5)}≡47×14≡1 より 47~≡14

第03節 [3] 不定方程式による逆元の求値 法47で34の逆元 合同式の逆元の定義を、整数パラメタを使った除法等式で記述し、 ユークリッドの不定方程式に帰着させる。 目の子によらない機械的な手順で、効率的な算法である。 法47で34の逆元 法47で34の逆元を x とすると 34x≡1 ; mod 47 整数パラメタ t を用いた除法等式で 34x＝1＋47t これより、ユークリッドの不定方程式 34x－47t＝1 34x－47t＝34(x－t)－13t で y＝x－t とおき 34y－13t＝1 34y－13t＝13(3y－t)－5y で s＝3y－t とおき 13s－5y＝1 13s－5y＝5(3s－y)－2s で z＝3s－y とおき 5z－2s＝1 ここで、具体解 z＝1, s＝2 を得る。 これから逆算し、y＝3s－z＝5, t＝3y－s＝13, x＝y＋t＝18 で 34~≡18

第04節 [3] 複合同式と中国剰余問題 中国古代の書物「孫子算経」に、以下のような問題と解法が載っている。 「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」 これは、複数の除数に対する剰余から元の整数を求める問題である。 これが西洋に伝わり、中国剰余問題と呼ばれるようになった。 異なる法による合同式として立式されるので、複合同式ともいう。 a で割ると r 余り、b で割ると s 余る数 n n≡r ; mod a, n≡s ; mod b 複合同式において、法 a,b が互いに素のとき、 解 n が、0～ab-1 の範囲に必ず1つ存在する。 別の言い方をすれば、法 ab で、一意に定まる。 上記の問題では、3個の法 3,5,7 に関する問題であるが、互いに素で、 3×5×7＝105 であり、105 未満の自然数に解が存在する。 そのため、江戸時代の日本の書物では、百五減算として紹介されていた。

第04節 [4] 複合同式の逆元による解法 11で割って3余り、13で割って6余る整数 n 複合同式は、法 a,b が互いに素の場合、古来より、 互いの逆元を求めて組み合わせる解法が知られている。 解 n は、0～ab-1 の範囲で、あるいは法 ab で、一意に定まる。 a⊥b で n≡r ; mod a, n≡s ; mod b n＝ax＋by とおくと、n≡by≡r ; mod a, n≡ax≡s ; mod b これから y≡rb~ ; mod a, x≡sa~ ; mod b よって n≡a(sa~)＋b(rb~) ; mod ab 11で割って3余り、13で割って6余る整数 n 題意より n≡3 ; mod 11, n≡6 ; mod 13 n＝11a＋13b とおく。 このとき n≡13b≡2b≡3 ; mod 11, n≡11a≡-2a≡6 ; mod 13 これから b≡3×2~≡3×6≡7, a≡6×(-2)~≡6×6≡10 よって n＝11×10＋13×7＝201 実際には n≡201≡58 ; mod 143 すなわち、一般解は n＝58＋143t ; tは整数パラメタ

第04節 [5] 複合同式の拡張互除法による解法 11で割って3余り、13で割って6余る、最小の自然数 実際には、複合同式は、ユークリッドの不定方程式に帰着させ、 拡張互除法で解く方が効率的である。 この解法は、法が互いに素でない場合でも通用する。 ただし、解が存在しない場合がある。 11で割って3余り、13で割って6余る、最小の自然数 題意より n≡3 ; mod 11, n≡6 ; mod 13 除法等式で n＝3＋11x, n＝6＋13y から ユークリッドの不定方程式 11x-13y＝3 具体解 x＝5, y＝4 から、一般解 x＝5＋13t, y＝4＋13t よって n＝3＋11(5＋13t)＝58＋143t ; t は整数パラメタ nは自然数であるから n≧0 で t≧0 最小性より t＝0 で n＝58

第04節 [6] 中国剰余定理 複合同式すなわち中国剰余問題の解の存在性は、以下の通りである。 これを中国剰余定理と呼ぶ。非常に重要な定理である。 複合同式 n≡r ; mod a, n≡s ; mod b において、 a⊥b のとき、以下の解法により、法 ab で唯一の解が存在する。 n＝ax＋by とおくと、n≡by≡r ; mod a, n≡ax≡s ; mod b これから y≡rb~ ; mod a, x≡sa~ ; mod b よって n≡a(sa~)＋b(rb~) ; mod ab a⊥b でないとき、剰余の差 c＝r-s が d＝gcd(a,b) で割り切れれば、 法 lcm(a,b)＝ab/d で唯一の解が存在する。 解法は、余因数 a'＝a/d, b'＝b/d を考え、 n≡r≡r' ; mod a', n≡s≡s' ; mod b' に帰着させる。 割り切れないとき、解は存在しない。

第05節 [1] 剰余速算法 ● 10の因数による剰余速算法 ● 3と11の剰余速算法 ○ 2^p で割った剰余 下位p桁を2^pで割った余り ○ 5^p で割った剰余 下位p桁を5^pで割った余り ● 3と11の剰余速算法 ○ 3 で割った剰余 各桁の数字の総和を3で割った余り ○ 9 で割った剰余 各桁の数字の総和を9で割った余り ○ 11 で割った剰余 奇数番目の数字の総和から 偶数番目の数字の総和を 引いた値を11で割った余り

第05節 [2] 整除判定法 ● 法での10の逆元を利用した整除判定法 ○ 7 の倍数 十の位以上に、一の位を5倍して加えた数 ○ 7 の倍数 十の位以上に、一の位を5倍して加えた数 ○ 13 の倍数 十の位以上に、一の位を2倍して引いた数 ○ 17 の倍数 十の位以上に、一の位を5倍して引いた数 ○ 19 の倍数 十の位以上に、一の位を2倍して加えた数 8569 → 856＋9×5＝901 → 90＋1×5＝95 7の倍数でない 3679 → 367＋9×4＝403 → 40＋3×4＝52 13の倍数 5432 → 543－2×5＝533 → 53－3×5＝38 17の倍数でない 6498 → 649＋8×2＝665 → 66＋5×2＝78 19の倍数