補題：数式中で使う記号の定義
（補題：数式中で使う記号の定義 - Plus Le Toolから移動しました。）
初期seedから日時を求める無謀な挑戦 - Plus Le Blogのための補題。
ＳＨＡ－１の計算過程では、32bit符号なし整数（uint型）の論理積，論理和，排他的論理和，論理否定，算術和，循環シフト，および代入の演算が必要になるので、それらの記号をここで定義しておく。
【1bit整数（bool型）の記号】
| 記号 | 意味 | 備考 |
|---|---|---|
| \(x,\,y,\,z,\,\dots\) | 1bit整数（bool型） | 変数 （主に）アルファベット小文字を使う |
| \(0\) | 偽（FALSE） | 定数 |
| \(1\) | 真（TRUE） | 定数 |
| \(x\,\cap\,y\) | 論理積（AND） | 強調したい場合を除き \(xy\) のように略記する |
| \(x\,\cup\,y\) | 論理和（OR） | |
| \(x\,\oplus\,y\) | 排他的論理和（XOR） | |
| \(\bar{x}\) | 論理否定（NOT） | |
| \(x\cdot y\) | 算術積 | 論理積ではないので注意 \(xy\) のような略記はしない |
| \(x+y\) | 算術和 | 論理和ではないので注意 オーバーフローした上位bitは切り捨て |
| \(=\) | 代入 | 等式の意味でも使うので注意 |
【32bit符号なし整数（uint型）の記号】
| 記号 | 意味 | 備考 |
|---|---|---|
| \(X,\,Y,\,Z,\,\dots\) | 32bit符号なし整数（uint型） | 変数 （主に）アルファベット大文字を使う |
| \(X\,\cap\,Y\) | 論理積（AND） | 積集合の意味でも使うので注意 強調したい場合を除き \(XY\) のように略記する |
| \(X\,\cup\,Y\) | 論理和（OR） | 和集合の意味でも使うので注意 |
| \(X\,\oplus\,Y\) | 排他的論理和（XOR） | |
| \(\bar{X}\) | 論理否定（NOT） | 補集合の意味でも使うので注意 |
| \(X\,\underset{c}{<<}\,n\) | 左循環シフト | cは"circular shift"の略 |
| \(X\,\underset{c}{>>}\,n\) | 右循環シフト | cは"circular shift"の略 |
| \(X\cdot Y\) | 算術積 | 論理積ではないので注意 \(XY\) のような略記はしない オーバーフローした上位bitは切り捨て |
| \(X+Y\) | 算術和 | 論理和ではないので注意 オーバーフローした上位bitは切り捨て |
| \(=\) | 代入 | 等式の意味でも使うので注意 |
【その他の定義】
- 論理積
- \(\displaystyle\bigcap_{i=0}^{n}x_{i}=x_{0}\,\cap\,x_{1}\,\cap\,\dots\,\cap\,x_{n}\;\left(=x_{0}x_{1}\dots x_{n}\right)\)
\(\displaystyle\bigcap_{i=0}^{n}X_{i}=X_{0}\,\cap\,X_{1}\,\cap\,\dots\,\cap\,X_{n}\;\left(=X_{0}X_{1}\dots X_{n}\right)\)- 論理和
- \(\displaystyle\bigcup_{i=0}^{n}x_{i}=x_{0}\,\cup\,x_{1}\,\cup\,\dots\,\cup\,x_{n}\)
\(\displaystyle\bigcup_{i=0}^{n}X_{i}=X_{0}\,\cup\,X_{1}\,\cup\,\dots\,\cup\,X_{n}\)- 排他的論理和
- \(\displaystyle\bigoplus_{i=0}^{n}x_{i}=x_{0}\,\oplus\,x_{1}\,\oplus\,\dots\,\oplus\,x_{n}\)
\(\displaystyle\bigoplus_{i=0}^{n}X_{i}=X_{0}\,\oplus\,X_{1}\,\oplus\,\dots\,\oplus\,X_{n}\)- 算術積
- \(\displaystyle\prod_{i=0}^{n}x_{i}=x_{0}\cdot x_{1}\cdot\,\dots\,\cdot x_{n}\)
\(\displaystyle\prod_{i=0}^{n}X_{i}=X_{0}\cdot X_{1}\cdot\,\dots\,\cdot X_{n}\)- 算術和
- \(\displaystyle\sum_{i=0}^{n}x_{i}=x_{0}+x_{1}+\,\dots\,+x_{n}\)
\(\displaystyle\sum_{i=0}^{n}X_{i}=X_{0}+X_{1}+\,\dots\,+X_{n}\)- bool型変数を使った二進数表示
- \(X=\left\{\begin{array}{l}\left(x_{31}x_{30}\dots x_{0}\right)_{2}\\\left(x_{32}x_{31}\dots x_{1}\right)_{2}\end{array}\right.\)
（※最下位bitを \(x_{0}\) から数えるか \(x_{1}\) から数えるかは気まぐれなので注意。……いや統一しろよ、俺orz）- 扱う数の集合
- \(\mathbb{B}=\left\{0,\,1\right\}\)
- 定義文
- \(y\overset{\mathrm{def}}{=}f\left(x\right)\)
（新しい変数（この場合 \(y\) ）を定義する際に使う）- 合同式
- \(y\equiv x\pmod{M}\)
（法を \(M\) とする合同関係を表す）- 剰余算
- \(y= x\,\bmod\,M\)
（\(x\) を \(M\) で割った余り（ \(0\) 以上 \(M -1\) 以下）が \(y\) であることを表す）
