補題：32bit符号なし整数変数間の演算をブール関数で表す

初期seedから日時を求める無謀な挑戦 - Plus Le Toolのための補題。
使う記号の定義は[id:plusletool:20130427:p2]参照。

ＳＨＡ−１アルゴリズムは32bit符号なし整数（uint型）間の演算で記述されているが、あえてそれを1bit整数（bool型）間の演算に書き換えることで、手がかりを得ようという試み。
最初に断っておくと、メモリ使用量的にも計算時間的にも明らかに無謀。でもやる。

uint型整数変数をbool型整数変数で記述する方法を考える。例えばuint型整数の変数を $X$ とする。
$X$ の第 $i$ bitを $x_{i}$ とする、つまり、 $X$ を二進表示すると次のようになるとする。

（＊１）
$X=\left(x_{32}x_{31}\dots x_{1}\right)_{2}$

見ての通り、 $X$ の第1bit（最下位bit）は $x_{1}$ であり、第32bit（最上位bit）は $x_{32}$ である。
また、この $x_{1},x_{2},\dots,x_{32}$ は $n$ 個のbool型変数 $u_{1},u_{2},\dots,u_{n}$ の関数であるとする。

（＊２）
$\begin{array}{lcl}x_{1}&=&x_{1}\left(u_{1},u_{2},\dots,u_{n}\right)\\x_{2}&=&x_{2}\left(u_{1},u_{2},\dots,u_{n}\right)\\&\vdots&\\x_{32}&=&x_{32}\left(u_{1},u_{2},\dots,u_{n}\right)\end{array}$

これらの関数をシャノン展開してみよう。

【補足】シャノン展開
例えばブール関数 $f\left(x,y,z\right)$ について、次の式を考える。

$\alpha=f\left(0,y,z\right)\bar{x}\,\cup\,f\left(1,y,z\right)x$

$x=0$ のときは、 $\alpha=f\left(0,y,z\right)\cap\bar{0}\,\cup\,f\left(1,y,z\right)\cap 0=f\left(0,y,z\right)$ である。
$x=1$ のときは、 $\alpha=f\left(0,y,z\right)\cap\bar{1}\,\cup\,f\left(1,y,z\right)\cap 1=f\left(1,y,z\right)$ である。
つまり $\alpha$ は　 $x$ の値によらず $f\left(x,y,z\right)$ に一致するので、関数 $f\left(x,y,z\right)$ は次のように書き換えられる。

$f\left(x,y,z\right)=f\left(0,y,z\right)\bar{x}\,\cup\,f\left(1,y,z\right)x$

次に、上式に含まれる $f\left(0,y,z\right)$ および $f\left(1,y,z\right)$ は $x$ に依存しないので、 $y,z$ の関数である。
上と同様に考えることで、これらの関数はそれぞれ次のように書き換えられる。

$f\left(0,y,z\right)=f\left(0,0,z\right)\bar{y}\,\cup\,f\left(0,1,z\right)y\\f\left(1,y,z\right)=f\left(1,0,z\right)\bar{y}\,\cup\,f\left(1,1,z\right)y$

同様に、 $f\left(0,0,z\right),\,f\left(0,1,z\right),\,f\left(1,0,z\right),\,f\left(1,1,z\right)$ は $x,y$ に依存しないので $z$ の関数であり、これらはそれぞれ次のように書き換えられる。

$f\left(0,0,z\right)=f\left(0,0,0\right)\bar{z}\,\cup\,f\left(0,0,1\right)z\\f\left(0,1,z\right)=f\left(0,1,0\right)\bar{z}\,\cup\,f\left(0,1,1\right)z\\f\left(1,0,z\right)=f\left(1,0,0\right)\bar{z}\,\cup\,f\left(1,0,1\right)z\\f\left(1,1,z\right)=f\left(1,1,0\right)\bar{z}\,\cup\,f\left(1,1,1\right)z$

この式中に現れる $f\left(0,0,0\right)$ ， $f\left(0,0,1\right)$ ， $f\left(0,1,0\right)$ ， $f\left(0,1,1\right)$ ， $f\left(1,0,0\right)$ ， $f\left(1,0,1\right)$ ， $f\left(1,1,0\right)$ ， $f\left(1,1,1\right)$ は $x,y,z$ に依存しない。
（もし $f\left(x,y,z\right)$ に別の変数 $w$ が含まれていたとしたらこれら（ $f\left(0,0,0\right)$ など）は $w$ の関数になるが、 $x,y,z$ 以外の変数が含まれないならこれら（ $f\left(0,0,0\right)$ など）は定数である。）
上述の式変形を順に行い整理すると、関数 $f\left(x,y,z\right)$ は次のように変形できる。

$\begin{array}{lclclclcl}f\left(x,y,z\right)&=&f\left(0,0,0\right)\bar{x}\bar{y}\bar{z}&\,\cup\,&f\left(0,0,1\right)\bar{x}\bar{y}z&\,\cup\,&f\left(0,1,0\right)\bar{x}y\bar{z}&\,\cup\,&f\left(0,1,1\right)\bar{x}yz\\&\,\cup\,&f\left(1,0,0\right)x\bar{y}\bar{z}&\,\cup\,&f\left(1,0,1\right)x\bar{y}z&\,\cup\,&f\left(1,1,0\right)xy\bar{z}&\,\cup\,&f\left(1,1,1\right)xyz\end{array}$

このような変形をシャノン展開という。

上の例は3変数の場合だが、一般には次のように書ける。

$\begin{array}{lcl}f\left(x_{1},x_{2},\dots,x_{n}\right)&=&\bigcup_{b_{1}\in\mathbb{B}\\b_{2}\in\mathbb{B}\\\dots\\b_{n}\in\mathbb{B}}\left(f\left(b_{1},b_{2},\dots,b_{n}\right)\bigcap_{i=1}^{n}\left(x_{i}\,\oplus\,\bar{b_{i}}\right)\right)\\&=&f\left(0,0,\dots,0\right)\bar{x_{1}}\bar{x_{2}}\dots\bar{x_{n}}\,\cup\,f\left(0,0,\dots,1\right)\bar{x_{1}}\bar{x_{2}}\dots x_{n}\,\cup\,\dots\,\cup\,f\left(1,1,\dots,1\right)x_{1}x_{2}\dots x_{n}\end{array}$

※ $\mathbb{B}$ はブール代数で使用するすべての元（簡単に言うと整数のこと）の集合、つまり $\mathbb{B}=\left\{0,1\right\}$ である。
※右辺に出てくる係数 $f\left(b_{1},b_{2},\dots,b_{n}\right)$ は $x_{1},x_{2},\dots,x_{n}$ に依存しない（≒定数）。

><
※ $x\,\oplus\,\bar{b}=b x\,\cup\,\bar{b}\bar{x}$ より、 $x\,\oplus\,\bar{b}$ は「 $b=0$ のとき $\bar{x}$ 、 $b=1$ のとき $x$ 」を意味する。
なおこの式（上記の一般の場合の式）の右辺は、「 $x_{1},x_{2},\dots,x_{n}$ の肯定リテラルまたは否定リテラルのいずれか一方を1個ずつすべて論理積した項」の組み合わせをすべて含むので、項数は $2^{n}$ である。
また、この式の右辺は積和標準形になっている。

（＊２）をシャノン展開して積和標準形で表すと、次のようになる。

（＊３）
$\begin{array}{rcrcrcrcr}x_{1}\left(u_{1},u_{2},\dots,u_{n}\right)&=&x_{1}\left(0,0,\dots,0\right)\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&x_{1}\left(0,0,\dots,1\right)\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&x_{1}\left(1,1,\dots,1\right)u_{1}u_{2}\dots u_{n}\\x_{2}\left(u_{1},u_{2},\dots,u_{n}\right)&=&x_{2}\left(0,0,\dots,0\right)\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&x_{2}\left(0,0,\dots,1\right)\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&x_{2}\left(1,1,\dots,1\right)u_{1}u_{2}\dots u_{n}\\&\vdots&\\x_{32}\left(u_{1},u_{2},\dots,u_{n}\right)&=&x_{32}\left(0,0,\dots,0\right)\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&x_{32}\left(0,0,\dots,1\right)\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&x_{32}\left(1,1,\dots,1\right)u_{1}u_{2}\dots u_{n}\end{array}$

ところで、積和標準形は「式中の論理和を排他的論理和に置き換えても等式が成り立つ」という性質がある。
また排他的論理和は、法2の下での算術和の値に等しい。
これらより（＊３）は次のように変形できる（第 $i$ bitの場合を示す）。

（＊４）
$\begin{array}{lclclclclcl}x_{i}\left(u_{1},u_{2},\dots,u_{n}\right)&=&x_{i}\left(0,0,\dots,0\right)\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&x_{i}\left(0,0,\dots,1\right)\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&x_{i}\left(1,1,\dots,1\right)u_{1}u_{2}\dots u_{n}\\&=&x_{i}\left(0,0,\dots,0\right)\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\oplus&x_{i}\left(0,0,\dots,1\right)\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\oplus&\dots&\oplus&x_{i}\left(1,1,\dots,1\right)u_{1}u_{2}\dots u_{n}\\&\equiv&x_{i}\left(0,0,\dots,0\right)\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&+&x_{i}\left(0,0,\dots,1\right)\bar{u_{1}}\bar{u_{2}}\dots u_{n}&+&\dots&+&x_{i}\left(1,1,\dots,1\right)u_{1}u_{2}\dots u_{n}\;\pmod{2}\end{array}$

これを使って（＊３）を行列で表すと次のようになる。

（＊５）
$\begin{bmatrix}x_{1}\left(u_{1},u_{2},\dots,u_{n}\right)\\x_{2}\left(u_{1},u_{2},\dots,u_{n}\right)\\\vdots\\x_{32}\left(u_{1},u_{2},\dots,u_{n}\right)\end{bmatrix}\equiv\left[\begin{array}{cccc}x_{1}\left(0,0,\dots,0\right)&x_{1}\left(0,0,\dots,1\right)&\dots\dots\dots&x_{1}\left(1,1,\dots,1\right)\\x_{2}\left(0,0,\dots,0\right)&x_{2}\left(0,0,\dots,1\right)&\dots\dots\dots&x_{2}\left(1,1,\dots,1\right)\\&&\vdots&\\x_{32}\left(0,0,\dots,0\right)&x_{32}\left(0,0,\dots,1\right)&\dots\dots\dots&x_{32}\left(1,1,\dots,1\right)\end{array}\right]\begin{bmatrix}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}\\\bar{u_{1}}\bar{u_{2}}\dots u_{n}\\\vdots\\\vdots\\\vdots\\u_{1}u_{2}\dots u_{n}\end{bmatrix}\;\pmod{2}$

左辺の列ベクトルは32次、右辺の係数行列は $32\times N$ 行列、右辺の列ベクトルは $N$ 次である。
ただし、 $N\overset{\mathrm{def}}{=}2^{n}$ とおいた。

（＊５）で、係数行列を $M_{\small{X}}$ とする。

（＊６）
$M_{\small{X}}\overset{\mathrm{def}}{=}\left[\begin{array}{cccc}x_{1}\left(0,0,\dots,0\right)&x_{1}\left(0,0,\dots,1\right)&\dots\dots\dots&x_{1}\left(1,1,\dots,1\right)\\x_{2}\left(0,0,\dots,0\right)&x_{2}\left(0,0,\dots,1\right)&\dots\dots\dots&x_{2}\left(1,1,\dots,1\right)\\&&\vdots&\\x_{32}\left(0,0,\dots,0\right)&x_{32}\left(0,0,\dots,1\right)&\dots\dots\dots&x_{32}\left(1,1,\dots,1\right)\end{array}\right]$

この行列の各成分は $u_{1},u_{2},\dots,u_{n}$ に依存しない値である（ $u_{1},u_{2},\dots,u_{n}$ について定数）。
そこで $M_{\small{X}}$ の $\left(i,j\right)$ 成分を $x_{i,j}$ とおく。

（＊７）
$\begin{eqnarray}M_{\small{X}}&=&\left[\left\{x_{i,j}\right\}\right]\\&=&\left[\begin{array}{cccc}x_{1,1}&x_{1,2}&\dots\dots\dots&x_{1,N}\\x_{2,1}&x_{2,2}&\dots\dots\dots&x_{2,N}\\&&\vdots&\\x_{32,1}&x_{32,2}&\dots\dots\dots&x_{32,N}\end{array}\right]\end{eqnarray}$
ただし、
$\begin{eqnarray}x_{1,1}&\overset{\mathrm{def}}{=}&x_{1}\left(0,0,\dots,0\right)\\x_{1,2}&\overset{\mathrm{def}}{=}&x_{1}\left(0,0,\dots,1\right)\\&\vdots&\\x_{1,N}&\overset{\mathrm{def}}{=}&x_{1}\left(1,1,\dots,1\right)\\x_{2,1}&\overset{\mathrm{def}}{=}&x_{2}\left(0,0,\dots,0\right)\\x_{2,2}&\overset{\mathrm{def}}{=}&x_{2}\left(0,0,\dots,1\right)\\&\vdots&\\x_{2,N}&\overset{\mathrm{def}}{=}&x_{2}\left(1,1,\dots,1\right)\\&\vdots&\\&\vdots&\\x_{32,1}&\overset{\mathrm{def}}{=}&x_{32}\left(0,0,\dots,0\right)\\x_{32,2}&\overset{\mathrm{def}}{=}&x_{32}\left(0,0,\dots,1\right)\\&\vdots&\\x_{32,N}&\overset{\mathrm{def}}{=}&x_{32}\left(1,1,\dots,1\right)\end{eqnarray}$

紛らわしいので念のため確認しておくが、

$x_{i}$ は $u_{1},u_{2},\dots,u_{n}$ の関数で、 $X$ の第 $i$ bitを表す。
$x_{i,j}$ は $u_{1},u_{2},\dots,u_{n}$ について定数で、 $x_{i}$ を積和標準形にした時の第 $j$ 項の係数を表す。

また、（＊５）の右辺の列ベクトルはこれ以降で変形されないので、これを $\mathbf{u}$ とおく。

（＊８）
$\mathbf{u}\overset{\mathrm{def}}{=}\begin{bmatrix}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}\\\bar{u_{1}}\bar{u_{2}}\dots u_{n}\\\vdots\\\vdots\\\vdots\\u_{1}u_{2}\dots u_{n}\end{bmatrix}$

（＊７）（＊８）を使って（＊９）を書き直して、次式を得る。

（＊９）
$\begin{eqnarray}\begin{bmatrix}x_{1}\left(u_{1},u_{2},\dots,u_{n}\right)\\x_{2}\left(u_{1},u_{2},\dots,u_{n}\right)\\\vdots\\x_{32}\left(u_{1},u_{2},\dots,u_{n}\right)\end{bmatrix}&\equiv&\left[\begin{array}{cccc}x_{1,1}&x_{1,2}&\dots\dots\dots&x_{1,N}\\x_{2,1}&x_{2,2}&\dots\dots\dots&x_{2,N}\\&&\vdots&\\x_{32,1}&x_{32,2}&\dots\dots\dots&x_{32,N}\end{array}\right]\begin{bmatrix}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}\\\bar{u_{1}}\bar{u_{2}}\dots u_{n}\\\vdots\\\vdots\\\vdots\\u_{1}u_{2}\dots u_{n}\end{bmatrix}\;\pmod{2}\\&=&M_{\small{X}}\mathbf{u}\end{eqnarray}$

（＊９）の左辺の列ベクトルは、あるuint型変数 $X$ の各bitを並べたものなので、 $X$ と $M_{\small{X}}$ は一対一に対応している。
よってuint型変数（この例では $X$ ）を調べたいときは、その係数行列（この例では $M_{\small{X}}$ ）を調べればいい。

さて、ここからが本題。
ＳＨＡ−１アルゴリズムで出てくる演算は、論理積，論理和，排他的論理和，論理否定，算術和，循環シフト，および代入の７種類。
これらの演算が1bit単位ではどのように表されるのかを、簡単なものから順に見ていこうと思う。

最初に1番簡単な代入演算から。
32bit整数の代入演算は、各bitを個別に代入したと考えても同じである。
よって（＊10）の32bit整数の代入演算を1bit単位で記述し直すと、（＊11）のようになる。

（＊10）代入（uint型）
$X=P$

（＊11）
$\begin{array}{lcl}x_{1}&=&p_{1}\\x_{2}&=&p_{2}\\&\vdots&\\x_{32}&=&p_{32}\end{array}$

（＊11）において、 $x_{i},p_{i}$ は $u_{1},u_{2},\dots,u_{n}$ の関数である。
2つの関数が等価ということは、その積和標準形の各係数がすべて等しいことを意味する。
よってそれぞれの係数行列 $M_{\small{X}},M_{\small{P}}$ を比較することで、次のようになる。

（＊12）代入（bool型）
$\begin{eqnarray}M_{\small{X}}&=&\left[\left\{p_{i,j}\right\}\right]\\&=&\left[\begin{array}{cccc}p_{1,1}&p_{1,2}&\dots&p_{1,N}\\p_{2,1}&p_{2,2}&\dots&p_{2,N}\\&&\vdots&&\\p_{32,1}&p_{32,2}&\dots&p_{32,N}\end{array}\right]\end{eqnarray}$

同じように考えていこう。
次は論理積，論理和，排他的論理和，論理否定をまとめて考えてみる。

（＊13）論理積（uint型）
$X=PQ$

（＊14）論理和（uint型）
$X=P\,\cup\,Q$

（＊15）排他的論理和（uint型）
$X=P\,\oplus\,Q$

（＊16）論理否定（uint型）
$X=\bar{P}$

複数bitの論理演算は各bitごとに演算するよう定義されているので、代入演算と同様に考えることができる。
よって（＊13）〜（＊16）を1bit単位で記述し直すと、次のようになる。

（＊17）
論理積
$\begin{array}{lcl}x_{1}&=&p_{1}q_{1}\\x_{2}&=&p_{2}q_{2}\\&\vdots&\\x_{32}&=&p_{32}q_{32}\end{array}$
論理和
$\begin{array}{lclcl}x_{1}&=&p_{1}&\cup&q_{1}\\x_{2}&=&p_{2}&\cup&q_{2}\\&\vdots&&&\\x_{32}&=&p_{32}&\cup&q_{32}\end{array}$
排他的論理和
$\begin{array}{lclcl}x_{1}&=&p_{1}&\oplus&q_{1}\\x_{2}&=&p_{2}&\oplus&q_{2}\\&\vdots&&&\\x_{32}&=&p_{32}&\oplus&q_{32}\end{array}$
論理否定
$\begin{array}{lcl}x_{1}&=&\bar{p_{1}}\\x_{2}&=&\bar{p_{2}}\\&\vdots&\\x_{32}&=&\bar{p_{32}\end{array}$

ところで、 $p_{i},q_{i}$ は $p_{i,1},p_{i,2},\dots,p_{i,N}$ および $q_{i,1},q_{i,2},\dots,q_{i,N}$ を係数とする積和標準形で表されるのだった。

（＊18）
$\begin{array}{lclclclclcl}p_{i}\left(u_{1},u_{2},\dots,u_{n}\right)&=&p_{i,1}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&p_{i,2}\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&p_{i,N}u_{1}u_{2}\dots u_{n}\\q_{i}\left(u_{1},u_{2},\dots,u_{n}\right)&=&q_{i,1}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&q_{i,2}\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&q_{i,N}u_{1}u_{2}\dots u_{n}\end{array}$

積和標準形どうしの論理積は、リテラル（ $u_{k}$ のこと）の組み合わせが同じである項の係数どうしの論理積を新たな係数とする積和標準形で表される。論理和と排他的論理和も同様。
……言葉で書くと分かりにくいので式を見たほうが早いだろうか。

（＊19）
$\begin{array}{lcrrcrcrcrcrl}p_{i}\left(u_{1},u_{2},\dots,u_{n}\right)q_{i}\left(u_{1},u_{2},\dots,u_{n}\right)&=&\big(&p_{i,1}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&p_{i,2}\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&p_{i,N}u_{1}u_{2}\dots u_{n}&\big)\\&\cap&\big(&q_{i,1}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&q_{i,2}\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&q_{i,N}u_{1}u_{2}\dots u_{n}&\big)\\&=&&p_{i,1}q_{i,1}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&p_{i,2}q_{i,2}\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&p_{i,N}q_{i,N}u_{1}u_{2}\dots u_{n}&\end{array}$
$\begin{array}{lcrrcrcrcrcrl}p_{i}\left(u_{1},u_{2},\dots,u_{n}\right)\,\cup\,q_{i}\left(u_{1},u_{2},\dots,u_{n}\right)&=&\big(&p_{i,1}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&p_{i,2}\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&p_{i,N}u_{1}u_{2}\dots u_{n}&\big)\\&\cup&\big(&q_{i,1}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&q_{i,2}\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&q_{i,N}u_{1}u_{2}\dots u_{n}&\big)\\&=&&\left(p_{i,1}\cup q_{i,1}\right)\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&\left(p_{i,2}\cup q_{i,2}\right)\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&\left(p_{i,N}\cup q_{i,N}\right)u_{1}u_{2}\dots u_{n}&\end{array}$
$\begin{array}{lcrrcrcrcrcrl}p_{i}\left(u_{1},u_{2},\dots,u_{n}\right)\,\oplus\,q_{i}\left(u_{1},u_{2},\dots,u_{n}\right)&=&\big(&p_{i,1}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&p_{i,2}\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&p_{i,N}u_{1}u_{2}\dots u_{n}&\big)\\&\oplus&\big(&q_{i,1}\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&q_{i,2}\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&q_{i,N}u_{1}u_{2}\dots u_{n}&\big)\\&=&&\left(p_{i,1}\oplus q_{i,1}\right)\bar{u_{1}}\bar{u_{2}}\dots\bar{u_{n}}&\cup&\left(p_{i,2}\oplus q_{i,2}\right)\bar{u_{1}}\bar{u_{2}}\dots u_{n}&\cup&\dots&\cup&\left(p_{i,N}\oplus q_{i,N}\right)u_{1}u_{2}\dots u_{n}&\end{array}$

よってそれぞれの係数行列を比較して、次のようになる。

（＊20）論理積（bool型）
$\begin{eqnarray}M_{\small{X}}&=&\left[\left\{p_{i,j}q_{i,j}\right\}\right]\\&=&\left[\begin{array}{cccc}p_{1,1}q_{1,1}&p_{1,2}q_{1,2}&\dots&p_{1,N}q_{1,N}\\p_{2,1}q_{2,1}&p_{2,2}q_{2,2}&\dots&p_{2,N}q_{2,N}\\&&\vdots&&\\p_{32,1}q_{32,1}&p_{32,2}q_{32,2}&\dots&p_{32,N}q_{32,N}\end{array}\right]\end{eqnarray}$

（＊21）論理和（bool型）
$\begin{eqnarray}M_{\small{X}}&=&\left[\left\{p_{i,j}\,\cup\,q_{i,j}\right\}\right]\\&=&\left[\begin{array}{cccc}p_{1,1}\cup q_{1,1}&p_{1,2}\cup q_{1,2}&\dots&p_{1,N}\cup q_{1,N}\\p_{2,1}\cup q_{2,1}&p_{2,2}\cup q_{2,2}&\dots&p_{2,N}\cup q_{2,N}\\&&\vdots&&\\p_{32,1}\cup q_{32,1}&p_{32,2}\cup q_{32,2}&\dots&p_{32,N}\cup q_{32,N}\end{array}\right]\end{eqnarray}$

（＊22）排他的論理和（bool型）
$\begin{eqnarray}M_{\small{X}}&=&\left[\left\{p_{i,j}\,\oplus\,q_{i,j}\right\}\right]\\&=&\left[\begin{array}{cccc}p_{1,1}\oplus q_{1,1}&p_{1,2}\oplus q_{1,2}&\dots&p_{1,N}\oplus q_{1,N}\\p_{2,1}\oplus q_{2,1}&p_{2,2}\oplus q_{2,2}&\dots&p_{2,N}\oplus q_{2,N}\\&&\vdots&&\\p_{32,1}\oplus q_{32,1}&p_{32,2}\oplus q_{32,2}&\dots&p_{32,N}\oplus q_{32,N}\end{array}\right]\end{eqnarray}$

（＊23）論理否定（bool型）
$\begin{eqnarray}M_{\small{X}}&=&\left[\left\{\bar{p_{i,j}}\right\}\right]\\&=&\left[\begin{array}{cccc}\bar{p_{1,1}}&\bar{p_{1,2}}&\dots&\bar{p_{1,N}}\\\bar{p_{2,1}}&\bar{p_{2,2}}&\dots&\bar{p_{2,N}}\\&&\vdots&&\\\bar{p_{32,1}}&\bar{p_{32,2}}&\dots&\bar{p_{32,N}}\end{array}\right]\end{eqnarray}$

続いて、循環シフト演算を見てみる。
32bit整数の循環シフトなので、32bitシフトすると元の値に戻るため、32bit以上のシフト幅は考えなくてよい。
よってシフト幅 $s$ を $0\le s\lt 32$ に限定し、次の左循環シフトを考える。

（＊24）左循環シフト（uint型）
$X=P\,\underset{c}{<<}\,s$

式（＊24）を1bit単位で記述し直すと、次のようになる。

（＊25）
$\begin{array}{lclcl}x_{1}&=&p_{1-s+32}&&\\x_{2}&=&p_{2-s+32}&&\\&\vdots&&&\\x_{s}&=&p_{s-s+32}&=&p_{32}\\x_{s+1}&=&p_{\left(s+1\right)-s}&=&p_{1}\\&\vdots&&&\\x_{31}&=&p_{31-s}&&\\x_{32}&=&p_{32-s}&&\end{array}$

（※一般項は $x_{i}=p_{\left(\left(i-s\right)\bmod{32}\right)}$ である。）
代入演算と同様に係数行列を比較して、次のようになる。

（＊26）左循環シフト（bool型）
$\begin{eqnarray}M_{\small{X}}&=&\left[\left\{p_{\left(\left(i-s\right)\bmod{32}\right),j}\right\}\right]\\&=&\left[\begin{array}{cccc}p_{33-s,1}&p_{33-s,2}&\dots&p_{33-s,N}\\p_{34-s,1}&p_{34-s,2}&\dots&p_{34-s,N}\\&&\vdots&&\\p_{32,1}&p_{32,2}&\dots&p_{32,N}\\p_{1,1}&p_{1,2}&\dots&p_{1,N}\\&&\vdots&&\\p_{31-s,1}&p_{31-s,2}&\dots&p_{31-s,N}\\p_{32-s,1}&p_{32-s,2}&\dots&p_{32-s,N}\end{array}\right]\end{eqnarray}$

同様に、右循環シフトは次のようになる。

（＊27）右循環シフト（uint型）
$X=P\,\underset{c}{>>}\,s$

（＊28）
$\begin{array}{lclcl}x_{1}&=&p_{1+s}&&\\x_{2}&=&p_{2+s}&&\\&\vdots&&&\\x_{32-s}&=&p_{\left(32-s\right)+s}&=&p_{32}\\x_{33-s}&=&p_{\left(33-s\right)+s-32}&=&p_{1}\\&\vdots&&&\\x_{31}&=&p_{31+s-32}&=&p_{s-1}\\x_{32}&=&p_{32+s-32}&=&p_{s}\end{array}$

（※一般項は $x_{i}=p_{\left(\left(i+s\right)\bmod{32}\right)}$ である。）

（＊29）右循環シフト（bool型）
$\begin{eqnarray}M_{\small{X}}&=&\left[\left\{p_{\left(\left(i+s\right)\bmod{32}\right),j}\right\}\right]\\&=&\left[\begin{array}{cccc}p_{s+1,1}&p_{s+1,2}&\dots&p_{s+1,N}\\p_{s+2,1}&p_{s+2,2}&\dots&p_{s+2,N}\\&&\vdots&&\\p_{32,1}&p_{32,2}&\dots&p_{32,N}\\p_{1,1}&p_{1,2}&\dots&p_{1,N}\\&&\vdots&&\\p_{s-1,1}&p_{s-1,2}&\dots&p_{s-1,N}\\p_{s,1}&p_{s,2}&\dots&p_{s,N}\end{array}\right]\end{eqnarray}$

最後に、算術和について見てみる。
32bitの算術和演算をすると結果は最大33bit（2変数の場合）になりオーバーフローする可能性があるが、そのオーバーフロー分は無視することになっている。
よって32bit整数の算術和演算は次のように書ける。

（＊30）算術和（uint型）
$X\equiv P+Q\;\pmod{2^{32}}$

（＊30）をbit単位で計算する場合、（＊31）のように書ける。ただし $\left\{c_{i}\right\}$ は繰り上がり項で、（＊32）のように漸化式で表される。
（証明はしないけど「全加算器」あたりで検索すればたくさん出るはず。）

（＊31）
$\begin{array}{lclclcl}x_{1}&=&p_{1}&\oplus&q_{1}&\oplus&c_{1}\\x_{2}&=&p_{2}&\oplus&q_{2}&\oplus&c_{2}\\&\vdots&&&&&\\x_{32}&=&p_{32}&\oplus&q_{32}&\oplus&c_{32}\end{array}$

（＊32）
$\begin{array}{lcl}c_{1}&=&0\\c_{i+1}&=&p_{i}q_{i}\,\oplus\,\left(p_{i}\oplus q_{i}\right)c_{i}\end{array}$

（＊32）の漸化式を解くと $c_{i}$ は次のようになる。

（＊33）
$c_{i}=\bigoplus_{k=1}^{i-1}\left(p_{k}q_{k}\bigcap_{l=k+1}^{i-1}\left(p_{l}\oplus q_{l}\right)\right)$

（＊33）を（＊31）に代入することで次式を得る。

（＊34）
$\begin{array}{lclclclclclcl}x_{1}\left(u_{1},u_{2},\dots,u_{n}\right)&=&p_{1}\oplus q_{1}&\\x_{2}\left(u_{1},u_{2},\dots,u_{n}\right)&=&p_{2}\oplus q_{2}&\oplus&p_{1}q_{1}\\x_{3}\left(u_{1},u_{2},\dots,u_{n}\right)&=&p_{3}\oplus q_{3}&\oplus&p_{2}q_{2}&\oplus&p_{1}q_{1}\left(p_{2}\oplus q_{2}\right)\\x_{4}\left(u_{1},u_{2},\dots,u_{n}\right)&=&p_{4}\oplus q_{4}&\oplus&p_{3}q_{3}&\oplus&p_{2}q_{2}\left(p_{3}\oplus q_{3}\right)&\oplus&p_{1}q_{1}\left(p_{2}\oplus q_{2}\right)\left(p_{3}\oplus q_{3}\right)\\&\vdots&&&&&\\x_{32}\left(u_{1},u_{2},\dots,u_{n}\right)&=&p_{32}\oplus q_{32}&\oplus&p_{31}q_{31}&\oplus&p_{30}q_{30}\left(p_{31}\oplus q_{31}\right)&\oplus&p_{29}q_{29}\left(p_{30}\oplus q_{30}\right)\left(p_{31}\oplus q_{31}\right)&\oplus&\dots&\oplus&p_{1}q_{1}\left(p_{2}\oplus q_{2}\right)\left(p_{3}\oplus q_{3}\right)\dots\left(p_{31}\oplus q_{31}\right)\\\end{array}$

この式中に出てくる演算子は論理積と排他的論理和だけなので、（＊20）（＊22）を繰り返し適用出来る。
そしてその係数行列を比較することで、次のように書ける。

（＊35）算術和（bool型）
$M_{\small{X}}=\left[\left\{p_{i,j}\,\oplus\,q_{i,j}\,\oplus\,\bigoplus_{k=1}^{i-1}\left(p_{k,j}q_{k,j}\bigcap_{l=k+1}^{i-1}\left(p_{l,j}\,\oplus\,q_{l,j}\right)\right)\right\}\right]$

無駄に複雑になるので展開まではしてないが、 $\left(i,j\right)$ 成分は（＊35）のようになる。

以上の結果をまとめよう。
32bit符号なし整数 $P,Q$ の論理積，論理和，排他的論理和，論理否定，算術和，循環シフト，および代入の各演算を、 $P,Q$ の積和標準形の係数 $p_{i,j},q_{i,j}$ で表すと次のようになる。

（＊Ａ）代入
$M_{\small{X}}=\left[\left\{p_{i,j}\right\}\right]$
（＊Ｂ）左循環シフト
$M_{\small{X}}=\left[\left\{p_{\left(\left(i-s\right)\bmod{32}\right),j}\right\}\right]$
（＊Ｃ）右循環シフト
$M_{\small{X}}=\left[\left\{p_{\left(\left(i+s\right)\bmod{32}\right),j}\right\}\right]$
（＊Ｄ）論理積
$M_{\small{X}}=\left[\left\{p_{i,j}q_{i,j}\right\}\right]$
（＊Ｅ）論理和
$M_{\small{X}}=\left[\left\{p_{i,j}\,\cup\,q_{i,j}\right\}\right]$
（＊Ｆ）排他的論理和
$M_{\small{X}}=\left[\left\{p_{i,j}\,\oplus\,q_{i,j}\right\}\right]$
（＊Ｇ）論理否定
$M_{\small{X}}=\left[\left\{\bar{p_{i,j}}\right\}\right]$
（＊Ｈ）算術和
$M_{\small{X}}=\left[\left\{p_{i,j}\,\oplus\,q_{i,j}\,\oplus\,\bigoplus_{k=1}^{i-1}\left(p_{k,j}q_{k,j}\bigcap_{l=k+1}^{i-1}\left(p_{l,j}\,\oplus\,q_{l,j}\right)\right)\right\}\right]$

これらの演算によって得たこの係数行列 $M_{\small{X}}$ の各成分は、右辺の係数行列（この場合は $M_{\small{P}},M_{\small{Q}}$ ）の成分（つまり $p_{1,1},\dots,p_{32,N},q_{1,1},\dots,q_{32,N}$ ）の関数になっている（※ $u_{1},u_{2},\dots,u_{n}$ の関数ではないので注意）。
この $P$ や $Q$ が各種演算によって得たのなら、 $M_{\small{P}},M_{\small{Q}}$ の成分は、それを求めた時の右辺（ $P',Q'$ とする）の係数行列の成分の関数である。
その $P',Q'$ の係数行列 $M_{\small{P'}},M_{\small{Q'}}$ の成分も、それを求めた時の右辺（ $P'',Q''$ とする）の係数行列の成分の関数である。
このように繰り返し遡っていけば、 $M_{\small{X}}$ の各成分は最終的に、ＳＨＡ−１の入力値の係数行列の成分の関数になる。

いや言い方が逆か。
ＳＨＡ−１の入力値に対して、ＳＨＡ−１の計算手順に従って（＊Ａ）〜（＊Ｈ）を繰り返し適用していくことで、ＳＨＡ−１の出力値の係数行列の成分をＳＨＡ−１の入力値の係数行列の成分の関数で記述できる。
よってそれらの式を連立方程式として解けばいいということだ。
……（現実的な時間で）解ければの話だが。

【余談】
なぜこんなめんどうなことをするかというと、簡単にいえばコンピュータに「式」を記憶させるためだ。
例えば $y=ax+b$ という式があったとして、 $a,b,x$ が既知の値なら $y$ には $ax+b$ を計算した値を代入すればいい。
しかし例えば $x$ が未知の値だった場合、 $y$ に $ax+b$ という式を「式として」記憶させることはできない。
いや確かに、強引な方法を使えばできないことはない。例えば"ax+b"のように文字列で記憶させるとか。
でもその方法だとその文字列を構文木解析して数式に戻さないといけない。これ結構面倒なんだよね。
あるいは式を文字列ではなく最初から構文木の形で記憶させる方法もある。
具体的には、「式インターフェース」を継承した「論理積クラス」「論理和クラス」「定数クラス」「未知変数クラス」などを作り、各インスタンスに「式インターフェース」を継承したクラスのインスタンスを0〜2個持たせることで実装できる。
……結局構文木作ってるわけだからこれも面倒なんだけどね。（面倒の一言で済ませてるけど、ただの面倒じゃなくてかなり真剣に面倒なんですよ。）

こういう場合、式を「具体的な定数値」（＝ $a,b$ ）と「計算方法」（＝未知数 $x$ の定数 $a$ 倍に定数 $b$ を加算する）に分けて考えるのがよい。（たぶん。）
「計算方法」を決めておけば、「具体的な定数値」を記憶させるだけで済むからだ。
この記事の方法では、 $M_{\small{X}}$ が「具体的な定数値」に当たり、 $M_{\small{X}}\mathbf{u}$ が「計算方法」に当たる。
特に、未知変数を全部 $\mathbf{u}$ の方にまとめてしまえば係数行列 $M_{\small{X}}$ の成分はすべて定数になるので、コンピュータに記憶させることができる。
その上、（＊Ａ）〜（＊Ｈ）は係数行列どうしの計算で完結してるので、その計算結果も定数であり、やはりコンピュータに記憶させることができる。
これは重要なことだ。……たぶん。

と、今回こんなめんどうなことをしたのは、こういう事情があるから。
他にもっと簡単な方法があるならその方法を使うんだけどね。

【追記】
ここまで書いといて後から気づいたけど、 $X\equiv M_{\small{X}}\mathbf{u}\;\pmod{2}$ のように行列を使って $X$ を32bitずつで表すんじゃなくて、 $\mathbf{x}_{i}\overset{\mathrm{def}}{=}\left(x_{i}\left(0,0,\dots,0\right),x_{i}\left(0,0,\dots,1\right),\dots,x_{i}\left(1,1,\dots,1\right)\right)$ と定義して $x_{i}\equiv\mathbf{x}_{i}\cdot\mathbf{u}\;\pmod{2}$ のようにベクトルの内積を使って $x_{i}$ を1bitずつ表すだけで充分だった。というかそうするべきだった気がする。
……今さら全部書き換えるのめんどうだなぁ。