WUPC2020-D Treasure Mountains で群論をつまみ食いする
久しぶりの更新です. 今回は先日 AOJ 上で開催された早稲田大学プログラミングコンテスト 2020 の D 問題の思考フローに伴い, 群論を軽くつまみ食いしようと思います. (簡単のため, 定理等の詳細な説明を省いたり, 厳密性を欠く記述が見受けられると思いますがご了承ください, 致命的な誤りがあればご指摘いただけると幸いです)
問題はこちら
https://onlinejudge.u-aizu.ac.jp/beta/room.html#WUPC2020/problems/D
概要:
考えたこと:
暗号化が完了した結果はなので, にの指数(とする)の乗法逆元乗をしてあげればいい(日本語さん…). 実はここに「 」が効いてくる.
まずは問題の整理をしましょう. この問題で解決しなければならない問題は大きく分けて二つあります.
- の計算
- の存在性および計算
1. はまずが大きいので一回のクエリで数列を何周もする可能性があり, 累積積を使うなどの工夫が必要です. しかし問題はそれだけでなく, が非常に大きくなることから, 上でそのまま計算することができません. ここでも何らかの工夫が必要です.
2. はが本当に存在するかという問題です. いつでもあると思うな, 乗法逆元ということです. あとは実際のの計算ですが, まあこれは繰り返し二乗法でやればいいでしょう. ただmodに気を付ける必要があります.
解決したい問題が分かったところで、一旦群の話をします.
群というのはある演算・に対し, 集合の要素について以下の3つが全て成り立つときにその集合のことを群と呼びます.
整数全体の集合を考えます. 非常に有名な演算であるところのは, 単位元 0, の逆元 , なのでに関して は群をなします.
一方では, 単位元は1であるものの逆元が一般に存在しません. この掛け算をで考える限り, 2に整数をかけた結果1になるものは無いのです.
これは の世界でもおよそ同じようなことが言えて, 例えば の世界では に をかければ になりますが, には何をかけても にはなりません.
一般に の世界で元 に対して乗法逆元が存在する必要十分条件は, と が互いに素であることです(証明は割愛). の逆元は拡張ユークリッドの互除法というアルゴリズムで具体的に求めることが出来ます.
ここまでで書くと, 制約 が嬉しそうだなと感じてきます. なぜなら も と互いに素になるからです. ただ, が での乗法逆元を指すのか, 別の での乗法逆元を指すのかはこの段階では分かっていません. もし での逆元が欲しいなら, 問題 は解決です.
話を群に戻します. 先の説明から, の が素数である時には の定数倍以外には乗法逆元が存在することが分かります. このとき, 群の定義から の世界での集合 は乗法に関して群を成すことが分かります. (単位元の存在と結合則は明らか. 元 の逆元は となる を整数全体で求め, その を で取り直したもの)
以降の記述のため, の世界での集合 を とします(この説明はあまり厳密ではないですが, 直感的には以降の説明に差し障りはないと思います).
ここで群の元に対する位数の概念と, 位数に対する重要な定理であるラグランジュの定理を説明します.
というのは単位元のことです. また,
という定理があります. 有限群というのは元の個数が有限であるような群のことを指します. 例えば に対する の位数は , の位数は , の位数は , の位数は です. は乗法に関して群をなし, 元の個数が なので確かにラグランジュの定理が確かめられました. ( 自体が という元によって乗法に関して群になれないことに注意です)
ラグランジュの定理から以下のことが言えます.
これは の位数を としたときに なる が存在し, となるためです.
さて, 今回は という制約のもと として暗号化をするのでした. なので が成立し, となります.
とします. 残りのやるべきことは 上での乗法逆元 (つまり法を とした時の乗法逆元)を求め, を で計算することです. 前者は拡張ユークリッドの互除法, 後者は繰り返し二乗法で求めることが出来ます. ここで先程挙げていた問題 の懸念点が解決されました. 注意としてはあくまで は素数ではないこと. 乗法逆元を求める手法として, 互除法のほかに法が素数の場合にのみ適用できるものがありますが今回はそれが適用できません. 私はこれで1時間溶かしました...
解法のまとめ
よって, この問題を以下のような手順で解くことが出来ました.
- 鍵を表す数列 の累積積を計算する.
- を, 累積積を用いて で計算する.
- の乗法逆元 を拡張ユークリッドの互除法で求める.
- 繰り返し二乗法により を で計算して出力する.
感想
群論の知識を扱うのにとてもいい問題でした. コンテスト中には通せなかったのが悔やまれる... この記事が群論に対してハードルの高さを感じている人に, 学んでみようというきっかけを与えられれば嬉しいです. やってみると楽しいよ!
追記: イマイチ分からなかった, という方は以下の記事が非常に要点がまとめられていて非常に分かりやすいと思います. (こういうの勝手に貼っていいのかな)