巡回群

前回に引き続き，「5次方程式の非可解性」がどのように確認出来るのかを見てみますgalois_theory3.wxm 一般の5次方程式について考えますので，次数 N に5を代入します（%o1） 最高次の係数を 1 とした5次方程式を%o3に示します この方程式の解を α1～5 とし,1次式の積と同一視します（%o4） これより方程式は5つの解の入れ替えに対して不変であることが解ります 5次対称群 S5 は5つの要素の置換全体からなる群で，その位数は 5! = 120 です これらの元を置換行列で出力した s1～s120 を配列としてまとめて S5 に代入します（%o7） いま In に配列 {1…

前回に引き続き，ガロア理論を用いて「4次方程式の可解性」がどのように確認出来るのかを見てみますgalois_theory2.wxm 一般の4次方程式について考えますので，次数 N に4を代入します（%o1） 最高次の係数を 1 とした4次方程式を%o3に示します この方程式の解を α1～4 とし,1次式の積と同一視します（%o4） これより方程式は4つの解の入れ替えに対して不変であることが解ります 4次対称群 S4 は4つの要素の置換全体からなる群で，その位数は 4! = 24 です これらの元を置換行列で出力した s1～s24 を配列としてまとめて S4 に代入します（%o7） いま In …

今回はガロア理論を用いて「3次方程式の可解性」がどのように確認出来るのかを見てみます例によってMaximaを使うのですが，群の操作がめんどくさいです（'A`) 素直にGAPを使えばよかったかも・・・galois_theory1.wxm 一般の3次方程式について考えますので，次数 N に 3 を代入します（%o1） 最高次の係数を 1 とした3次方程式を%o3に示します この方程式の解を α1～3 とし，1次式の積と同一視します（%o4） これより方程式は3つの解の入れ替えに対して不変であることが解ります 3次対称群 S3 は3つの要素の置換全体からなる群で，その位数は 3! = 6 です S3…

02/12(月) 午前4時に一瞬目を覚ましたらしいが、早々に二度寝に入ることができた。午前7時起床。布団に横たわったまま昼までずっとなろうを読んでいた。 午後1時頃に布団を脱出。今日は建国記念の日の振り替え休日だからインターン先定例会は行われないし、生協も営業していない。なので夜中までずっと先週の週記を書いていたが、案の定なろうに気を取られたりしており、あんまり捗った感じはしなかった。 日付が変わる前に投稿した。久しぶりにコンテストの感想をいくつか書けたが、週末のコンテストまではたどり着けなかった。週末は基本コンテストに出る以外の行動をしていないため、そこが埋まっていないと本当にスカスカになり…

今回は局所類体論の存在定理と呼ばれる局所体上のAbel拡大の分類定理の使い方と、その強さを -進数版のKronecker-Weberの定理 -進数版のKronecker-Weberの定理 を素数とする。任意の 上有限次Abel拡大は、ある自然数 が存在して に含まれる。ここで とは の原始 乗根である。 を証明することで見ていく。 目次: 局所体の定義と性質 局所類体論の存在定理 最後に 参考文献 局所体の定義と性質 この節では以下の内容について話す。 局所体の定義。 局所体 は その整数環の素元 と単数群 により という構造をしている。 局所類体論の存在定理は の指数有限開部分群と 上のAb…

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ABC335を解き直します。 コンテスト時はA～Dの4完でした。 いよいよもって落水の危機に立たされました。自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。 AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。 github.com A問題 atcoder.jp こういう文字列操作の問題は未だにどうRustで書くべきか迷いますね。 スライスを使う…

1/8(月) 今日は13時くらいに起床、昨日寝たのが4時くらいなので9時間くらい寝ていたことになる。なんか頭が痛い。まあ昨日は昼過ぎから図書館に行って、終電まで42にいたので結構自然かなあとも思った。 14時くらいまではだらだらして、シャワーを浴びてコンビニに昼ごはんを買いに行った。一番安い昆布のおにぎりでも140くらいして厳しいなあ、と思った。お腹が空いてたので色々買って750円くらいした。 そこからは今日の24:00が締め切りの生物のレポートをやった。最初はテーマに即さないなあと思っていたけど、細胞の誕生や死滅をシミュレーションするセルオートマトンを作ってなかなかいい出来になった気がする。…

離散対数問題に対するアプローチの一つ。 DLPでもECDLPでも同じアルゴリズムが適用できる。 DLPに対するPohlig-Hellman Attack 前提として、巡回群 の位数 が次のように素因数分解可能であるとする。よくあるのは素数 を法とする乗法群で、その位数はなので、 がB-smoothな場合。 この場合に の代わりに を考える。 と表されるとすると、オイラーの定理より、 となるので、 と置き直すとという形のDLPが導ける。 より、 を生成元とした巡回群の位数はなので、もともとのをBaby step Giant stepで解こうとするとかかっていたのに対して、はで解ける。当然 Pol…

1-out-of-n Oblivious Transferを構成するプロトコル。すなわち、n個のメッセージを送信し、受信者はそのうち1つだけを受信するが、送信者には、受信者がどれを受信したかわからない 準備 素数位数pを持つ巡回群 のgenerator である、何かしらのハッシュ、SHA1とかでいい のある元 プロトコル Alice から Bob にメッセージを送る Alice は 平文 を持ち、 Bob は と を持つ。 または のどちらかがBobに受信される Bob は を計算した後、 をAliceに送る。Aliceは となっていることを確かめておく Aliceは次の を計算してBobに送…

#nullconHackIM2019 https://ctftime.org/task/7528 https://gitlab.com/n0tsobad/ctf-writeups/tree/master/2019-02-01-nullcon/Singular https://grosquildu.github.io/writeups/2019/01/03/nullcon-singular/ https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp Alice and Bob calculated a sha…

Wathematicaで行っていた青雪江ゼミがつい先日終了したのでその活動報告をします！ 【青雪江ゼミ 最終回】5次以上の方程式がべき根で解けないことを証明しました！！！去年の夏頃に始まったこのゼミも本日でついに完結です。お疲れ様でした！！！！！ pic.twitter.com/cC0NNuZFK4 — 理工系学術サークルWathematica (@wathematica) 2023年12月1日 ゼミの概要 その名の通り、使用教科書は雪江明彦先生の『代数学２ 環と体とガロア理論』（日本評論社）です。最近新版が出ましたね。 １人１節ぐらいで発表担当をあらかじめ決めておいて発表する輪読形式のゼミを…