【イデアル格子勉強会 #1】m=3で理解する円分整数とイデアル

# 勉強会の概要

- 資料: https://www.iisec.ac.jp/proc/vol0006/arita14.pdf
- 暗号の会社にいるので、格子暗号に関して、普段数学を触らないビジネスサイドの人間も理解できるように定性的理解と可視化を大切にしました
- そのため数式の一般化は各自の努力にまかせて、円の3分整数(m=3)を用いて説明し概念を掴むことを目的とします
- m=3を用いることで次元が2次元となり、実軸-虚軸の複素平面(2次元)にキレイにマッピングすることができます。m=3のとき(正確に言うとm=6も)のときにしか、2次元で次元を揃えたマッピングはできませんが、いったんこの特性を利用してマッピングします
- 今回は例題1までの単元、イデアルの概念理解までを担当します


# 本日のゴール

[イデアル格子](https://www.iisec.ac.jp/proc/vol0006/arita14.pdf)における "2.円分整数" を理解する。具体的には以下の3つのポイントに関して概念を把握する。

- 円分整数は代数構造をもつ (足し算, 掛け算が可能)
- 円分整数は格子をなす
- 円分整数$g$ が生成するイデアル $I_g$ に含まれる円分整数の全体を考えると、それは $n$個のベクトル $g, \zeta g, \ldots, \zeta^{n-1} g$ が張る部分格子をなす。足し算も掛け算をもつ。

最後に、例題1を手触り感をもって理解できればOK

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/73207/d3fc1eab-8749-f0bb-ace1-ba5c8cea72c4.png)

# 資料の解説

## 事前準備: 円を3つに分ける複素数を考えてみよう

### オイラーの公式からスタート

円の3当分($m=3$) するとき $\theta = \frac{2 \pi}{m} = \frac{2 \pi}{3} (= 120^{\circ})$ となる。オイラーの公式で得られる値を$\zeta$とすると以下のようにかける

```math
\begin{eqnarray*}
\zeta = e^{i\theta} &=& \cos \theta + i\sin \theta \\
&=& \cos \left(\frac{2\pi}{3}\right) + i\sin \left(\frac{2\pi}{3}\right) \\
&=& -\frac{1}{2} + i\frac{\sqrt 3}{2}
\end{eqnarray*}
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/73207/ba1917e4-8499-5b7e-46ac-be3d3e3d8ea8.png)


### ζのべき乗は回転操作であり、円状をくるくる回る

この$\zeta$は3乗すると1になる。複素空間の回転動作と同様である。

$$\zeta^3 = e^{i(2\pi/3)3} = e^{2\pi i} = 1$$

つまり $\zeta^3 - 1 = 0$ となり これを 因数分解すると

$$(\zeta - 1)(\zeta^2 + \zeta + 1) = 0$$

これは$(\zeta - 1)$で割りきれるので、

$$\zeta^2 + \zeta + 1 = 0$$

これを使うと、0乗, 1乗, 2乗 ... としていくと値が循環していることが分かる

```math
\begin{align*}
\zeta^0 &= 1 \\
\zeta^1 &= \zeta \\
\zeta^2 &= -\zeta - 1 \\
\zeta^3 &= \zeta \cdot \zeta^2 = \zeta(-\zeta - 1) = -\zeta^2 - \zeta = -(-\zeta - 1) - \zeta = \zeta + 1 - \zeta = 1 \\
\zeta^4 &= \zeta^3 \cdot \zeta = 1 \cdot \zeta = \zeta \\
\end{align*}
```

```python
import numpy as np
import matplotlib.pyplot as plt

def plot_zeta_powers(m, p_num):
    # zetaの計算
    zeta = np.exp(2j * np.pi / m)  # ζ = e^(2πi/m)

    # ζのべき乗を計算
    powers = [zeta**n for n in range(1, m+1)]
    extra_power = zeta**p_num  # 追加で計算するζのべき乗

    # 座標の抽出
    x_vals = [z.real for z in powers]
    y_vals = [z.imag for z in powers]
    extra_x = extra_power.real
    extra_y = extra_power.imag

    # プロット
    plt.figure(figsize=(8, 8))
    plt.scatter(x_vals + [extra_x], y_vals + [extra_y], color='red')
    plt.plot([0, extra_x], [0, extra_y], color='blue')  # 原点からζ^p_numまでの線

    # 単位円の描画
    circle = plt.Circle((0, 0), 1, fill=False, color='green', linestyle='dotted')
    plt.gca().add_artist(circle)

    # 座標軸の設定
    plt.xlim(-1.5, 1.5)
    plt.ylim(-1.5, 1.5)
    plt.axhline(0, color='black',linewidth=0.5)
    plt.axvline(0, color='black',linewidth=0.5)
    plt.grid(color = 'gray', linestyle = '--', linewidth = 0.5)

    # ラベルの追加
    labels = [f'$\zeta^{n}$' for n in range(1, m+1)] + [f'$\zeta^{p_num}$']
    for i, txt in enumerate(labels):
        if i < m:
            plt.annotate(txt, (x_vals[i], y_vals[i]), textcoords="offset points", xytext=(10,-10), ha='center')
        else:
            plt.annotate(txt, (extra_x, extra_y), textcoords="offset points", xytext=(10,-10), ha='center')

    plt.title(f'Powers of $\\zeta$ on the Complex Plane for m={m}, line to $\zeta^{{p_num}}$')
    plt.xlabel('Real')
    plt.ylabel('Imaginary')
    plt.show()

# 例として m = 3 で zetaを2乗するとき
m = 3
p_num = 2
plot_zeta_powers(m, p_num)
```


## 円の3分整数

### べき乗の"くるくる回る性質" を使って、ζの多項式を変形すると・・

:::note
$\zeta$ の(一般次数) 多項式 $f(\zeta)$ は、$\zeta^2 = −ζ − 1$ であることを利用すれば、必ず $\zeta$ の一次式 $a_0 + a_1\zeta$ に変形することができる。
:::

例: $f(\zeta)$ = $4\zeta^{2} + 3\zeta + 1 = 4(-\zeta - 1) + 3\zeta + 1= -3 - \zeta$

この例の場合 $a_0 + a_1\zeta$ において:

- $a_0 = -3$
- $a_1 = -1$

となる。

### 円の3分整数の定義

$a_1$, $a_2$ を整数とすると円の3分整数は以下のように定義できる。

```math
a_0 + a_1\zeta
```

### 【特徴】 足し算と掛け算が可能 (代数構造を持つ)

```math
\begin{eqnarray*}
\text{足し算: } &(a_0 + a_1 \zeta) + (b_0 + b_1 \zeta) &=& &(a_0 + b_0) + (a_1 + b_1) \zeta \\
\text{掛け算: } &(a_0 + a_1 \zeta) \cdot (b_0 + b_1 \zeta) &=& &(a_0 b_0 - a_1 b_1) + (a_0 b_1 + a_1 b_0) \zeta
\end{eqnarray*}
```

### 【特徴】 円分整数はベクトルあるいは格子点と見なすこともできる

#### 円分整数の格子点

円の3分整数全体を $\mathbb{Z}[\zeta]$ とかくと円分整数はベクトルあるいは格子点と見なすこともできる。

```math
\mathbb{Z}[\zeta] = \left\{a_0 + a_1\zeta ~~~|~~~a_0, a_1\text{は整数} \right\}
```

つまり円分整数 $h = a_0 + a_1\zeta$に対して、$\zeta$に関する係数をならべると、格子点$(a_0, a_1)$を得る。

#### 円分整数の大きさを定義

円分整数hに対し、その大きさを考えることができる(この大きさ $ \parallel h \parallel $ は、複素数としての絶対値とは異なることに注意すること)

円の3分整数のときは以下のようにかける

```math
\parallel h \parallel = \sqrt{\left(a_0^{2} + a_1^{2}\right)}
```



```math
h = a_0 + a_1 \zeta  \Leftrightarrow \text{格子点 } (a_0, a_1)
```

#### 円分整数の可視化

Pythonとmatplotlibを使用して、円の3分整数の格子点をプロットすることが可能です。このケースでは、$\zeta$は $\ \zeta = e^{2\pi i/3} = -\frac{1}{2} + i\frac{\sqrt{3}}{2} $ と表現される複素数です。$ \mathbb{Z}[\zeta]$ の要素は $a_0 + a_1\zeta$ の形で、ここで $a_0$ と $a_1$ は整数です。

格子点 $(a_0, a_1)$ としてプロットする代わりに、各格子点に対応する複素数の位置をプロットすることができます。以下のコードはこのアイディアを実装したものです。ここでは、$ -10 $ から $ 10 $ の範囲で $ a_0 $ と $ a_1 $ の値を取り、対応する複素数の位置をプロットします。

```python
import numpy as np
import matplotlib.pyplot as plt

# ζの定義
zeta = -0.5 + np.sqrt(3)/2 * 1j

# 範囲を設定
range_min, range_max = -10, 10

# 格子点をプロット
plt.figure(figsize=(10, 10))
for a0 in range(range_min, range_max + 1):
    for a1 in range(range_min, range_max + 1):
        # a0 + a1*zeta に対応する複素数を計算
        z = a0 + a1 * zeta
        # 実部と虚部の取得
        x, y = z.real, z.imag
        # プロット
        plt.scatter(x, y, color='blue')

# プロット設定
plt.title("Lattice Points for $\mathbb{Z}[\\zeta]$, $\zeta = e^{2\pi i/3}$")
plt.xlabel("Real part")
plt.ylabel("Imaginary part")
plt.grid(True)
plt.axhline(0, color='black',linewidth=0.5)
plt.axvline(0, color='black',linewidth=0.5)
plt.xlim(-15, 15)
plt.ylim(-15, 15)
plt.gca().set_aspect('equal', adjustable='box')

plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/73207/7ef48688-8f15-16f3-087b-bff440b6d8a6.png)



## イデアル

### 【特徴】 円分整数の倍数はイデアル格子を生成

円分整数 $g = g_0 + g_1\zeta$ の**倍数**全体の集合$I_g$を**円分整数gが生成するイデアル**という

```math
I_g = \left\{a_0g + a_1\zeta g~~~|~~~a_0, a_1\text{は整数}\right\}
```

m=3のときの イデアル $I_g$ に含まれる円分整数 $h = a_0g + a_1\zeta g$ の全体は2個のベ
クトル $g, \zeta g$ が張る部分格子をなし、$h$はその格子点と考えることができる

以下はイデアルの例

- $g = 3 + 4\zeta$ は単に **俺が決めた!** 値
- $g$がきまれば$g\zeta$も計算できる
- 上2つの操作により、**新しい軸**が生成される(図中の点線)
    - $1g, 2g,3g....$
    - $1g\zeta, 2g\zeta, 3g\zeta ...$
- つまりイデアル格子が自動的に決定される
    - 図のように$1g$ と$1g\zeta$がなす格子を部分格子と言う

![イデアル格子](https://docs.google.com/drawings/d/e/2PACX-1vQj3SI3XD1odZ3oTEoCXnb9AbuySwUsNulHRYAI3uzjXjST-q4DgXqd5NbX4e9UrFHAkQmskcB11qj6/pub?w=712&h=673)


### 【特徴】 イデアルに含まれる円分整数どうしの足し算

イデアル Ig に含まれる円分整数どうしを足すと、またイデアル Ig に含まれる:

```math
h_1, h_2 \in I_g \implies h_1 + h_2 \in I_g
```

複素平面にマッピングしたときのイメージ。$g = 3 + 4\zeta$ は、単にサンプルとして "俺が決めた!" 値

![イデアル足し算](https://docs.google.com/drawings/d/e/2PACX-1vSfaZLdUWEFVtxVwtrGQlEDc4J_xVS38QJRyMaLl18QxQ_Sz60QUhjlv8q8nJ4i3UlUPIprCZlpOGge/pub?w=688&h=644)

### 【特徴】 イデアルに含まれる円分整数どうしの掛け算

```math
a \in \mathbb{Z}[\zeta], h \in I_g \implies ah \in I_g
```

複素平面にマッピングしたときのイメージ。はみ出しているが実際には、赤の点上にある。$g = 3 + 4\zeta$ は、単にサンプルとして "俺が決めた!" 値

![image.png](https://docs.google.com/drawings/d/e/2PACX-1vQC2w8_qLY2h18ftIuI9Gz9xHJJEP1JvrU6J-RCxIM4OpOOPM291xwlQ9WJSspAMxSiConuYGDMFzOI/pub?w=623&h=640)

# 例題1をみんなで計算してみよう

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/73207/d3fc1eab-8749-f0bb-ace1-ba5c8cea72c4.png)