はてぃーぽったーの備忘録

某授業まとめ+競プロの感想記事

WUPC2020-D Treasure Mountains で群論をつまみ食いする

久しぶりの更新です. 今回は先日 AOJ 上で開催された早稲田大学プログラミングコンテスト 2020 の D 問題の思考フローに伴い, 群論を軽くつまみ食いしようと思います. (簡単のため, 定理等の詳細な説明を省いたり, 厳密性を欠く記述が見受けられると思いますがご了承ください, 致命的な誤りがあればご指摘いただけると幸いです)

問題はこちら

https://onlinejudge.u-aizu.ac.jp/beta/room.html#WUPC2020/problems/D

概要: 
 N+1 が素数となるような N\geq 4が与えられる
 tを長さMの数列\{d_M\}を使って暗号化(各d_iはNと互いに素)
 tを数aで暗号化...t\mapsto t^a\hspace{2mm} mod\hspace{1mm} N+1
 各クエリx,y,z:\hspace{1mm} tをd_y,d_{(y+1) \% M},...,d_{(y+z-1) \% M}で暗号化した結果xになるとき, tを出力

考えたこと:

暗号化が完了した結果は t^{d_yd_{(y+1)\%M}...d_{(y+z-1)\%M}}=xなので,  x tの指数( kとする)の乗法逆元乗をしてあげればいい(日本語さん…). 実はここに「 各d_iはNと互いに素 」が効いてくる.

 

まずは問題の整理をしましょう. この問題で解決しなければならない問題は大きく分けて二つあります.

  1.  k=d_yd_{(y+1)\%M}...d_{(y+z-1)\%M}の計算
  2.  k^{-1}の存在性および計算

1. はまず zが大きいので一回のクエリで数列 \{d_M\}を何周もする可能性があり, 累積積を使うなどの工夫が必要です. しかし問題はそれだけでなく,  kが非常に大きくなることから,  \mathbb{Z}上でそのまま計算することができません. ここでも何らかの工夫が必要です.

2. は k^{-1}が本当に存在するかという問題です. いつでもあると思うな, 乗法逆元ということです. あとは実際の x^{k^{-1}}の計算ですが, まあこれは繰り返し二乗法でやればいいでしょう. ただmodに気を付ける必要があります.

 

解決したい問題が分かったところで、一旦群の話をします.

群というのはある演算・に対し, 集合 Gの要素について以下の3つが全て成り立つときにその集合のことを群と呼びます.

  1. 単位元 eが存在する. すなわち \forall a\in G に対し,  a・e=e・a=a なる  e\in G が存在する.
  2.  \forall a\in G に対し,  a・b=b・a=e となるような  b\in G が存在する. この  b a^{-1} と書き,  a の(乗法)逆元とよぶ.
  3.  \forall a,b,c\in G に対し,  (a・b)・c=a・(b・c), つまり結合則が成り立つ.

整数全体の集合 \mathbb{Z}を考えます. 非常に有名な演算であるところの '+'は, 単位元 0,  a の逆元  -a,  (a+b)+c=a+(b+c) なので +に関して \mathbb{Z} は群をなします.

一方で '×'は, 単位元は1であるものの逆元が一般に存在しません. この掛け算を \mathbb{Z}で考える限り, 2に整数をかけた結果1になるものは無いのです.

これは  mod\hspace{1mm} m の世界でもおよそ同じようなことが言えて, 例えば  mod\hspace{1mm} 4 の世界では  3 3 をかければ  1 になりますが,  2 には何をかけても  1 にはなりません. 

一般に  mod\hspace{1mm}m の世界で元  a に対して乗法逆元が存在する必要十分条件は,  a m が互いに素であることです(証明は割愛).  a の逆元は拡張ユークリッドの互除法というアルゴリズムで具体的に求めることが出来ます.

ここまでで書くと, 制約  各d_iはNと互いに素 が嬉しそうだなと感じてきます. なぜなら  k=d_yd_{(y+1)\%M}...d_{(y+z-1)\%M} N と互いに素になるからです. ただ,  k^{-1} mod\hspace{1mm} N での乗法逆元を指すのか, 別の  mod での乗法逆元を指すのかはこの段階では分かっていません. もし  mod\hspace{1mm}N での逆元が欲しいなら, 問題  2 は解決です.

 

話を群に戻します. 先の説明から,  mod\hspace{1mm}m m素数である時には  m の定数倍以外には乗法逆元が存在することが分かります. このとき, 群の定義から  mod\hspace{1mm} m の世界での集合  \{1, 2,\dots, m-1\} は乗法に関して群を成すことが分かります. (単位元の存在と結合則は明らか. 元  a の逆元は  ax + my = 1\Leftrightarrow ax = m\times(-y)+1 となる  (x,y) を整数全体で求め, その  x mod\hspace{1mm}m で取り直したもの)

以降の記述のため,  mod\hspace{1mm}p(pは素数) の世界での集合  \{0, 1,\dots,p-1\} \mathbb{F}_p とします(この説明はあまり厳密ではないですが, 直感的には以降の説明に差し障りはないと思います).

 

ここで群の元に対する位数の概念と, 位数に対する重要な定理であるラグランジュの定理を説明します.

 定義(群の元の位数): Gを群, x\in Gとする. もし, x^n=1_Gとなる正の整数が存在すれば, その中で最小のものをxの位数という.

 1_G というのは単位元のことです. また, 

 定理(ラグランジュの定理): Gが有限群なら, g\in G の位数は |G| の約数である.

という定理があります. 有限群というのは元の個数が有限であるような群のことを指します. 例えば  \mathbb{F}_5 に対する  1 の位数は  1,  2 の位数は  4,  3 の位数は  4,  4 の位数は  2 です.  \mathbb{F}_5 - \{0\} は乗法に関して群をなし, 元の個数が  4 なので確かにラグランジュの定理が確かめられました. ( \mathbb{F}_5 自体が  0 という元によって乗法に関して群になれないことに注意です)

ラグランジュの定理から以下のことが言えます.

 系(フェルマーの小定理): x\in \mathbb{F}_pについて, x^{p-1}=1

これは  x の位数を  n としたときに  n\times m = p-1 なる  m が存在し,  x^{p-1}=x^{n\times m}=1^m=1 となるためです.

さて, 今回は  N+1が素数 という制約のもと  t\mapsto t^k\hspace{1mm} mod\hspace{1mm}N+1 として暗号化をするのでした. なので  t^N=1 が成立し,  t^k=t^{k\%N} となります. 

 k\%N=k' とします. 残りのやるべきことは  \mathbb{F}_{N+1}-\{0\} 上での乗法逆元  k'^{-1} (つまり法を  N とした時の乗法逆元)を求め,  x^{k'^{-1}} mod\hspace{1mm}N+1 で計算することです. 前者は拡張ユークリッドの互除法, 後者は繰り返し二乗法で求めることが出来ます. ここで先程挙げていた問題  2 の懸念点が解決されました. 注意としてはあくまで  N素数ではないこと. 乗法逆元を求める手法として, 互除法のほかに法が素数の場合にのみ適用できるものがありますが今回はそれが適用できません. 私はこれで1時間溶かしました...

 

解法のまとめ

よって, この問題を以下のような手順で解くことが出来ました.

  1. 鍵を表す数列  \{d_M\} の累積積を計算する.
  2.  k=d_yd_{(y+1)\%M}...d_{(y+z-1)\%M} を, 累積積を用いて  mod\hspace{1mm} N で計算する.
  3.  k の乗法逆元  k^{-1} を拡張ユークリッドの互除法で求める.
  4. 繰り返し二乗法により  x^{k^{-1}} mod\hspace{1mm}N+1 で計算して出力する.

 

感想

群論の知識を扱うのにとてもいい問題でした. コンテスト中には通せなかったのが悔やまれる... この記事が群論に対してハードルの高さを感じている人に, 学んでみようというきっかけを与えられれば嬉しいです. やってみると楽しいよ!

 

追記: イマイチ分からなかった, という方は以下の記事が非常に要点がまとめられていて非常に分かりやすいと思います. (こういうの勝手に貼っていいのかな)

剰余の乗法の逆元とRSA暗号

参考資料

www.amazon.co.jp