読者です 読者をやめる 読者になる 読者になる

補題:数式中で使う記号の定義

ブール代数

補題:数式中で使う記号の定義 - Plus Le Toolから移動しました。)


初期seedから日時を求める無謀な挑戦 - Plus Le Blogのための補題

SHA-1の計算過程では、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\) であることを表す)