9.12 SAT と RSA に何の関係が？
以前に第 3.5 節で、命題論理式の充足可能性問題 (SAT) の効率的な判定法が発見されると社会が崩壊する (少なくとも機密情報を安全にやり取りできなくなる) と説明した。なぜだろうか？ まず、RSA の安全性が「巨大な二素数の積は簡単に計算できるのに対して、巨大な二素数の積の素因数分解はおそらく現実的には不可能である」という観察に依拠している事実を思い出してほしい。
第 3.2 節で見たように、任意のデジタル回路は同程度の大きさの命題論理式で表現できる。よってデジタル回路の充足可能性を判定する問題は SAT に等しい (参照: 問題 3.24)。
乗算を表現するデジタル回路は簡単に構築できる。この「積チェッカー」は \(\operatorname{\text{\footnotesize AND}}\), \(\operatorname{\text{\footnotesize OR}}\), \(\operatorname{\text{\footnotesize NOT}}\) ゲートだけを含む \(4n\) 入力 \(1\) 出力のデジタル回路である。入力の最初の \(n\) 個は整数 \(i\) のバイナリ表現、次の \(n\) 個は整数 \(j\) のバイナリ表現、そして最後の \(2n\) 個は整数 \(k\) のバイナリ表現であり、出力は \(ij = k\) が成り立つなら \(1\) となり、成り立たないなら \(0\) となる。単純な構築では \(n^{2}\) に比例する個数のゲートが使われる。
この「積チェッカー」と SAT ソルバーを利用して二進 \(2n\) 桁の任意の整数 \(m\) を素因数分解する方法を示す。まず、積チェッカーの最後の \(2n\) 個の入力 (整数 \(k\) を表す部分) を \(m\) のバイナリ表現で固定する。続いて、整数 \(i\) を表す入力の最初の一桁を \(1\) に固定する。こうした上で、積チェッカーを充足させる残りの \(2n-1\) 個の入力があるかどうかを SAT ソルバーで調べる。つまり、出力が \(1\) となるように \(i\) と \(j\) を表す残りの入力を設定できるかどうかを判定する。そのような設定が存在するなら \(i\) の最初の一桁を \(1\) に固定し、存在しないなら \(i\) の最初の一桁を \(0\) に固定する。これで \(ij = m\) を満たす \(i\) のバイナリ表現の最初の一桁が判明した。
同様の処理で \(i\) の二桁目以降も決定できる。\(i\) の全 \(n\) 桁が決定すれば、\(ij = m\) を満たす \(i > 1\) が手に入る。言い換えれば、\(m\) の約数 \(i\) が見つかる。後は \(m\) を \(i\) で割れば \(j\) が得られる。
よって SAT ソルバーを \(n\) 回使うと \(m\) を素因数分解できる。つまり、\(n^{2}\) に比例する個数のゲートから構成される \(4n\) 入力の回路を表す命題論理式に対する SAT を解く手続きにかかる時間が \(n\) に関する \(d\) 次多項式で抑えられるとき、\(m\) の素因数分解にかかる時間は \(n\) の \(d + 1\) 次多項式で抑えられる。言い換えれば、SAT が多項式時間で解けるなら素因数分解も多項式時間で可能であり、RSA は「簡単に」解読できる。