ぺんぎんさんのおうち

トリトリトリ

タイトルは後で考える

いくつか命題を証明していきたい.

素数pを法とすると平方剰余の個数は(p-1)/2個となる

\(A := \{x^{2} \, mod \, p \mid x \in GF(p) \} \) としたときに, \( \#A = \frac{p-1}{2} \) となることを示したい.

まず\(GF(p) = \{1, 2, ..., p-1 \}\), \(\#GF(p) = p-1\)であり, \(\forall a \in A, a^{\frac{p-1}{2}} \equiv 1 \, mod \, p\)


\(x^{2} \equiv (p-x)^{2} \, mod \, p\) であるため,

\begin{eqnarray} 1^{2} &\equiv& (p-1)^{2} \, mod \, p \newline 2^{2} &\equiv& (p-2)^{2} \, mod \, p \newline . \newline . \newline ({\frac{p-1}{2}})^{2} &\equiv& ({\frac{p+1}{2}})^{2} \, mod \, p \newline \end{eqnarray}

したがって\( \#A = \frac{p-1}{2} \)である. \(GF(p)\)の半分の元は平方剰余, もう半分は平方非剰余であることを言っている.


p ≡ 2 mod 3 のとき, x3 = a mod pはただ一つのみ解を持つ

\(f_p(x) = x^{3}\) が全単射であることを示せばよく, \( f: GF(p) \rightarrow GF(p) \)であるため単射であるならば全射でもある. 単射であることを示そう.

単射の定義より, \(f_p(x) = f_p(y) \) なら \(x = y\)である.

\begin{eqnarray} x^{3} &\equiv & y^{3} \, (mod \, p) \newline (xy^{-1})^{3} & \equiv & 1 \newline \end{eqnarray}

ここで一旦置いておく.
先に, \(z^{3} \equiv 1 \, mod \, p; z \in GF(p) \) なら\( z \equiv 1 \, mod \, p\) を示す.

\(z^{3} = 1\)であるから \( \#G(z) \mid 3 \). これは\((1, 3)\)のどちらかである.

またラグランジュの定理より, \(G(z)\)は\(GF(p)\)の部分群であるため \( \#G(z) \mid \#GF(p) \)でなければならない.

\(p \equiv 2 \, mod \, 3\)より \(p = 3k + 2\)
\(\#GF(p) = p - 1 = 3k + 1 \)

\( \#G(z) \mid \#GF(p) \) となる\(\#G(z)\)は1のみであるから \( z^{3} \equiv 1 \, mod \, p\) なら \( z \equiv 1 \, mod \, p\)

これを踏まえて上の式を考える.
\begin{eqnarray} (xy^{-1})^{3} & \equiv & 1 \newline xy^{-1} & \equiv & 1 \newline x & \equiv & y \, mod \, p \end{eqnarray}

\(x, y \in GF(p)\)なので \(x \equiv y\)から\(x = y\)が言える.
\(f_p(x) = f_p(y) \) なら \(x = y\)を示せたので, \(f_p(x) = x^{3}\)は単射である.

したがって\(f_p(x) = x^{3}\)は全単射であり, p ≡ 2 mod 3のとき, x3 = a mod pはただ一つのみ解を持つ.

以下参考:
If 𝑝≡2 mod 3, 𝑥3≡𝑎 mod 𝑝 has only one solution modulo 𝑝.


上の2つは, 楕円曲線\(E_p(0, b); p \equiv 2 \, mod \, 3\) の位数が\(p+1\)であることを示すために使われる.

\(K := \{x^{3} + b \mid x \in GF(p), b \neq 0 \} \) のとき, \(K = \{ 0 \} \cup GF(p) \backslash \{b\} \neq GF(p) \) であるが, これは\(x^{3} + b \equiv 0 \, mod \, p\) の解が存在することを示している. この場合でも位数は変わらない.

Euler's criterion 平方剰余の判別

整数論において奇素数\(p\)をModulusとしたとき, \(a \in GF(p)\)について $$ x^{2} \equiv a \, mod \, p $$

となる \(x\)が存在するとき\(a\)を\(p\)の平方剰余であるという.
\(a\)が平方剰余であるかどうか(上式で解を持つかどうか)を判定するのに使われるのがEuler's criterion(オイラーの基準)である.

式はシンプルで, \(a \in GF(p)\)を入力に取り, 出力は\(\{0,1,-1\}\)のどれかである. (ルジャンドル記号の話は割愛する)
0が出力されるのは\(a\)が\(p\)で割り切れる場合であり, この記事内では扱わない.

$$ a^{\frac{p-1}{2}} \, mod \, p = \begin{cases} 0 \newline 1 \newline -1
\end{cases} $$

上式で1が出力されれば\(a\)は平方剰余である(\(x^{2} \equiv a \, mod \, p\)の解が存在する).

なぜ1を得たときに\(a\)が平方剰余となるのかを解説していこう.
まずフェルマーの小定理より, modulusは素数なので任意の \(a \in GF(p)\)について

$$ a^{p-1} \equiv 1 \, mod \, p $$

これを変形していく.

\begin{eqnarray} a^{p-1} & \equiv & 1 \, mod \, p \newline a^{p-1} - 1 & \equiv & 0 \newline (a^{\frac{p-1}{2}} - 1)(a^{\frac{p-1}{2}} + 1) & \equiv & 0 \newline \end{eqnarray}

2つの因数が得られ, これらを別々に考える.

・ \((a^{\frac{p-1}{2}} - 1) \equiv 0\)

\begin{eqnarray} a^{\frac{p-1}{2}} - 1 & \equiv & 0 \, mod \, p \newline a^{\frac{p-1}{2}} & \equiv & 1 \, mod \, p \newline \end{eqnarray}

ここで, \(x^{2} \equiv a \)とすると

\begin{eqnarray} {x^{2}}^{\frac{p-1}{2}} & \equiv & 1 \, mod \, p \newline x^{p-1} & \equiv & 1 \, mod \, p \newline \end{eqnarray}

\(a\) と \(p\) は互いに素であり \(x\) と \(p\) も同様に互いに素であるためフェルマーの小定理に従う.
したがって, \(x^{2} \equiv a \, mod \, p\)を満たす\(x\)は存在し, \(a\)は平方剰余であることがいえる.

言い換えると, \(a^{\frac{p-1}{2}} \, mod \, p = 1\) であれば \(x^{2} \equiv a \, mod \, p\)を満たす\(x\)が必ず存在する.


・ \((a^{\frac{p-1}{2}} +1) \equiv 0\)

\begin{eqnarray} a^{\frac{p-1}{2}} + 1 & \equiv & 0 \, mod \, p \newline a^{\frac{p-1}{2}} & \equiv & -1 \, mod \, p \newline (& \equiv & p-1 \, mod \, p) \end{eqnarray}

先ほどと同様に, \(x^{2} \equiv a \)とすると

\begin{eqnarray} {x^{2}}^{\frac{p-1}{2}} & \equiv & -1 \, mod \, p \newline x^{p-1} & \equiv & -1 \, mod \, p \newline \end{eqnarray}

\(x\) と \(p\) は互いに素であるため, フェルマーの小定理に従うはずである. このような\(x \in GF(p)\)は存在しない.
これは \(x^{2} \equiv a \, mod \, p\)を満たす\(x\)が存在せず, \(a\)は平方剰余でないことを意味している.


楕円曲線の整数点

Euler's criterionを利用すると, \((x, y) \in GF(p)\)で総当たりをしなくても, \(x \in GF(p)\)で右辺を計算した結果が平方剰余かどうか判定すれば, ある\(x\)について曲線の式を満たす\(y\)が存在するか判別できる.

Euler's criteriionはあくまで平方剰余かどうかを判別するだけで, 実際の解を得るわけではない点に注意. 解を得るには Tonelli–Shanks algorithm を読むと良い.

複素数点を持つ楕円曲線は構成可能か

はじめに

これは妄想である. なにか明確な答えがあるわけではない.
現在, よく知られている楕円曲線は整数点\((x, y)\)を持つが, これを複素数点\((z_{1}, z_{2})\)で考えることは可能かという話.

この件に関して, 本を探したりネットで検索したりは一切していない. もしかしたら結論が出ているのかもしれないが, 結論を知ってしまったら面白くないだろう.
もし可能だったとして, 複素数で考えることによってセキュリティがどうこうとかそういう話をする予定もない. 単純に気になっただけである.


追記: 複素数点を持つ楕円曲線は構成可能なのか(ちゃんと点と点の足し算などを考えられるか)という話からスタートしたが, ある点と別の点を足して得られた点やある点を2倍して得られた点がちゃんと同じ曲線に乗っていることが確認できた.
これを"複素数楕円曲線"として定義しよう.



複素数

複素数\(z\)は実数\(a, b\)と虚数単位を意味する\(i\)を使って以下のように表される.

$$ z = a + bi; \, a, b \in \mathcal{R}
$$

複素数は体か?

  • 加法, 乗法において結合律を満たす
  • 加法における単位元0が存在する \((e = 0 + 0i)\)
  • 乗法における単位元1が存在する \((e = 1 + 0i)\)

あとは逆元である. まずは加法.
逆元\(-z\)は

$$ -z = -a + (-bi) $$ であり,

\begin{eqnarray} z + (-z) &=& (a + bi) + (-a - bi) \newline &=& 0 + 0i \end{eqnarray} となるため逆元が存在することが言える.
次に乗法. 乗法では零元を考えない.

逆元\(z^{-1}\)は

$$ z^{-1} = \frac{1}{a + bi} = \frac{a - bi}{a^{2} + b^{2}} \, (= \frac{a}{a^{2} + b^{2}} - \frac{b}{a^{2} + b^{2}} i ) $$

\(zz^{-1} = 1 + 0i\)となることを確認しよう.

\begin{eqnarray} zz^{-1} &=& (a + bi) \frac{a - bi}{a^{2} + b^{2}} \newline &=& \frac{a^{2} + b^{2}}{a^{2} + b^{2}} \newline &=& 1 + 0i \end{eqnarray}

したがって複素数\(\mathcal{C}\)は体であることがわかる.

複素数で剰余体を考える

剰余環でもいいが, 楕円曲線につなげることを考えると体の方が都合が良い.
基本的な演算は剰余を考えない場合と同じだが, \(z = a+bi; \, (a, b \in \mathcal{Z}) \)とする.

剰余を考えない場合と同様に確認していこう. Modulusを素数\(p\)とする.

  • 加法, 乗法において結合律を満たす
  • 加法における単位元0が存在する \((e = 0 + 0i)\)
  • 乗法における単位元1が存在する \((e = 1 + 0i)\)

逆元をみていこう.
加法
\begin{eqnarray} z + (-z) &=& (a + bi) + (-a - bi) \, mod \, p \newline &=& (a + bi) + ((p-a) + (p- b)i) \newline &=& a + (p-a) + (bi + pi- bi) \newline &=& p + pi \newline &=& 0 + 0i \end{eqnarray}

加法において\(-z = -a - bi \, mod \, p\)が逆元として存在する.
続いて乗法. やはり零元は考えない.

\begin{eqnarray} z^{-1} &=& \frac{1}{a + bi} \, mod \, p \newline &=& \frac{a}{a^{2} + b^{2}} - \frac{b}{a^{2} + b^{2}}i \newline &=& a(a^{2} + b^{2})^{-1} - bi(a^{2} + b^{2})^{-1} \newline &=& (a - bi)(a^{2} + b^{2})^{-1} \end{eqnarray}

\(zz^{-1} = 1 + 0i\)となればよい.

\begin{eqnarray} zz^{-1} &=& (a + bi)(a - bi)(a^{2} + b^{2})^{-1} \newline &=& (a^{2} + b^{2})(a^{2} + b^{2})^{-1} \newline &=& 1 + 0i \end{eqnarray}


ただし, \(a^{2} + b^{2} \neq 0 \, mod \, p \, \,(\forall a, b \in GF(p) )\)でなければならない.
このような\(p\)は, 複素数を使っても素因数分解できない素数を選べばいい気がしている.

たとえば, \(17 = (4 + i)(4 - i)\) や \(65537 = (256 + i)(256 - i)\)はだめ. \(17 = 4^{2} + (-i^{2}) \) なので正しそう.


Modulusである素数の選び方によっては複素数の剰余体を構成することが可能であることが言えそうな気がしてきた.
ではこれらを踏まえて, 今回の本題である楕円曲線の話に進んでいこう.

複素数点 on the Elliptic Curve

楕円曲線では, 点の座標を\((x, y); \, \, x, y \in GF(p) \) を使って表した.
これを \( (z_{1}, z_{2}) \) に置き換えてみる. ここで \( z_{1} = x_{1} + y_{1}i\), \( z_{2} = x_{2} + y_{2}i\) としよう.


$$ z_{2}^{2} = z_{1}^{3} + Az_{1} + B $$

$$ A := (a, 0) = a + 0i , B := (b, 0) = b + 0i $$

(左辺の実部 = 右辺の実部) & (左辺の虚部 = 右辺の虚部) となるような\( (z_{1}, z_{2}) \)を, この曲線の点とする.

\( (z_{1}, z_{2}) \)のそれぞれが実部と虚部を持つので4次元(?)空間になる. グラフで表現できないということが素晴らしい.

Golangで実装した. 点と点の足し算の定義などはしていないが, 実際に楕円曲線の式を満たす点は存在することがわかった.

\(P = (zx_{1}, zy_{1})\), \(Q = (zx_{2}, zy_{2})\) を \(P = (x_{1}, y_{1})\), \(Q = (x_{2}, y_{2})\) とみなして計算しても同じ曲線の上に点を持つ. ということは, これを複素数点を持つ楕円曲線として定義できたことになる.

電通大に編入して約一ヶ月経ったので

もうすぐ4月も終わりということで、電通大編入して一ヶ月過ごした雑感を述べていきます。

 

 

単位認定

これだけで4月が終わった。

先生との面談自体は20日くらいに終わってましたが、最終的な書類の提出はGW前だったので単位認定だけで4月が終わったと言っても過言ではないですね。

お疲れ様でした。

 

 

人が多い

なんですかこれ。昼休みの生協とかやばいですよほんとに。

GW明けから人がいなくなると聞いたので期待ですね。

 

 

研究室

編入生だからとすぐに仮配属されることはなく、内部生と同様のシステムで(仮)配属が決まります。

授業しかすることないので先生にアポとって見学してきました。今は週一ペースで先輩の研究の見学や手伝いしてます。

 

 

一ヶ月くらいじゃ書くことないですね。

前期が終わったら、夏休みに突入したら改めて記事を書くことにします。

電通大3年次編入 単位認定 [2019年度]

追記1: 令和元年(これいる?)に申請した科目について、編入生全員の単位が認定されました。やったね。

単位認定マラソン、最終書類を提出したので第三部完です。
正式な認定については6月頃に公開される(と思う)ので、公開されたら詳しく追記します。
追記2: 追記しません。2000万稼がなきゃいけないので。


面倒という話は諸先輩方から聞いていましたが、いざ実際にやってみると想像のInf倍は面倒でした。

電通大の単位認定は他の大学と比較すると結構厳しいと思います。シラバス提出するだけであとはよしなにしてくれるところもありますしね。
単位認定を進学する大学の選考に考慮するのはナンセンスかもしれませんが、最悪のケースが存在することは知っておいた方がいいでしょう。電通大への進学を考えているのなら、高専の選択科目もなるべく受講した方がいいです。「この講義受ける暇があるならコード書くわw」とかバカみたいなこと言ってると電通大入ってから大変になります。

ということで、単位認定の話を詳しくやっていきます。

私は制御情報工学科からII類のセキュリティ情報学へ進んだのでセキュリティ系の科目は一切やっていませんでしたが、電通大でもセキュリティの授業は3年生から開講なので気にしなくてもいいかもしれません。もし高専で講義としてやっていれば認定してくれる可能性はあるので一応書いておきましょう。
ただし、3年生の科目は原則、時間割を組むのが難しい場合(1,2年の必修が3年の科目(必修も選択も)と被っている)のみ認定してくれるので、認定されればラッキーくらいで思っていた方がいいです。基本的には1,2年の必修科目の認定を優先するように言われます。それはそう。


B4の人曰く、類に改組されてからセキュリティ情報学プログラムに編入したのは僕が一人目らしいです。これを読んでいる、セキュリティ情報学に進もうと思っている2020年入学の皆さんは僕が唯一の先輩になるわけです。残念でしたね...。

認定までの流れ

  1. 作業書のお知らせが届く(2月頃)
  2. 作業書を作成, シラバスを用意
  3. 書類を電通大へ提出
  4. 返却された作業書をみて, 追加認定や再提出
  5. 最終的な認定書類を作成して提出(作業書とは別)
  6. 認定された単位の発表

大抵ガイダンスのときに作業書が返却されます。"要面談"や"否"と書かれた科目があれば先生にメールして面談のアポを取りましょう。
ガイダンスの次の日にはメールを出すくらいでいいと思います。早く動かないと他の編入生もいますし授業始まるとなかなか面談の都合がつかなくなります。

必修科目 (1)

もしII類に進むのであれば、以下の科目が必修となります。認定されるよう頑張りましょう。

面談等で認定してあげるよと言われた科目に対して認定 "可" としています。

科目 内容 備考 認定
確率統計 確率
力学 力学物理 物理学概論1,2があるので認定が難しいかも
応用数学A フーリエ変換, ラプラス変換
基礎電気回路 アナログ回路
基礎電磁気学 電磁気学
基礎演習A 応用数学,基礎電気回路,基礎電磁気学の演習
数値解析およびプログラミング演習 数値解析 数値解析系のシミュレーションをやっていれば認定される可能性あり
アルゴリズムとデータ構造およびプログラミング演習

以上が専門の必修科目です。

それぞれ順に紹介していきます。webで参照可能なシラバスに各科目の詳細が書かれているので、ここでは一部だけとします。

確率統計

名前どおりですね。 ガウス分布や共分散、期待値、確率変数とかやってると心強いです。

力学

これも名前どおりですね。物理学、特に力学をやります。 剛体モーメントとかやってたらいいんじゃないでしょうか。ただ、一年生の物理学概論第一/第二を認定させてしまうと物理科目を使い切るのでこちらの認定は難しいかもしれません。

応用数学A

フーリエ変換ラプラス変換をします。

基礎電気回路

アナログ回路です。

基礎電磁気学

ファラデーとかクーロン、マクスウェル方程式とかだったと思います。

基礎演習A

応用数学A, 基礎電気回路, 基礎電磁気学の演習をローテーションします。

数値解析およびプログラミング演習

二分法、ルンゲクッタ法といった数値解析系の演習をします。

アルゴリズムとデータ構造およびプログラミング演習

ソートアルゴリズムやスタック/キュー構造とかですね。


必修科目 (2)

数学、化学、物理の必修科目です。
類に関係なく全員が修得しなければない科目になります。 全部修得しないと4年生になれません(厳密に言うと研究室配属されない)。絶対に認定してもらうか受講しましょう。

電通大の科目 内容 備考 認定
微分積分学第一
微分積分学第二
線形代数学第一 行列とか
線形代数学第二 ベクトル空間とか
解析学 微分方程式や整数級
数学演習第一
数学演習第二
物理学概論第一
物理学概論第二
化学概論第一 物理寄り(熱力学とか量子)
基礎プログラミングおよび演習

各科目の詳細は省きます。面倒なので。

これだけは絶対認定されておけ

基礎科学実験A

物理系の実験です。 1年生と仲良くなれるやんけ!なんてことは考えず、高専で実習・実験をやっているなら優先して認定してもらいましょう。

基礎科学実験B

こちらは化学系の実験です。 Aと同様に、認定してもらった方がいいです。私は認定してもらえたので詳しい内容はわかりませんが、他の科目を受けながら実験をやるのは結構辛いです。

健康・体力つくり実習

体育ですね。受けてもいいと思いますが、多摩川運動場まで行く必要があるので移動が怠いと思います。徒歩だと片道20分程度だそうです。
私は認定してもらえたので詳しいことはわかりませんが、4,5年に体育があるなら受講して認定までもっていった方がいいです。

最後に

認定の優先度は、
基礎科学実験A,B>1,2年の必修>>>>>それ以外
です。

基礎科学実験は言わずもがなですが、1,2年の必修は特に前期科目を優先しましょう。授業を受けながら履修登録をしないといけないので時間割を組むのが難しくなります。科目によっては初回ガイダンスの参加が必須だったりします。気をつけましょう。
そういえば認定作業書類で誤字をすると認められないので気をつけましょう。 私はオペレーティングシステムをオペレーションシステムと書いていてダメだよって言われました。

この科目認定難しそうだよな〜と思っても諦めずに書類を出してみましょう。面談で認定してくれることもあります。実際、私は高専で化学をほとんどやっていなかったので化学科目の認定を諦めていましたが、化学概論第一と基礎科学実験Bの認定を勝ち取ることができました。(全くやっていないわけではなかったので)

認定作業は本当にアレなので、気を紛らわせながら頑張っていきましょう。私はガイダンス前にシアタス調布でボヘミアンラプソディーを観てから、ずっとQUEENの曲を聴きながら作業してました。
ジョジョのスタンドがよく洋楽から取られてるのは知っていましたが、吉良吉影キラークイーン、シアハートアタック、アナザーワンバイツァダストって全部QUEENだったんですね。


単位認定について何か聞きたいことがあれば@ykm_knにでもコンタクト取ってくれると力になれるかもしれません。が、基本スタンスとして面倒事には関わらないのでアドバイスくらいしかできないかもしれません。気が向いたらめちゃくちゃ助けることもあります。
追記3: 2000万稼がなきゃいけないので気が向くことはないと思います。