数学書っぽく「定義→定理→証明→定義→・・・」と書いてもいいのですが，おそらく秒でブラウザバックされるため，
地の文：大雑把な定義やお気持ち＋例→論文中の議論を大雑把に理解したい方向け
折りたたみ：上記の厳密な定義→論文を厳密に理解したい方向け
の流れで書こうと思います．全て書くと見通しが悪くなってしまうためです．
地の文では，論文に出てくる記号・概念の意味やイメージを解説するので，これだけでも分かるように書く予定です．ただし，正確性は保証できないので，そこが気になる方は折りたたみを開いてチェックしてください．

突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください

また，以下の内容は共通で扱いません．

プログラマブルブートストラップの直感的な説明
プログラマブルブートストラップの発展過程やこの先どこへ向かうのか
プログラマブルブートストラップの実装に向けた話
ニューラルネットワークなどAI系への応用
美味しいラーメン屋の紹介

まず１と２に関しては，下記の記事が詳しいです．分かりやすい！

1と2のQiitaの記事

3についてもこちらの連載の記事が詳しいです（理論解説のため実装まで踏み込めない）．これも分かりやすい！

3のQiitaの記事

続いて4ですが，この原著論文の第５章を参考にしてください．
5は何なら僕に教えてください．

全４回通しでの目次

第１回（イマココ）

本論文全体の流れ
前提知識
今回出てくる予備知識のまとめ
2.1 Torus and Torus Polynomials
- Torus
- 加群
- 多項式環
- 既約多項式と円分多項式
- Torus上の多項式
2.2 Probability Distributions
- 離散一様分布と正規分布
- 実数から整数への丸め

第２回

今回出てくる予備知識のまとめ
Appendix A : Complexity Assumptions Over the Real Torus
- TLWEとTRLWE
3章前説
- 3章の流れ
- ギリシャ文字と花文字
- $\hat{\mathbb{Z}}$ と $\hat{\mathbb{T}}$
- 3章前説の議論
- 3章前説の議論の考察
3.1 Encoding/Decoding Messages
- lift
- Upper
- 3.1の議論
- 3.1の議論の考察

第2.5回（番外編）

なぜ番外編が必要なのか
今回出てくる予備知識のまとめ
GGSW方式とは
無限ノルム
Tensor積
gadget行列
gadget decomposition
GGSW方式のアルゴリズム
GGSW方式のアルゴリズムの具体例
これまでの議論の考察１
GGSW方式の暗号文の足し算
GGSW方式の暗号文同士の内積
これまでの議論の考察２

第３回

今回出てくる予備知識のまとめ
3.2 Description
- TFHE方式のアルゴリズム
- TFHE方式のアルゴリズムの具体例
- 無限ノルム
- TFHE方式のアルゴリズムの正当性
- 3.2の議論の考察
3.3 Leveled Operation
- Tensor積
- gadget行列
- gadget decompostion
- GGSW方式の概要
- TFHE方式の暗号文の足し算
- TFHE方式の暗号文のスカラー倍
- 結局 Leveled Operaion とは何か
- TFHE方式の暗号文とGGSW方式の暗号文の外積
- Cmuxゲート
- 3.3の議論の考察

第４回

この連載を読みやすくリメイクしたQiitaの記事
第１回：第１回
第２回：第２回
第３回：第３回

さて，今回は記念すべき（何の？）第１回目ということで，
2. Preliminaries
2.1 Torus and Torus Polynomials
2.2 Probability Distributions
を扱います．

具体的な内容としては，次のようになります:

本論文全体の流れ
前提知識
今回出てくる予備知識のまとめ
2.1 Torus and Torus Polynomials
- Torus
- 加群
- 多項式環
- 既約多項式と円分多項式
- Torus上の多項式
2.2 Probability Distributions
- 離散一様分布と正規分布
- 実数から整数への丸め

今回は本題というより，準備ということで，数学的な内容が多めです．本論文の議論の流れやこの記事を読むにあたっての前提知識にも触れます．
何に注意して議論を解説するかなどは次回整理します．
それでは早速見ていきましょう．

本論文全体の流れ

どういう背景や課題・モチベーションがあって，
どのようなアイディアのもとで，
どのような結果が得られたのか

を整理します．

背景・課題
完全準同型暗号を達成する暗号として格子暗号ベースが考えられています．
格子暗号は簡単には暗号文にノイズを付与することで，安全性を保証しており，
暗号文を何度も演算するとノイズが増大する問題は，ブートストラップと呼ばれる技術で解消できます．
このブートストラップを実用性のあるものにすべく，TorusベースのTFHE方式（提唱者の頭文字をとってCGGI方式とも）が考えられました．
しかし，このTFHE方式の暗号化では，暗号文に任意の演算，特に非線型演算( $\exp$ とか)を与えるのが難しいとされていました．

アイディア
従来のブートストラップにleveled operation（演算回数に制限をつける）で解決です

結果
暗号文で任意の演算が可能になりました．やったね！

それらを元に各章を整理すると，次のようになります:

1章：イントロ
2章：前提知識
3章：TFHE方式
4章：ブートストラップとプログラマブルブートストラップ
5章：Neural Network への応用

つまり，３章と４章の前半までが「準備段階」で，４章の後半が一番言いたいことになります．
ただ，発想自体は別に難しいものではなく，むしろ「準備段階」が一番難しいため，今回の記事を書くに当たったというわけです．

前提知識

なるべく丁寧に解説することは心がけますが，

（素朴）集合論（ $\neq$ 公理的集合論）：全射・単射・全単射・直積
線型代数：行列の和や積・行列式
確率・統計：確率分布・確率密度関数
代数：Abel群・可換環・体の定義
初等整数論：mod
計算量理論：クラスPとNP

ぐらいは前提知識とします（サイレント修正の可能性あり）．知らなくてもググればどうにかなるかもです．
他に必要なものは，論文解説で使用するものは本文中，補足で必要なものは折りたたみで必要になったときに定義します．

また，次の記号を使います（使わないものもあるかもですが）:

$\mathbb{N}$ : 自然数全体の集合，0を含む
$\mathbb{Z}$ : 整数全体の集合
$\mathbb{Q}$ : 有理数全体の集合
$\mathbb{R}$ : 実数全体の集合
$\mathbb{C}$ : 複素数全体の集合
$\mathbb{B} = \{0, 1 \}$
$x \overset{\#}{\leftarrow} X$ : 集合 $X$ から要素 $x$ をランダムに取る
Def : 定義
Thm : 定理

＊ランダムに取るときの記号は本当は$で出力したいのですが，なんか数式モードだと上手くいかない？ようなので#で代用します（有識者教えてください）

主に参考にする書籍を以下で挙げます（最後に載せているのと同じ）．ただ割と数学色が強いので，
線形代数と確率・統計は自分でやる
→代数と計算量理論は暗号の本を見る
が手っ取り早いのかなって思っています（あまりよく知らない）．

↓ステマではないです

集合論

初学者向け
集合と位相空間

かなりまとまっている本
集合と位相(増補新装版)(数学シリーズ)

線型代数

初学者向け
線型代数

数学書っぽい雰囲気を味わいたい方向け，あとは加群を見据えて単因子論をやりたい方向け
線型代数入門

確率・統計

実用性のコスパ的には一番良い気がします
統計学入門

代数

群の初学者向け（たぶん）
代数学1 群論入門

環・環上の加群・Galois理論の初学者向け（環以外は少し読みづらいかも）
代数学2　環と体とガロア理論

群・環・環上の加群を復習したい方むけ（初学はかなりきつそう）
代数入門(新装版): 群と加群 (数学シリーズ)

環上の加群（あまり読んでないです）
代数学〈2〉環上の加群 (大学数学の入門)

体・Galois理論の初学者向け（薄いけど例もきっちり書かれています）
代数学〈3〉体とガロア理論 (大学数学の入門)

＊環上の加群，は「ホモロジー代数」を扱った本でも良いと思います（僕はそれで読んだ）

初等整数論

上の代数学シリーズの数論版（代数もまとまっているのでこれだけで良い感はある()）
整数論1: 初等整数論からp進数へ

個人的にはこっちの方が好きです（僕の大学の先生方も関わっています）
初等整数論 ―数論幾何への誘い― (共立講座数学探検 6)

計算量理論

計算理論の基礎 [原著第2版] 2.計算可能性の理論

代数とか計算量理論が載っている暗号の本

マジの聖書（耐量子計算機暗号に多かれ少なかれ関わっている方はもちろん，数学的に量子計算や高機能暗号を捉えたい方に勧められます．量子計算機の共通鍵暗号への影響もちらっとだけ触れられていて，本当に痒いところに手が届く本です）
（ですが，計算量や代数は載っているもののかなりさらっと書かれているので，初学向けではないです）
耐量子計算機暗号

代数だけならつい最近にいい感じの本が出ましたね
暗号から学ぶ代数学 (数学のみかた,考え方)

以下は洋書ですが良い本が多いです
１冊目は「正統派」な本で，
２冊目は「代数」・３冊目は「計算量・ロジック」・４冊目は「アルゴリズムなどの手法」から暗号を眺める本です．
５冊目・６冊目は僕が勉強するときに使っていた（今でも読んでいる）本です

１冊目
暗号の授業をしろ，と言われたらこれを参照するかなと（古典的な内容は網羅されています）
Understanding Cryptography: A Textbook for Students and Practitioners

２冊目
ここの要望に応えてくれる本
代数・初等整数論も計算量も書かれていて，格子も割と充実しています，英語に抵抗のない暗号理論の初学者に１冊薦めるならこれです
An Introduction to Mathematical Cryptography (Undergraduate Texts in Mathematics)

３冊目
ロジックの視点から始まり，NL完全とかPPなど計算量の観点から眺める本（代わりに代数はあっさり）
Complexity Theory and Cryptology

４冊目
アルゴリズム以外も色々書いてあります，体の拡大とか必要なんか？（計算量の記述が少ないのが惜しい）
Cryptography Made Simple (Information Security and Cryptography)

５冊目
「one-way」・「psueudorandom」・「zero-knowledge」がかなり丁寧に書かれていて，これらを読むだけでも相当な実力になるかと（お陰でくどいし長い）
Foundations of Cryptography v1

６冊目
５冊目の続き，徹底的にセキュリティを定式化するって感じです（上もそうですが，厳密に暗号を扱いたい方向けかなと）
Foundations of Cryptography

今回出てくる予備知識のまとめ

前提知識以外の数学的な予備知識は適宜まとめてはいますが，一覧がほしい方もいらっしゃるかもなので，先にまとめます．折りたたみで出てくる概念のみを対象で，本文中に出てくるものは目次を参考にしてください．
順番は今回の記事で出てくる順で，内容は定義だけざっと並べています．

同値類と代表元
群準同型・環準同型
ImとKer
群準同型定理・環準同型定理
濃度
整域
可約・既約
イデアル

同値類と代表元

$\underline{\mathrm{Def(二項関係， binary \ relation)}}$
集合 $X$ 上の二項関係とは，直積集合 $X \times X$ の部分集合 $R$ のことであり， $(x, y) \in R$ のとき， $x, y$ は関係 $R$ があるといい， $x \sim y$ と書く．

$\underline{\mathrm{Def(同値関係, equivalence \ relation)}}$
集合 $X$ 上の二項関係 $\sim$ が次の3条件を満たすとき， $\sim$ を集合 $X$ 上の同値関係という．

\begin{align*} & \bullet \ x \in X \ \text{について} \ x \sim x \\ & \bullet \ x, y \in X \ \text{について} \ x \sim y \Rightarrow y \sim x \\ & \bullet \ x, y, z \in X \ \text{について} \ x \sim y \ \text{かつ} \ y \sim z \Rightarrow x \sim z \end{align*}

$\underline{\mathrm{Def(同値類, equivalence \ class)}}$
集合 $X$ 上の同値関係 $\sim$ と $x \in X$ について，次の $X$ の部分集合 $C_{X}(x)$ を $x$ の同値類という:

\begin{align*} C_{X}(x) = \{ y \in X \ | \ x \sim y \} \end{align*}

また， $x$ を $C_{X}(x)$ の代表元という．

$\underline{\mathrm{Def(剰余類, residue \ class)}}$
$G$ をAbel群， $H$ を $G$ の部分群（ $G$ の部分集合であって， $G$ の演算で閉じている群のことです）とする． $x, y \in G$ とする．
$x^{-1} y \in H$ のとき， $x \sim y$ とすると， $\sim$ は同値関係になる．このとき， $x \in G$ の同値類を $x H$ と書いて， $x$ の $H$ による剰余類といい， $G / H$ で剰余類の集合を表す．

群準同型・環準同型

$\underline{\mathrm{Def(群準同型, group \ homomorphism)}}$
$(G, \ast), (G^{\prime}, \ast^{\prime})$ を群とするとき，写像 $f : G \rightarrow G^{\prime}$ が準同型であるとは，次の2つの条件を満たすことである:

\begin{align*} & \bullet \ f(g \ast h) = f(g) \ast^{\prime} f(h) \hspace{10pt} g, h \in G \\ & \bullet \ f(1_G) = 1_{G^{\prime}} \end{align*}

$\underline{\mathrm{Def(環準同型, ring \ homomorphism)}}$
$(R, +, \cdot), (R^{\prime}, +^{\prime}, \cdot^{\prime})$ を環とするとき，写像 $f : R \rightarrow R^{\prime}$ が準同型であるとは，次の3つの条件を満たすことである:

\begin{align*} & \bullet \ f(g + h) = f(g) +^{\prime} f(h) \hspace{10pt} g, h \in G \\ & \bullet \ f(g \cdot h) = f(g) \cdot^{\prime} f(h) \hspace{10pt} g, h \in G \\ & \bullet \ f(1_R) = 1_{R^{\prime}} \end{align*}

ImとKer

$\underline{\mathrm{Def(ImとKer, Image \ and \ Kernel)}}$
$(R, +, \cdot), (R^{\prime}, +^{\prime}, \cdot^{\prime})$ を環， $f : R \rightarrow R^{\prime}$ を環準同型とするとき， $\mathrm{Im} \ f$ と $\mathrm{Ker} \ f$ を次のように定める:

\begin{align*} \mathrm{Im} \ f & = \{ y \in R^{\prime} \ | \ x \in R, f(x) = y \} \\ \mathrm{Ker} \ f & = \{ x \in R \ | \ x \in R, f(x) = 0 \} \end{align*}

群準同型定理・環準同型定理

$\underline{\mathrm{Thm(群準同型定理, fundamental \ homomorphism \ thorem)}}$
$(G, \ast), (G^{\prime}, \ast^{\prime})$ を群で，写像 $f : G \rightarrow G^{\prime}$ が準同型のとき次が成り立つ:

\begin{align*} G / \mathrm{Ker} f \cong \mathrm{Im} f \end{align*}

$\underline{\mathrm{Thm(環準同型定理, fundamental \ homomorphism \ thorem)}}$
$R, R^{\prime}$ を環で，写像 $f : R \rightarrow R^{\prime}$ が準同型のとき次が成り立つ:

\begin{align*} R / \mathrm{Ker} f \cong \mathrm{Im} f \end{align*}

濃度

$\underline{\mathrm{Def(濃度, cardinality)}}$
集合 $X$ から集合 $Y$ へ全単射が存在するとき， $X$ と $Y$ は濃度が等しい，という．

整域

$\underline{\mathrm{Def(整域, integral \ domain)}}$
$R$ を環で $a, b$ を $R$ の0でない要素とするとき， $ab \neq 0$ が常に成り立つならば， $R$ は整域であるという．

体ならば整域

$F$ を体として，整域でないと仮定します．つまり， $a, b$ 共に0でなく， $ab = 0$ になるような $a, b$ が存在したとします．
このとき， $a$ $F$ の元で0ではないので逆元 $a^{-1}$ が存在します．これを $ab = 0$ の両辺に左から掛けると $b = 0$ を得ます．しかし， $b$ も0ではないのでこれは矛盾します．
よって示されました．

可約・既約

$\underline{\mathrm{Def(可約・既約, reducible \ and \ irreducible)}}$
$R$ を整域， $0 \neq a \in R$ を任意に取る．次の２つの条件を満たすとき， $a$ は既約である，という．

\begin{align*} & \bullet \ a \text{は逆元を持たない} \\ & \bullet \ b, c \in R \setminus \{0\}, a = b c \ \text{なら} \ b \ と \ c \ \text{のいずれかは逆元を持つ} \end{align*}

そうでないとき， $a$ は可約である，という．

初めの条件を $a$ は単元である，と言ったりします．

既約多項式

$\underline{\mathrm{Def(既約多項式, irreducible \ polynomial)}}$
$R$ を整域とするとき，多項式環 $R[X]$ 上で既約な元を既約多項式という．

円分多項式

$\underline{\mathrm{Def(n乗根と原始n乗根, nth \ root \ and \ primitive \ nth \ root)}}$
$n$ を正整数とするとき， $z \in \mathbb{C}$ であって， $z^n = 1$ を満たす $z$ を1の $n$ 乗根という．
$\zeta$ が1の $n$ 乗根であり， $0 < m < n$ で $\zeta^m \neq 1$ を満たすとき， $\zeta$ を1の原始 $n$ 乗根という．

$\underline{\mathrm{Def(原始n乗根を用いた円分多項式, cyclotomic \ polynomial)}}$
$n$ を正整数， $\zeta_n \in \mathbb{C}$ を1の原始 $n$ 乗根とするとき， $n$ 次の円分多項式 $\Phi_n(X)$ は次のように表せる:

\begin{align*} \displaystyle \Phi_n(X) = \prod_{1 \leq i \leq n, iとnは互いに素} (X - \zeta_n^i) \end{align*}

イデアル

$\underline{\mathrm{Def(イデアル, ideal)}}$
$R$ を可換環， $I$ を $R$ の部分集合とするとき， $I$ が $R$ のイデアルとは，次の2つの条件を満たすことである:

\begin{align*} & \bullet \ a, b \in I \Rightarrow a + b \in I \\ & \bullet \ a \in I, c \in R \Rightarrow ac (= ca) \in I \\ \end{align*}

Torus

トーラスと聞くと何を思い浮かべますか？

ドーナツ（本当は浮き輪）の形
$S^1$ と $S^1$ の直積に・・・
ラーメンとか聞いたし，ポン・デ・リング食べたい・・・

など色々とあると思いますが，分野が暗号ということで，幾何的なイメージよりも代数的な操作を意識します．

幾何的な視点から代数に移す話

浮き輪とかは３次元空間内の２次元トーラスで，上で書いた $S^1$ とは複素平面上での単位円周のことです．
一般には $n$ 次元トーラスを考えたりします．以下では， $n = 1$ としましょう．

$n = 1$ では，複素平面上での単位円周を表すので，原点からの距離が1，つまり，絶対値が1である複素数全体の集合と考えられます．すると

\begin{align*} \{ z \in \mathbb{C} \ | \ | z | = 1 \} \end{align*}

このように書けます．複素数の極座標表示をご存知の方なら，

\begin{align*} \{ e^{\sqrt{-1} \theta} \ | \ \theta \in \mathbb{R} \} \end{align*}

だったり（この集合に $\theta$ の和で演算を定めた群を1次ユニタリ群といいます），特殊直交群をご存知の方なら，

\begin{align*} \{ \begin{pmatrix} \cos \theta & - \sin \theta \\ \sin \theta & \cos \theta \end{pmatrix} \ | \ \theta \in \mathbb{R} \} \end{align*}

で表せます．色々書きましたが，重要なことは，
円周上の点は $x$ 軸から見た角度 $\theta$ というパラメータ1つだけで表せる
ということです．
これによって，円周という幾何的な対象をパラメータ1つで議論することができました．

だいぶ大雑把ではありますが，Torus（群）の理解は次で十分でしょう．
Torusとは0以上1未満の実数全体で，和を考えるときは整数部分は無視する

2πを無視する過程

少し大雑把な議論をしますが，後に出てくる「同値類と代表元」と「このように表せる理由」の2つの折りたたみで正当化します．感覚的にはこれで十分です．

例えば $x$ 軸から見て $\frac{\pi}{2}$ (90°)だけ回転した点と $\frac{5 \pi}{2}$ (450°)だけ回転した点はどちらも $(0, i)$ を表します．
この例から分かる通り， $2 \pi$ の(360°)整数倍の違いは点の位置に影響しません．

すると， $\theta$ は実数全体を動く必要はなく， $\theta \ \mathrm{mod} \ 2 \pi \mathbb{Z}$ ( $2 \pi$ の整数倍の違いは考えない)とすればOKです．また，直前の綴じ込みから $\theta$ さえ分かれば，円周上の位置はわかるため，以降は $\theta \ \mathrm{mod} \ 2 \pi \mathbb{Z}$ で考えます．

この $\theta \ \mathrm{mod} \ 2 \pi \mathbb{Z}$ という元が属する集合が $\mathbb{R} / 2 \pi \mathbb{Z}$ です．ここまでの議論から， $\mathbb{R} / 2 \pi \mathbb{Z}$ は，0以上2 $\pi$ 未満の実数全体で，和を考えるときは整数部分は無視する，と見なせます．
上で出てきた
Torusとは0以上1未満の実数全体で，和を考えるときは整数部分は無視する
に随分近くなりました．

そして，ここに出てくる2 $\pi$ は無視することができます．それは $\theta$ を $2 \pi \theta$ と考えればいいからです．2 $\pi$ という定数は気にしなくていいことになります．
最終的には $\mathbb{R} / \mathbb{Z}$ という集合で考えればよく，その元は $\theta \ \mathrm{mod} \ \mathbb{Z}$ となり，大雑把には
0以上1未満の実数全体で，和を考えるときは整数部分は無視する
と考えることができます．

最後に出てくる $\mathbb{R} / \mathbb{Z}$ で以降はTorusを定義します．

そんなこんなで，厳密には次のように定義します．

$\underline{\mathrm{Def(Torus)}}$
Torus とは $\mathbb{R} / \mathbb{Z}$ なる集合のことであり， $\mathbb{T}$ と表す．
この集合は，0以上1未満の実数全体の集合とみなせて， $x, y \in \mathbb{T}$ に対して，演算 $+$ が $x + y \ \mathrm{mod} \ 1$ のようにして定まっている．
$(\mathbb{T}, +)$ はAbel群になっている

$x, y \in \mathbb{T}$ に対して，とは， $\mathbb{T}$ の任意の変数 $x, y$ に対して，という意味です．

「みなせて」の部分について
$x$ を0以上1未満の実数とするとき，それに対応する $\mathbb{T}$ の元 $\overline{x}$ は， $\{ x + n \ | \ n \in \mathbb{Z} \}$ という集合を表しています．

ただし， $\overline{x}$ という集合を扱うところを， $\mathbb{T}$ の元として，もしくは， $\mathbb{T}$ 内での足し算を扱う際にはその集合の元 $x$ ，特に $x \ \mathrm{mod} \ 1$ で議論を進めても問題ないので，あまり深く意識する必要はありません．
要するに，小数点以下が一致する実数は１つの集合にまとめて，その集合を1つの実数とみなす，ということです．

同値類と代表元

同値類とは同値関係に属する集合のことです．そのためにまず一般的な「二項関係」を定義して，その例として「同値関係」を紹介します．剰余類とは同値類の例です．

抽象的な定義が続きますが，暗号などで馴染みのある $\mathbb{Z} / 5 \mathbb{Z}$ 辺りを例に説明します．

$\underline{\mathrm{Def(二項関係, binary \ relation)}}$
集合 $X$ 上の二項関係とは，直積集合 $X \times X$ の部分集合 $R$ のことであり， $(x, y) \in R$ のとき， $x, y$ は関係 $R$ があるといい， $x \sim y$ と書く．

例えば， $\mathbb{Z}$ に対して， $x \sim y \Leftrightarrow x = y$ と定めると， $5 = 5$ ですが， $5 \neq 4$ です．このとき， $5 \sim 5$ ですが， $5 \nsim 4$ と書くわけです．

$\underline{\mathrm{Def(同値関係, equivalence \ relation)}}$
集合 $X$ 上の二項関係 $\sim$ が次の3条件を満たすとき， $\sim$ を集合 $X$ 上の同値関係という．

\begin{align*} & \bullet \ x \in X \ \text{について} \ x \sim x \\ & \bullet \ x, y \in X \ \text{について} \ x \sim y \Rightarrow y \sim x \\ & \bullet \ x, y, z \in X \ \text{について} \ x \sim y \ \text{かつ} \ y \sim z \Rightarrow x \sim z \end{align*}

先ほどの $x \sim y \Leftrightarrow x = y$ は当然ですが同値関係です．また， $\mathbb{Z}$ 上の $x \sim y \Leftrightarrow x \equiv y \ \mathrm{mod} \ 5$ も同値関係です．

$\underline{\mathrm{Def(同値類, equivalence \ class)}}$
集合 $X$ 上の同値関係 $\sim$ と $x \in X$ について，次の $X$ の部分集合 $C_{X}(x)$ を $x$ の同値類という:

\begin{align*} C_{X}(x) = \{ y \in X \ | \ x \sim y \} \end{align*}

また， $x$ を $C_{X}(x)$ の代表元という．

例えば， $\mathbb{Z}$ 上の同値関係 $x \sim y \Leftrightarrow x \equiv y \ \mathrm{mod} \ 5$ について，

\begin{align*} C_{\mathbb{Z}}(0) & = \{ y \in X \ | \ 0 \sim y \} = \{ \cdots, -10, -5, 0, 5, 10, \cdots \} \\ C_{\mathbb{Z}}(1) & = \{ y \in X \ | \ 1 \sim y \} = \{ \cdots, -9, -4, 1, 6, 11, \cdots \} \\ C_{\mathbb{Z}}(2) & = \{ y \in X \ | \ 2 \sim y \} = \{ \cdots, -8, -3, 2, 7, 12, \cdots \} \\ C_{\mathbb{Z}}(3) & = \{ y \in X \ | \ 3 \sim y \} = \{ \cdots, -7, -2, 3, 8, 13, \cdots \} \\ C_{\mathbb{Z}}(4) & = \{ y \in X \ | \ 4 \sim y \} = \{ \cdots, -6, -1, 4, 9, 14, \cdots \} \end{align*}

ですね．ちなみに $C_{\mathbb{Z}}(0) = C_{\mathbb{Z}}(-5) = C_{\mathbb{Z}}(5)$ ですし， $\displaystyle \mathbb{Z} = C_{\mathbb{Z}}(0) \bigcup C_{\mathbb{Z}}(1) \bigcup C_{\mathbb{Z}}(2) \bigcup C_{\mathbb{Z}}(3) \bigcup C_{\mathbb{Z}}(4)$ となっています．
$\mathbb{Z}$ は $C_{\mathbb{Z}}(n)$ という集合の集合 というイメージです．

例えば，0 は $C_{\mathbb{Z}}(0)$ の代表元ですし，1 は $C_{\mathbb{Z}}(1)$ の代表元ですが，
-5 も $C_{\mathbb{Z}}(0)$ の代表元ですし，11 も $C_{\mathbb{Z}}(1)$ の代表元です．

＊上の定義は「Abel」ではなく一般の群でもOKです．ただ，左剰余類とかは使わないのでカットしました．

上の定義で $G = \mathbb{Z}, H = 5 \mathbb{Z}$ としたときの $G / H$ こそがよく見かける $\mathbb{Z} / 5 \mathbb{Z}$ です．
＊厳密には「Abel群→可換環，部分群→イデアル」に変更した場合です

そんなこんなで厳密には $\mathbb{Z} / 5 \mathbb{Z}$ の元は，整数ではなく集合です．
ただし，習いたてだと $[n] \in \mathbb{Z} / 5 \mathbb{Z}$ とか $\overline{n} \in \mathbb{Z} / 5 \mathbb{Z}$ みたいな記号を使うこともあり，「これを元と同一視する」みたいな記述もあったりします．それはのちに補足します．

このように表せる理由

これは $f : \mathbb{R} \rightarrow [0,1)$ で上記の演算で $f(x) = x \ \mathrm{mod} \ 1$ とすると $f$ は全射準同型なので，準同型定理から $\mathbb{R} / \mathbb{Z} \simeq [0, 1)$ となるからです．

とだけ書いて分かる方は以下の折りたたみの内容は飛ばしてください．また，必要な概念は結構多かったので，最後にまとめて紹介しています．

f : \mathbb{R} \rightarrow [0,1)

について， $f(x) = x \ \mathrm{mod} \ 1$ と定めます．例えば $f(3.14) = 0.14$ です．

チェックすべき項目は，

$f$ の準同型性
$f$ の全射性
準同型定理を用いるとどうなるか

これら３つです．慣れない方は最後の折りたたみを参考にしながら，証明を追ってみてください．

準同型

まず， $f$ が準同型になっていることを確認します．これは，

\begin{align*} \forall x, y \in \mathbb{R} \hspace{10pt} f(x + y) &= f(x) + f(y) \\ \forall x \in \mathbb{R}, \forall c \in \mathbb{Z} \hspace{10pt} f(cx) &= c f(x) \end{align*}

の２つを確認すればOKです．前半は左辺が $f(x + y) = (x + y) \ \mathrm{mod} \ 1$ となり，右辺が $f(x) + f(y) = ((x \ \mathrm{mod} \ 1) + (y \ \mathrm{mod} \ 1)) \ \mathrm{mod} \ 1 = (x + y) \ \mathrm{mod} \ 1$ となるので，なり足ります．
後半は左辺が $f(cx) = cx \ \mathrm{mod} \ 1$ で，右辺が $c \cdot (x \ \mathrm{mod} \ 1) \ \mathrm{mod} \ 1$ となるので，これも成り立ちます．

全射

次に $f$ が全射になっていること，この場合，任意の $a \in [0,1)$ に対して， $x \in \mathbb{R}$ で $f(x) = a$ になるような $x$ が存在するかを考えます．
これは $x = a$ が該当するので，これもOKです．

準同型定理

以上から $f$ が全射準同型なので，準同型定理から $\mathbb{R} / \mathrm{Ker} f \simeq \mathrm{Im} f = [0,1)$ が成り立ちます． $\mathrm{Ker} f$ とは送った先が0になる元全体のことだったので，今回なら小数部分が0になる $x$ のことです．小数部分がちょうど0になる実数全体，ということで，これは整数全体を表します．

以上で示されました．

この綴じ込みで必要な定義や定理

初めに「群準同型・環準同型」を扱い，その後に「ImとKer」で，最後に「群準同型定理・環準同型定理」を紹介します．

準同型は「演算の構造を保つ」写像のことで，写像によってImやKerといった扱いやすい集合を導入できるのですが，準同型定理（第一同型定理）でそれらの関係式を示します．

群準同型・環準同型

\begin{align*} & \bullet \ f(g \ast h) = f(g) \ast^{\prime} f(h) \hspace{10pt} g, h \in G \\ & \bullet \ f(1_G) = 1_{G^{\prime}} \end{align*}

$\ast$ と $\ast^{\prime}$ は異なっても良いことに注意してください．上の証明でも $\ast = +$ ですが， $\ast^{\prime} = + \ \mathrm{mod} \ 1$ になっています．
他の例としては $(\mathbb{R}, +)$ から $(\mathbb{R}_{> 0}, \cdot)$ で $f(x) = e^x$ と定める（\mathbb{R}_{> 0} は正の実数全体の集合）と， $f$ は群準同型になっています．実際， $e^0 = 1$ で単位元が移っていますし， $f(x + y) = e^{x + y} = e^x \cdot e^y = f(x) \cdot f(y)$ となっています．
同様に $(\mathbb{R}_{> 0}, \cdot)$ から $(\mathbb{R}, +)$ で $f(x) = \log \ x$ と定めると， $f$ は群準同型になっています．

環準同型は上の定義を環バージョンにしたものです．

\begin{align*} & \bullet \ f(g + h) = f(g) +^{\prime} f(h) \hspace{10pt} g, h \in G \\ & \bullet \ f(g \cdot h) = f(g) \cdot^{\prime} f(h) \hspace{10pt} g, h \in G \\ & \bullet \ f(1_R) = 1_{R^{\prime}} \end{align*}

ImとKer

Imは全射・Kerは単射に関わってきます．以下は環準同型の場合で定義しますが，群準同型の場合でも同じです．

\begin{align*} \mathrm{Im} \ f & = \{ y \in R^{\prime} \ | \ x \in R, f(x) = y \} \\ \mathrm{Ker} \ f & = \{ x \in R \ | \ x \in R, f(x) = 0 \} \end{align*}

つまり， $\mathrm{Im} \ f$ は $R^{\prime}$ の部分集合（実はイデアルになっている）であって， $R$ の $f$ による写り先と考えられます．また， $\mathrm{Ker} \ f$ は $R$ の部分集合（これもイデアルになっている）であって，移り先が0に向かうものと考えられます．

群準同型定理・環準同型定理

全射な準同型は，元の集合を $\mathrm{Ker} f$ で割ったものが行き先と同型になる，という定理です．
線型代数で次元定理というのをやったことがある方は，それが群や環でも似たようなことが言える，という話です．

\begin{align*} G / \mathrm{Ker} f \cong \mathrm{Im} f \end{align*}

第一同型定理なんて言ったりします（使ったことない）．
特に全射であれば $\mathrm{Im} f \cong G^{\prime}$ ですので， $G / \mathrm{Ker} f \cong G^{\prime}$ が成り立ちます．

$\underline{\mathrm{Thm(環準同型定理, fundamental \ homomorphism \ thorem)}}$
$R, R^{\prime}$ を環で，写像 $f : R \rightarrow R^{\prime}$ が準同型のとき次が成り立つ:

\begin{align*} R / \mathrm{Ker} f \cong \mathrm{Im} f \end{align*}

さて， $f : \mathbb{Z} \rightarrow \{0, 1, 2, 3, 4\}$ で $f(x) = x \ \mathrm{mod} \ 5$ なる環準同型 $f$ を考えてみましょう．
このとき $f$ は全射です．なぜなら $x = 0, 1, 2, 3, 4$ の場合で尽くせるからです．
また，上の環準同型定理から $\mathbb{Z} / \mathrm{Ker} f \cong \mathrm{Im} f$ が成り立ち， $f$ は全射だったので， $\mathrm{Im} f = \{0, 1, 2, 3, 4\}$ です．
$\mathrm{Ker} f$ はどうなるかというと， $f(x) = x \ \mathrm{mod} \ 5$ で $f(x) = 0$ になる $x$ の集合ですから，それは5の倍数全体の集合，つまり， $5 \mathbb{Z}$ となります．
よって， $\mathbb{Z} / 5 \mathbb{Z} \cong \{0, 1, 2, 3, 4\}$ となり，特に体となります．

また， $\mathbb{T}$ は初めに書いたように「0以上1未満の実数全体の集合」なので無限集合です．

濃度

有限集合の「個数」の概念を無限集合に拡張した「濃度」という概念を紹介します．

$\underline{\mathrm{Def(濃度, cardinality)}}$
集合 $X$ から集合 $Y$ へ全単射が存在するとき， $X$ と $Y$ は濃度が等しい，という．

有限集合の場合は単に個数です．数列は写像なので，有限集合は有限個の数列と見ることができるからです．

さて，無限集合の場合は直感には反するような色々と面白いことが知られています．証明は全て省略しますが，下記の事実が知られています:

$\mathbb{N}$ と $\mathbb{Z}$ の濃度は等しい
$\mathbb{Z}$ と $\mathbb{Q}$ の濃度は等しい
しかし， $\mathbb{Q}$ と $\mathbb{R}$ の濃度は等しくない
よって， $\mathbb{N}$ と $\mathbb{R}$ の濃度は等しくない
$\mathbb{R}$ と $[0, 1) \subset \mathbb{R}$ の濃度は等しい

よって，0以上1未満の実数全体の集合と実数全体の集合の濃度は等しく（特に $\mathbb{N}$ とは等しくない），無限集合であることがこのことからも分かります．

Z / 5Z との違い

皆さんなら以下の主張にどう答えますか？
「 $\mathbb{Z} / 5 \mathbb{Z}$ において $\mathbb{Z}$ は整数全体の集合だから無限集合で， $5 \mathbb{Z}$ は5の倍数全体の集合だからこちらも無限集合．一方で， $\mathbb{Z} / 5 \mathbb{Z}$ は有限集合になる．
$\mathbb{R}$ も $\mathbb{Z}$ もどちらも無限集合だし， $\mathbb{R} / \mathbb{Z}$ は有限集合になるんじゃないの？」

答え

簡潔には「 $\mathbb{R}$ は $\mathbb{Z}$ より濃度が大きいから」と言えます．

上の「濃度」の畳み込みから $\mathbb{Z}$ と $\mathbb{R}$ の濃度は等しくない，ことが分かりますが，これは $\mathbb{R}$ の方が $\mathbb{Z}$ より濃度が大きいことを指します．
＊集合 $X$ が集合 $Y$ より濃度が大きい，とは， $X$ から $Y$ に向かう写像で全射なものは存在するが，単射なものは存在しない，ということです

そして，濃度が大きい集合を小さい集合で割っても，大きい濃度のままだからです．
これは $\mathbb{R} / \mathbb{Z} \cong X$ で $X$ が有限集合とすると， $\mathbb{R} \cong \mathbb{Z} \oplus X$ が成り立ちます． $\oplus$ は直和を表しますが，大雑把には直積と同じようなものと思っていただけたら大丈夫です．
すると， $X$ は有限集合ですから， $\mathbb{Z} \oplus X$ の濃度は $\mathbb{Z}$ と等しくなります．しかし， $\mathbb{Z}$ と $\mathbb{R}$ の濃度は等しくないためこれは矛盾します．

同様の理由で $X$ が可算無限の場合も矛盾します．可算無限の直積は可算無限になるからです．

ちなみに，同じ濃度の集合で割っても濃度が小さくなるとは限らないので注意してください．例えば， $\mathbb{Q} / \mathbb{Z}$ を考えると，確かに $\mathbb{Z}$ も $\mathbb{Q}$ も可算無限ですが， $\mathbb{Q} / \mathbb{Z}$ も可算無限であることが知られています．

上記で $\mathbb{T}$ 内の足し算を定義しましたが，一方で $\mathbb{T}$ 内の掛け算は「上手くいかない」ので，実用上では考える必要がありません．

トーラス内の掛け算

色々と書いていますが，トーラス内の掛け算は定義できないわけではないことを認識してくださればスキップしても構いません．well-defined をご存知の方は最後だけチラ見してださい．

集合 $S$ 上の2項演算 $\ast$ とは， $S$ の任意の元 $x, y$ に対して， $x \ast y$ が $S$ に含まれるものでした．さっきの定義風に書くと，次のようになります:

\ast : S \times S \ni (x, y) \mapsto x \ast y \in S

さて，これを元にトーラス内の掛け算とは，足し算をベースにすると，
$\mathbb{T}$ の任意の元 $x, y$ に対して， $x \cdot y$ が $\mathbb{T}$ に含まれるかどうか
を考えればいいわけです．

そして，実際に含まれることを確認しましょう．まず足し算の場合はどうだったかを思い返します．
分かりやすくするために，剰余類などの言葉を使って足し算の定義をリメイクします．

$\underline{\mathrm{Def(Torusの足し算)}}$
$x, y \in \mathbb{R}$ に対して，それらの $\mathbb{Z}$ による剰余類を $\overline{x}, \overline{y} \in \mathbb{T}$ として， $\overline{x} + \overline{y} = \overline{x + y \ \mathrm{mod} \ 1}$ と定める．

すると，Torusの掛け算を定義しようと思うと，自然と次のように考えられるはずです．

$\underline{\mathrm{Def(Torusの掛け算)}}$
$x, y \in \mathbb{R}$ に対して，それらの $\mathbb{Z}$ による剰余類を $\overline{x}, \overline{y} \in \mathbb{T}$ として， $\overline{x} \cdot \overline{y} = \overline{x \cdot y \ \mathrm{mod} \ 1}$ と定める．

しかし，２つの定義には決定的な違いがあります．それが「well-defined」と呼ばれるものです．
well-defiend そのものには触れませんが，代表元の取り方について話をします．

問題となる箇所について初めに書いておきます．それは
$x, y$ を定めると， $\overline{x}, \overline{y}$ が対応し， $\overline{x}$ と $\overline{y}$ の演算は $x$ と $y$ で定まる
というところです．

何のこっちゃって思うかもしれませんが， $x, y$ の取り方に任意性があるのが少しまずいのです．今回だと
$\overline{x}$ と $\overline{y}$ の演算で $x$ と $y$ から出力される結果（仮に $a$ とします）と $x - 10$ と $y + 4$ から出力される結果（仮に $b$ とします）が異なる
つまり， $\overline{x}$ と $\overline{y}$ の演算結果は $a$ のときもあれば $b$ のときもある
みたいなことが起こると，それは意味のある定義なの？っていうことです．

今回での，演算が「well-defined」とは，「代表元の取り方によらない（依存しない）」ことを示す必要があります．

というわけでまず足し算から確かめましょう． $m, n$ を整数として， $\overline{x}, \overline{y}$ の代表元として $x + m$ と $y + n$ を取ります．
すると， $r = (x + m) + (y + n) = x + y \ \mathrm{mod} \ 1$ ですから， $\overline{r} = \overline{x + y}$ が成り立ち，無事に代表元の取り方によらないことが分かりました．

続いて掛け算です． $m, n$ を整数として， $\overline{x}, \overline{y}$ の代表元として $x + m$ と $y + n$ を取ります．
すると， $r = (x + m) \cdot (y + n) = x y + x n + m y \ \mathrm{mod} \ 1$ ですから， $\overline{r} = \overline{x \cdot y}$ が成り立つとは限りません．
例えば， $0.4 \cdot 0.8 = 0.32 \ \mathrm{mod} \ 1$ ですが， $1.4 \cdot 1.8 = 0.52 \ \mathrm{mod} \ 1$ です．つまり，代表元の取り方によって， $\overline{0.4} \cdot \overline{0.8}$ の結果が異なります．

まとめると，
トーラス内の足し算は定義できるし，well-defined なので，元っぽく足し算を扱っても許される
けど，トーラス内の掛け算は定義できるが，well-defined ではない（ill-defined と言ったり言わなかったり）ので，元っぽく掛け算を扱うことは許されない
ということになります．

ここで，今後 $\mathbb{T}$ での演算は $\mathrm{mod} 1$ ではなく，次のように表記します:

0.3 + 0.8 = 0.1 \ \mathrm{in} \ \mathbb{T}

なぜ上記の表記をするか

以下の表記をよく見かけます:

0.3 + 0.8 = 1.1 \equiv 0.1 \ \mathrm{mod} \ 1

これは個人の感想ですが，0.3 や 0.8 が見えた時点で代表元を0以上1未満に制限しているのかなと思ってしまうのに，1.1 が出てくるのはなんだかなって思います．
オーバーフローみたいな感じです．実際には違うので，本当に個人的なあれですが．

0.3 + 0.8 = 0.1 \ \mathrm{mod} \ 1

こう書くのはOKです（そもそもこのように定義しています）が，毎回 mod を書くのが面倒なのと，どこの世界での演算なのかをはっきりさせることを意識して，in $\mathbb{T}$ を使います．

半群について，群の定義で「演算で閉じている・結合則・単位元の存在性・逆元の存在性」の４つを満たす必要がありますが，始めの２つのみを満たしているのが半群で，始めの３つを満たしているものをモノイドといいます．
ちなみにですが，半群やモノイドを知らないと「何を知っているんですか？」と言われることもある（本当にあった怖い話）ので，注意しましょう()

加群

しかし， $\mathbb{T}$ は積だと上手くいかないね，残念だねで終わってしまうのではなく， $\mathbb{Z}$ 加群の構造が入ることに注目します．

要するに， $\mathbb{T}$ での積っぽいものとして，スカラー倍を考えます．すると，和とスカラー倍に関して，分配法則を含めた良い感じの代数構造が入り，それを加群と言います．

以下，環といったら零環ではなく，また，単位元を持つものとします．また，簡単のため可換環の場合のみを考えます．

$\underline{\mathrm{Def(加群, module)}}$
$R$ を可換環， $M$ を空でない集合として， $R$ 加群 $M$ とは， $(M, +)$ は Abel 群であり，以下の演算が定義されている:

\begin{align*} R \times M \ni (r, x) & \mapsto rx \in M \\ M \times R \ni (x, r) & \mapsto xr \in M \end{align*}

このとき， $a, b \in R, \ x , y \in M$ として，次の４つの条件を満たすものとする:

\begin{align*} & (1) \hspace{10pt} 1 x = x \\ & (2) \hspace{10pt} a (bx) = (ab) x \\ & (3) \hspace{10pt} (a + b) x = a x + b x \\ & (4) \hspace{10pt} a (x + y) = a x + a y \\ \end{align*}

スカラー倍を考える理由

さて突如出てきたスカラー倍について，なんかいかにもって感じの定義をしていますね．なぜスカラー倍を考えるか，という疑問に関しては，「スカラー倍は複数回の足し算を一々書くのがめんどくさいので導入した」からです．なにか難しいことをやっているわけではありません．

今回の $\mathbb{T}$ で考えると，例えば， $0.3 \in \mathbb{T}$ を６回足したいなと思うときがありますよね？（ありますよね？）
そのとき，いくら $\mathbb{T}$ が和で閉じているからといって， $0.3 + 0.3 + 0.3 + 0.3 + 0.3 + 0.3 = 0.8 \ \mathrm{in} \ \mathbb{T}$ って書くのはあまりにめんどくさいです．
「普通」だと $6 \cdot 0.3$ と書きますよね．それと同じことです．

何回も足し算を書くのはめんどくさいので，それの省略記号として掛け算を導入する，のは小学校でやった掛け算と同じ導入の仕方です．紙面の省略をしています．

ちなみにスカラー倍なので「-2回足す」もできます．これはどう考えるかというと，例えば， $0.3 \in \mathbb{T}$ を「-2回足す」のは $- 0.3$ を「2回足す」と考えればOKです．
Torusは和で閉じている（これがポイント）ので，和に関する単位元（今回は0）が存在し， $0.3$ の逆元が存在することになります．

一般に和で閉じている集合の要素 $t$ への $K$ 倍は，
整数 $K$ が自然数なら， $t$ を $K$ 回足すこと
整数 $K$ が負の整数なら， $- t$ を $- K$ 回足すこと
に対応します．

この辺の一般的な議論は第３回で考察します．

加群はよく「ベクトル空間の一般化」と言われますが，それは $R$ の部分を体にするとベクトル空間の定義になるからです．

今回の $\mathbb{T}$ は $\mathbb{Z}$ 加群になっています．

上記のチェック

まず， $\mathbb{Z}$ は可換環です．また，

\begin{align*} \mathbb{Z} \times \mathbb{T} & \ni (n, x) \mapsto nx \ \mathrm{mod} \ 1 \in \mathbb{T} \\ \mathbb{T} \times \mathbb{Z} & \ni (x, n) \mapsto xn \ \mathrm{mod} \ 1 \in \mathbb{T} \end{align*}

と演算を定めることができます．
このとき， $m, n \in \mathbb{Z}, x, y \in \mathbb{T}$ に対して，

\begin{align*} & (1) \hspace{10pt} 1 x = x \\ & (2) \hspace{10pt} n (mx) \equiv n m x \equiv (nm) x \ \mathrm{mod} \ 1 \\ & (3) \hspace{10pt} (n + m) x \equiv n x + m x \ \mathrm{mod} \ 1 \\ & (4) \hspace{10pt} n (x + y) \equiv n x + n y \ \mathrm{mod} \ 1 \\ \end{align*}

が成り立っているので， $\mathbb{T}$ は $\mathbb{Z}$ 加群です．

多項式環

次に多項式環というものを考えます．特に１変数の場合です．多項式の次元についても導入します．

ここはそんなに難しくないです．多項式を元とする環を考えているだけです．

$\underline{\mathrm{Def(多項式環, polynomial \ ring)}}$
可換環 $R$ に対して，文字 $X$ を不定元とする， $R$ 係数の( $R$ 上の)多項式とは，

\begin{align*} \displaystyle a_n X^n + a_{n - 1} X^{n - 1} + \cdots + a_1 X + a_0 = \sum_{i = 0}^n a_i X^i \hspace{10pt} a_i \in R \end{align*}

なる形のものである．
多項式として0のもの（ $f(X) = 0$ なる $f$ ）を零多項式と呼び，零多項式以外の $R$ 係数の( $R$ 上の)多項式 $f(X)$ について

\begin{align*} \displaystyle \mathrm{max} \{ 0 \leq i \ | \ a_i \neq 0 \} \end{align*}

なる整数が存在し，これを多項式 $f(X)$ の次数と呼び， $\mathrm{deg} \ f(X)$ と書く．
ここで，零多項式の次数は $- \infty$ とする．即ち， $\mathrm{deg} \ 0 = - \infty$ である．

大雑把には，多項式の次数はそれぞれの項のうち，最大の次数のものを表します．
例としては，実数係数の多項式 $f(X) = X^2 + x + 1$ において， $\mathrm{deg} \ f(X) = 2$ です．

多項式や次数を考える際の注意点

$f(X) = X^2 + x + 1$ を考える際に， $f(X) = X^2 + X + 1 = - X^3 + X^3 + X^2 + x + 1$ だから， $\mathrm{deg} \ f(X) = 3$ では，と思う方もいらっしゃるかもしれません．
しかし，単に多項式と言ったら「標準形」になっているのが暗黙の了解です．っていうか上の考え方だと次数は一意に定まらないですし．

「標準形」について補足します．
$R$ 係数の多項式 $f(X)$ ，といったら，同じ変数の同じ指数の項は1つの項とみなします．上で言うと， $-X^3 + X^3$ を $(-1 + 1)X^3$ と1つの項でまとめます．
そして， $f$ の各係数は演算できるなら演算する必要があります．つまり上記の例だと， $-1 + 1$ を演算する必要がありますが，その答えは $0$ なので，次数の定義から　 $f(X)$ の次数は3にはならない，ことが分かります．

$- \infty$ は任意の整数より小さい整数，というイメージでいいと思います．

零多項式の次数

唐突に $- \infty$ が出てくるのが，意味分からん・・・という方もいらっしゃるかと思います．結論から書くと「そう定義すると都合が良いから」です．

一般に $f(X), g(X)$ を $R$ 係数の多項式でどちらも零多項式でないとするとき，

\begin{align} \mathrm{deg} \ (f + g)(X) & = \mathrm{max} \{ \mathrm{deg} \ f(X), \mathrm{deg} \ g(X) \} \\ \mathrm{deg} \ (fg)(X) & = \mathrm{deg} \ f(X) + \mathrm{deg} \ g(X) \\ \end{align}

が成り立ちます．
さて，零多項式の次数がまだ分からない状況として，(1)と(2)が零多項式の場合でも成り立ってくれるような零多項式の次数を考えることにします．
そうすると，次数が0とか-1のときはうまくいかないことがわかると思います．

例えば， $f(X) = X, g(X) = 0$ とすると， $fg(X) = 0$ であるときに，零多項式の次数が0とすると， $\mathrm{deg} \ (fg)(X) = 0$ と $\mathrm{deg} \ f(X) + \mathrm{deg} \ g(X) = 1 + 0 = 1$ となってしまい，(2)の式を満たしません．
同様に，零多項式の次数が-1とすると， $\mathrm{deg} \ (fg)(X) = -1$ と $\mathrm{deg} \ f(X) + \mathrm{deg} \ g(X) = 1 + (-1) = 0$ となってしまい，こちらも(2)の式を満たしません．
そして，零多項式の次数が $- \infty$ のとき， $\mathrm{deg} \ (fg)(X) = - \infty$ と $\mathrm{deg} \ f(X) + \mathrm{deg} \ g(X) = 1 + (- \infty) = - \infty$ なので，式(2)を満たします．式(1)も成り立ちます．

上記では具体例のみ考えましたが，これは一般の $\displaystyle f = \sum_{i = 0}^m a_i X^i$ の場合でも成り立ちます．
こんな感じで成り立ってほしい性質があるときに，それが成り立つよう上手く定義するみたいなことをたまに数学でやったりします．

(1)と(2)の証明

以下では，

\begin{align*} \displaystyle f = \sum_{i = 0}^m a_i X^i , \ g = \sum_{j = 0}^n b_i X^j \end{align*}

とします（特に $a_m \neq 0, \ b_n \neq 0$ ）．定義から $m = \mathrm{deg} \ f (X), \ n = \mathrm{deg} \ g (X)$ に注意します．
(1)
$\mathrm{deg} \ (f + g)(X)$ は， $m$ と $n$ の大小関係に依存します．つまり， $\mathrm{deg} \ (f + g)(X) = \mathrm{max} \{ m, n \}$ であり， $m = \mathrm{deg} \ f (X), \ n = \mathrm{deg} \ g (X)$ だったので，(1)が成り立ちます．
(2)
$\mathrm{deg} \ (fg)(X)$ は，ちょうど $m + n$ になります．これは $a_m \neq 0, \ b_n \neq 0$ より， $a_m b_n \neq 0$ なので， $fg$ の $X^{m + n}$ の係数が0ではないためです．

以上より示されました．

既約多項式と円分多項式

既約多項式は大雑把には「これ以上割り切れない多項式」で，円分多項式は $X^M - 1$ を割り切る $M - 1$ 次以下の既約多項式のことです．

$\underline{\mathrm{Def(既約多項式, irreducible \ polynomial)}}$
$R$ 係数の多項式 $f(X)$ が既約多項式であるとは，次数が $\mathrm{deg} \ f(X)$ 未満の $R$ 係数の多項式で割り切れないことである．

$\underline{\mathrm{Def(円分多項式, cyclotomic \ polynomial)}}$
$M$ を正整数とするとき， $M$ 次の円分多項式 $\Phi_M(X)$ とは，既約多項式であって， $X^M - 1$ を割り切るが，任意の $k < M$ で $X^k - 1$ を割り切らない多項式のことである．

既約多項式は考える $R$ によって既約かどうか異なることに注意しましょう．例えば， $x^2 + 1$ という多項式は $\mathbb{R}$ 上では（実数係数では）既約多項式ですが， $\mathbb{C}$ 上では（複素係数では）既約多項式ではありません． $(x + \sqrt{-1})(x - \sqrt{-1})$ と因数分解できるからです．
円分多項式を次数が小さい順に列挙すると， $\Phi_1(X) = X - 1, \ \Phi_2(X) = X + 1, \ \Phi_3(X) = X^2 + X + 1, \ \Phi_4(X) = X^2 + 1$ です．

しかし，これでは大雑把すぎるので，以下では，整域と既約という概念を定義した上で，既約多項式と円分多項式を定義する方法を紹介します．

整域

整域とは，「体っぽい環」と言えばいいでしょうか．0ではない元同士を掛けると0ではない，そのような環です．

例えば， $\mathbb{Z}$ は名前の通り？整域ですし， $\mathbb{Z} / 2 \mathbb{Z}$ や $\mathbb{Z} / 3 \mathbb{Z}$ も整域です．
しかし， $\mathbb{Z} / 4 \mathbb{Z}$ は整域ではありません． $2 \cdot 2 = 0$ となるからです．

上の定義で $R$ は可換環である必要はありません．
実は，初めに紹介した $\mathbb{Z} / 2 \mathbb{Z}$ は体なので，自動的に整域になります．

＊体になる云々の話は，次の記事の「hatについて」の折りたたみ「 $\mathbb{Z} / p \mathbb{Z}$ について」を参照してください

体ならば整域

可約・既約

既約はこれ以上「割り切れない」もので，可約は「まだ割り切れる」もののことです．

整数環 $Z$ において，2や3は既約です． $2 = 2 \cdot 1$ とすると，1は $Z$ で1自身が逆元になっているからです．しかし，6は可約です． $6 = 2 \cdot 3$ とすると，2も3も既約だからです．
この辺は，素数かどうかが関わってきます．

\begin{align*} & \bullet \ a \text{は逆元を持たない} \\ & \bullet \ b, c \in R \setminus \{0\}, a = b c \ \text{なら} \ b \ と \ c \ \text{のいずれかは逆元を持つ} \end{align*}

そうでないとき， $a$ は可約である，という．

初めの条件を $a$ は単元である，と言ったりします．

既約多項式

$\underline{\mathrm{Def(既約多項式, irreducible \ polynomial)}}$
$R$ を整域とするとき，多項式環 $R[X]$ 上で既約な元を既約多項式という．

整域と多項式はセットで考えます．ただ，体は整域なので，この辺から体の方が考えやすいかもしれません．

整域でないと，多項式を既約多項式の積に分解しようとしたとき，その分解の仕方が一意に定まらないことがあります．
例えば， $\mathbb{Z} / 4 \mathbb{Z}$ 上の多項式 $x^2$ は $x \cdot x$ と既約多項式の積に分離できますが， $(x + 2) \cdot (x + 2)$ も同様です．

円分多項式

$\underline{\mathrm{Def(n乗根と原始n乗根, nth \ root \ and \ primitve \ nth \ root)}}$
$n$ を正整数とするとき， $z \in \mathbb{C}$ であって， $z^n = 1$ を満たす $z$ を1の $n$ 乗根という．
$\zeta$ が1の $n$ 乗根であり， $0 < m < n$ で $\zeta^m \neq 1$ を満たすとき， $\zeta$ を1の原始 $n$ 乗根という．

よく見る $i = \sqrt{-1}$ は1の4乗根であり，1の原始4乗根です．しかし，1の8乗根でもありますが，1の原始8乗根ではありません．

\begin{align*} \displaystyle \Phi_n(X) = \prod_{1 \leq i \leq n, iとnは互いに素} (X - \zeta_n^i) \end{align*}

いかつい形をしていますが，なんと $\Phi_n(X)$ は任意の $n$ で整数係数の既約多項式であることが知られています．
少し計算をしてみると，例えば， $n = 3$ のとき，

\begin{align*} \displaystyle \Phi_3(X) &= (X - \zeta_3^1)(X - \zeta_3^2) = (X - e^{\frac{2 \pi \sqrt{-1}}{3}})(X - e^{\frac{4 \pi \sqrt{-1}}{3}}) \\ &= (X - (- \frac{1}{2} + \frac{\sqrt{3}}{2} \sqrt{-1}))(X - (- \frac{1}{2} - \frac{\sqrt{3}}{2} \sqrt{-1})) = X^2 + X + 1 \end{align*}

となり， $n = 4$ では，

\begin{align*} \displaystyle \Phi_4(X) &= (X - \zeta_4^1)(X - \zeta_4^3) = (X - \sqrt{-1})(X - \sqrt{-1}^3) = (X - \sqrt{-1})(X + \sqrt{-1}) \\ &= X^2 + 1 \end{align*}

となります．確かに前に出した例と一致していますね．こんな感じで計算できます．

Torus上の多項式

2.1 最後です．Torus上の多項式を考えます．

自然数 $N$ を取って，次の多項式環を考えます:

\begin{align*} \mathbb{R}_N[X] & := \mathbb{R}[X] / (X^N + 1) \\ \mathbb{Z}_N[X] & := \mathbb{Z}[X] / (X^N + 1) \end{align*}

元を具体的に書くと， $r_0, r_1, \cdots, r_{N - 1} \in \mathbb{R}$ として， $\displaystyle r_0 + r_1 X + \cdots + r_{N - 1} X^{N - 1} \in \mathbb{R}_N[X]$ であり， $z_0, z_1, \cdots, z_{N - 1} \in \mathbb{Z}$ として， $\displaystyle z_0 + z_1 X + \cdots + z_{N - 1} X^{N - 1} \in \mathbb{Z}_N[X]$ です．

イデアル

イデアルとは，環の部分集合であって，和とスカラー倍で閉じているものをいいます．

例えば，整数全体の集合 $Z$ において，偶数（2の倍数）全体の集合 $2 Z$ はイデアルになっています．2の倍数同士の和は2の倍数ですし，2の倍数にどんな整数を掛けても2の倍数だからです．
逆に奇数全体の集合は $\mathbb{Z}$ でのイデアルとはなりません．奇数同士の和は偶数になり，和で閉じていないからです．

厳密な定義は次のようになります．

$\underline{\mathrm{Def(イデアル, ideal)}}$
$R$ を可換環， $I$ を $R$ の部分集合とするとき， $I$ が $R$ のイデアルとは，次の2つの条件を満たすことである:

\begin{align*} & \bullet \ a, b \in I \Rightarrow a + b \in I \\ & \bullet \ a \in I, c \in R \Rightarrow ac (= ca) \in I \\ \end{align*}

上の定義では可換環でなくてもいいですが，その場合はどちらから $c$ を作用させるかに注意してください．
一見すると難しいように見えますが，部分環の条件を緩めたもの，と考えると馴染みやすいかと思います．

上の2つの定義に出てくるイデアルについて

上の2つの定義の $(X^N + 1)$ はそれぞれ異なるもの（イデアル）です．厳密には

\begin{align*} \mathbb{R}_N[X] & := \mathbb{R}[X] / \mathbb{R}[X] \cdot (X^N + 1) \\ \mathbb{Z}_N[X] & := \mathbb{Z}[X] / \mathbb{Z}[X] \cdot (X^N + 1) \end{align*}

です．つまり， $\mathbb{R}[X] \cdot (X^N + 1)$ は $(X^N + 1)$ を任意の実数係数の多項式倍したイデアルで， $\mathbb{Z}[X] \cdot (X^N + 1)$ は $(X^N + 1)$ を任意の整数係数の多項式倍したイデアルです．

どこの世界で生成しているのかに注意してください．

イデアルになっていることのチェック

$\mathbb{R}[X] \cdot (X^N + 1)$ の場合のみ確認します．念のため元を明示すると， $r(X) = r_0 + r_1 X + \cdots + r_{m - 1} X^{m - 1}$ を実数係数の多項式とする( $\mathbb{R}[X]$ の元として取る)とき， $r(X)(X^N + 1) = (r_0 + r_1 X + \cdots + r_{m - 1} X^{m - 1})(X^N + 1) \in \mathbb{R}[X] \cdot (X^N + 1)$ と書けます．

まず， $\mathbb{R}[X] \cdot (X^N + 1) \subset \mathbb{R}[X]$ は上の元が結局実数係数の多項式になることから分かります．
次に $r(X), s(X) \in \mathbb{R}[X]$ とします．つまり， $r(X), s(X)$ は共に実数係数の多項式です．すると， $r(X) (X^N + 1) + s(X) (X^N + 1)$ が $I$ に含まれるかどうかを考えればいいですが， $r(X) (X^N + 1) + s(X) (X^N + 1) = (r(X) + s(X)) (X^N + 1)$ で， $\mathbb{R}[X]$ は環ゆえ和で閉じているため， $r(X) + s(X) \in \mathbb{R}[X]$ ですから成り立ちます．
$r(X), c(X) \in \mathbb{R}[X]$ とします．すると， $c(X) \cdot r(X) (X^N + 1)$ が $I$ に含まれるかどうかを考えればいいですが， $\mathbb{R}[X]$ は環ゆえ積で閉じているため， $c(X) \cdot r(X) \in \mathbb{R}[X]$ ですから成り立ちます．

以上より示されました．

イメージとしては， $\mathbb{Z}$ 上の多項式全ては計算機には扱えないから，多項式の次数を有限に抑える感じです．

さて，Torus上の多項式を次のように表します:

\mathbb{T}_N[X] := \mathbb{R}_N[X] / \mathbb{Z}_N[X]

よって， $\mathbb{T}_N[X] = \mathbb{T}[X] / (X^N + 1)$ です．

上記の等号をチェック

以下では， $[0, 1)_N[X]$ という多項式環を導入します．これは，

\begin{align*} [0, 1)_N[X] = [0, 1)[X] / (X^N + 1) \end{align*}

です．元を具体的に書くと， $m_0, m_1, \cdots, m_{N - 1} \in [0, 1)$ として， $\displaystyle m_0 + m_1 X + \cdots + m_{N - 1} X^{N - 1} \in [0, 1)_N[X]$ です．

まず，Torusの定義と同様に $\mathbb{R}_N[X] / \mathbb{R}_Z[X] \cong [0, 1)_N[X]$ が成り立ちます．各係数ごとで考えてください．
すると， $[0, 1)_N[X]$ と $\mathbb{T}_N[X]$ が等しいかどうか，つまり， $[0, 1)[X] / (X^N + 1) \cong \mathbb{T}[X] / (X^N + 1)$ を確認することになりますが，
これは $[0, 1)$ の任意の元を $\mathbb{T}$ の代表元と見ることで成り立つことが分かリます．

よって，示されました．

$\mathbb{T}$ は

和でAbel群
整数のスカラー倍を考えられる

と同様に， $\mathbb{T}_N[X]$ は

和でAbel群
整数のスカラー倍を考えられる

ことに注意しましょう．証明は $\mathbb{T}$ のときと同様です．

上記の証明

和でAbel群
まず閉じていることを確認します．
$s_0 + s_1 X + \cdots + s_{N - 1} X^{N - 1}, t_0 + t_1 X + \cdots + t_{N - 1} X^{N - 1} \in \mathbb{T}_N[X]$ を取ります．ただし，任意の $i \in [0, N - 1]$ で $s_i, t_i \in \mathbb{T}$ です．
これらの和は $(s_0 + t_0) + (s_1 + t_1) X + \cdots + (s_{N - 1} + t_{N - 1}) X^{N - 1}$ となり， $\mathbb{T}$ は和で閉じているので， $i \in [0, N - 1]$ で $s_i + t_i \in \mathbb{T}$ ，つまり，和を取った後の多項式の各係数は $\mathbb{T}$ の元なので，示されました．

結合則と交換則は省略します．Torusと同じですし，所詮は実数の演算なので当たり前です．
$\mathbb{T}_N[X]$ の単位元は零多項式で， $\mathbb{T}_N[X]$ の逆元は各係数の $\mathbb{T}$ での逆元とした多項式です．

スカラー倍
今回の「加群」の折りたたみ「スカラー倍を考える理由」と同様です．

かなりはしょりましたが，これで証明を終わりにします．

ただし，先ほどのTorusと同じように掛け算を考えてもあまり意味はないので， $\mathbb{T}_N[X]$ は環ではありません．

離散一様分布と正規分布

ここから2.2で確率分布に入っていきます．

離散一様分布と正規分布を扱います．

$\underline{\mathrm{Def(離散一様分布, discrete \ uniform \ distribution)}}$

$N$ を正整数とする．確率変数 $X$ の確率密度関数が

\begin{align*} \displaystyle \forall x \in \{ 1, 2, \cdots, N \}, \ f(x) = \frac{1}{N} \end{align*}

のとき， $X$ は集合 $\{ 1, 2, \cdots, N \}$ 上の離散一様分布に従う，という．

$\underline{\mathrm{Def(正規分布, normal \ distribution)}}$

パラメータ $\mu, \sigma$ で，確率変数 $X$ の確率密度関数が

\begin{align*} \displaystyle f(x) = \frac{1}{\sqrt{2 \pi} \sigma} \exp \left \{ - \frac{(x - \mu)^2}{2 \sigma^2} \right \} \end{align*}

のとき， $X$ は $N(\mu, \sigma)$ の正規分布に従う，という．

正規分布は実数上で考えていますが，離散一様分布は整数上で考えています．正規分布は中々に「性質が良い」のですが，計算機上で扱うには実数を整数へ「丸め」る必要があります．

実数から整数への丸め

さて，問題のパートです．

上記では正規分布を考えましたが，実際に扱うのは実数ではなく整数ですので，実数を整数へと「丸める」必要があります．そのときにどういうものを想定するかというと，「四捨五入」だと思います．

本論文でも四捨五入を使っていますが， $x$ を実数としたとき， $\lfloor x \rceil$ という記号を使っています．これはなんなのでしょうか．

$\underline{\mathrm{Def(floor \ function)}}$
$x$ を実数としたとき， $\lfloor x \rfloor$ を $x$ の floor function といい，次のように定める:

\begin{align*} \lfloor x \rfloor = \mathrm{max} \{ n \in \mathbb{Z} \ | \ n \leq x \} \end{align*}

$\underline{\mathrm{Def(ceiling \ function)}}$
$x$ を実数としたとき， $\lceil x \rceil$ を $x$ の ceiling function といい，次のように定める:

\begin{align*} \lceil x \rceil = \mathrm{min} \{ n \in \mathbb{Z} \ | \ x \leq n \} \end{align*}

いわゆる，floor function が「切り捨て」で，ceiling function が「切り上げ」です．
$\lfloor x \rceil$ とは，これらを組み合わせた記号のことです．四捨五入，と定義してもいいのですが，上記の floor function なりを用いると，次のように定式化できます．

$\underline{\mathrm{Def(round \ function)}}$
$x$ を実数としたとき， $\lfloor x \rceil$ を $x$ の round function といい，次のように定める:

\displaystyle \begin{align*} \lfloor x \rceil = \lfloor x + \frac{1}{2} \rfloor (= \mathrm{max} \{ n \in \mathbb{Z} \ | \ n \leq x + \frac{1}{2} \} = \mathrm{min} \{ n \in \mathbb{Z} \ | \ x - \frac{1}{2} < n \}) \end{align*}

具体的に本論文では，どのように丸めているかを紹介します．
$q$ を正整数として， $(\mathbb{Z} / q \mathbb{Z})^{\prime}$ という集合を次のように取ります:

\begin{align*} \displaystyle (\mathbb{Z} / q \mathbb{Z})^{\prime} =　 \{ \lceil - \frac{q}{2} + 1 \rfloor + nq , \cdots , \lceil \frac{q}{2} \rfloor + nq \} \end{align*}

＊つまり $\displaystyle \left( - \frac{q}{2}, \frac{q}{2} \right] \bigcap \mathbb{Z}$ 上の整数を代表元とする同値類のこと

なぜ半開区間なのか

初めに $\displaystyle \left( - \frac{q}{2}, \frac{q}{2} \right] \bigcap \mathbb{Z}$ なので，要するに $\displaystyle \left( - \frac{q}{2}, \frac{q}{2} \right]$ に含まれる整数を考えればOKです．
結論から書くと「この端点だと任意の $q$ で半開区間の場合のみ $\mathrm{mod} \ q$ での異なる $q$ 個の代表元を含むから」です．

例えば， $q = 4$ の場合， $(-2, 2]$ に含まれる整数，つまり， $n$ を整数としたとき $-2 < n \leq 2$ を考えます．すると，端点では-2は含まれず2は含まれるため， $-1, 0, 1, 2$ が該当します．
一方で， $q = 3$ の場合， $(-2.5, 2.5]$ に含まれる整数，つまり， $n$ を整数としたとき $-2.5 < n \leq 2.5$ を考えます．すると，端点では-2と2は含まれますが，-3も3も含まれないため， $-2,-1, 0, 1, 2$ が該当します．

こんな感じで，考えていくと，

\begin{align*} q = 1 & \Rightarrow - 0.5 < n \leq 0.5 \Rightarrow n = 0 \\ q = 2 & \Rightarrow - 1 < n \leq 1 \Rightarrow n = 0, 1 \\ q = 3 & \Rightarrow - 1.5 < n \leq 1.5 \Rightarrow n = -1, 0, 1 \\ q = 4 & \Rightarrow - 2 < n \leq 2 \Rightarrow n = -1, 0, 1, 2 \\ q = 5 & \Rightarrow - 2.5 < n \leq 2.5 \Rightarrow n = -2, -1, 0, 1, 2 \\ \end{align*}

となり， $q$ の値が異なれば，それに応じて含まれる整数も異なることが分かります（このことは一般の $q$ で成り立ちます）．特に $q$ 個だけ整数が含まれているのがポイントですね．

では，開区間や閉区間の場合はどうなるでしょうか．まず，開区間で $\displaystyle \left( - \frac{q}{2}, \frac{q}{2} \right) \bigcap \mathbb{Z}$ だと，

\begin{align*} q = 1 & \Rightarrow - 0.5 < n < 0.5 \Rightarrow n = 0 \\ q = 2 & \Rightarrow - 1 < n < 1 \Rightarrow n = 0 \\ q = 3 & \Rightarrow - 1.5 < n < 1.5 \Rightarrow n = -1, 0, 1 \\ q = 4 & \Rightarrow - 2 < n < 2 \Rightarrow n = -1, 0, 1 \\ q = 5 & \Rightarrow - 2.5 < n < 2.5 \Rightarrow n = -2, -1, 0, 1, 2 \\ \end{align*}

であり，例えば， $q = 1, 2$ や $q = 3, 4$ でそれぞれの開区間に含まれる整数が同じになっています．

次に閉区間です． $\displaystyle \left[ - \frac{q}{2}, \frac{q}{2} \right] \bigcap \mathbb{Z}$ だと，

\begin{align*} q = 1 & \Rightarrow - 0.5 \leq n \leq 0.5 \Rightarrow n = 0 \\ q = 2 & \Rightarrow - 1 \leq n \leq 1 \Rightarrow n = -1, 0, 1 \\ q = 3 & \Rightarrow - 1.5 \leq n \leq 1.5 \Rightarrow n = -1, 0, 1 \\ q = 4 & \Rightarrow - 2 \leq n \leq 2 \Rightarrow n = -2, -1, 0, 1, 2 \\ q = 5 & \Rightarrow - 2.5 \leq n \leq 2.5 \Rightarrow n = -2, -1, 0, 1, 2 \\ \end{align*}

であり，こちらも例えば， $q = 2, 3$ や $q = 4, 5$ で閉区間に含まれる整数が同じです．

ということで，半開区間であれば， $q$ が異なれば，その区間に含まれる整数も異なることがわかりました．
そして，半開区間の場合で例えば $q = 5$ なら $-2, -1, 0, 1, 2$ の5つの整数が含まれていますが，これは -2 を 3， -1 を 4 と対応づけることで $\mathrm{mod} \ 5$ での代表元と見ることもできます．
つまり，一般にこの半開区間に含まれる整数は $\mathrm{mod} \ q$ での代表元を含んでいることになります．

そして，任意の整数 $n$ を $\displaystyle \left( - \frac{q}{2}, \frac{q}{2} \right] \bigcap \mathbb{Z}$ 上の整数に対応させる操作を $\mathrm{mod}^{\prime} \ q$ と書くことにします．
例えば， $q = 5$ のとき， $11 \equiv 1 \ \mathrm{mod}^{\prime} \ 5$ , $13 \equiv -2 \ \mathrm{mod}^{\prime} \ 5$ です．
＊上では通常の $\mathrm{mod}$ を通して， $11 \equiv 1 \equiv -4 \mathrm{mod} \ 5$ と $13 \equiv 3 \equiv -2 \mathrm{mod} \ 5$ で， $[-2, 2]$ に属するものを考えています．

このとき，実数値 $X$ と正整数 $q$ を取ります．そのとき整数値 $Z$ を $Z = \lfloor X q \rceil \ \mathrm{mod}^{\prime} \ q$ で定めます．この $Z$ は， $(\mathbb{Z} / q \mathbb{Z})^{\prime}$ の元ですので， $X$ を「整数に丸めた」値となっています．

今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！

パイオニアの論文読みづらいがち

全４回通しでの目次

本論文全体の流れ

前提知識

集合論

線型代数

確率・統計

代数

初等整数論

計算量理論

代数とか計算量理論が載っている暗号の本

今回出てくる予備知識のまとめ

Torus

準同型

全射

準同型定理

群準同型・環準同型

ImとKer

群準同型定理・環準同型定理

加群

多項式環

既約多項式と円分多項式

Torus上の多項式

離散一様分布と正規分布

実数から整数への丸め

Discussion