すべての操作を論理ビットで実行しますが、計算はしません。 論理的な変数のみで動作し、計算の複雑さから震え、無限の期待を予想します。 この世界では、2、3の10ビット数をほとんど乗算できないと無力感を覚えます。
第1章追加
行きましょう。 追加から始めましょう。 数値をビットのシーケンスとして表します
$インライン$ {a0、a1、a2、a3 ...}、$インライン$
$インライン$ {b0、b1、b2、b3 ...}、$インライン$
$インライン$ {x0、x1、x2、x3 ...}、$インライン$
どこで $インライン$ a0、b0 $インライン$ -低ビット。
変数の下 $インライン$ x $インライン$ 私は操作の結果を意味します。
これらの数字を追加してみましょう。 合計のゼロビットは何ですか？ ビットが $インライン$ a0 $インライン$ そして $インライン$ b0 $インライン$ 等しい $インライン$ x0 $インライン$ ゼロになり、そうでなければ1になります。 $インライン$ x0 = a0 \ XOR \ b0 $インライン$ 。 さらに、論理演算子は、次のように貴重なインターネットスペースを節約するために簡単に記述されます。 $インライン$ AND \ equiv $インライン$ *、 $インライン$または\ equiv $インライン$ +。
今最初のビット。 両方のゼロビットが1に等しい場合、ゼロビットに依存し、最初のビットにビットが追加されます。 このコンポーネントをキャリービットと呼びます。 合計で、最初のビットに影響を与える3つのコンポーネントがあります。 それは $インライン$ a1、b1 $インライン$ そして $インライン$（a0 * b0）$インライン$ 。
これらのコンポーネントの1つが1つまたは3つすべてに等しい場合、最初のビットは1に等しくなります。 これは次のように書かれています。
$ inline $ a1 * b1 *（a0 * b0）+！a1 * b1 *（a0 * b0）+ a1 *！b1 *（a0 * b0）+ a1 * b1 *！（a0 * b0）$ inline $ 。
ホラー 私は今それを書いたかどうかすらわかりません。
便宜上三項演算を導入しました $インライン$ XOR3 $インライン$ -奇数の引数が1に等しいときに1を返します。
次に、2番目のビット。 すべては彼と同じです-彼は3つのコンポーネントに依存しています： $インライン$ a2、b2 $インライン$ 、および最初のビットからのキャリービット。 現在、最初のビットのキャリービットは3つのコンポーネントに依存しています。 $インライン$ a1、b1 $インライン$ 、および前のキャリービット。 これら3つのコンポーネントのうち2つが1に等しい場合、キャリービットも1になります。 この三項関数は $インライン$ AND3 $インライン$ ：3ビットのうち2ビットが1に等しい場合、1を返します。 式はより単純です： $インライン$ AND3（a、b、c）=（a * b）+（a * c）+（b * c）。$インライン$
さて、次のビットは2番目のビットと同じ方法で決定されます。 ループでは、次のようになります。キャリービットをカウントします $インライン$ p（i-1）$インライン$ 、結果ビットを考慮 $インライン$ x（i）$インライン$
$インライン$ p2 = AND3（a2、b2、p1）$インライン$
$インライン$ x3 = XOR3（a3、b3、p2）$インライン$
$インライン$ p3 = AND3（a3、b3、p2）$インライン$
...
ここで、数字を追加する方法を学びました。
5ビット数の合計は次のようになります
------------ビット0 -----------------
！a0 * b0または
a0 *！b0
------------ビット1 -----------------
a0 * a1 * b0 * b1 OR
！a1 *！b0 * b1または
！a0 *！a1 * b1 OR
a0 *！a1 * b0 *！b1 OR
a1 *！b0 *！b1 OR
！a0 * a1 *！b1
------------ビット2 -----------------
a0 * a2 * b0 * b1 * b2 OR
！a1 * a2 *！b0 *！b2または
！a0 *！a1 *！a2 * b2または
！a2 *！b0 *！b1 * b2または
！a0 *！a2 *！b1 * b2または
！a0 *！a1 * a2 *！b2または
a0 * a1 * a2 * b0 * b2 OR
a1 * a2 * b1 * b2または
a2 *！b0 *！b1 *！b2または
！a0 * a2 *！b1 *！b2または
a0 * a1 *！a2 * b0 *！b2または
！a1 *！a2 *！b1 * b2または
！a1 *！a2 *！b0 * b2または
！a1 * a2 *！b1 *！b2または
a0 *！a2 * b0 * b1 *！b2または
a1 *！a2 * b1 *！b2
------------ビット3 -----------------
a2 * a3 * b2 * b3 OR
a2 *！a3 * b2 *！b3 OR
a3 *！b0 *！b1 *！b2 *！b3または
！a1 *！a2 *！a3 *！b0 * b3または
a0 * a1 * a2 *！a3 * b0 *！b3 OR
！a3 *！b0 *！b1 *！b2 * b3または
！a0 *！a2 *！a3 *！b1 * b3または
a1 * a3 * b1 * b2 * b3または
a0 * a2 * a3 * b0 * b1 * b3または
！a0 *！a1 *！a3 *！b2 * b3または
！a0 *！a3 *！b1 *！b2 * b3または
！a0 *！a1 * a3 *！b2 *！b3または
！a2 *！a3 *！b0 *！b1 * b3または
a0 * a1 * a3 * b0 * b2 * b3 OR
a0 * a1 * a2 * a3 * b0 * b3 OR
a0 * a2 *！a3 * b0 * b1 *！b3 OR
！a1 *！a3 *！b1 *！b2 * b3または
！a0 * a3 *！b1 *！b2 *！b3または
！a2 * a3 *！b0 *！b1 *！b3または
！a2 *！a3 *！b2 * b3または
！a1 * a3 *！b0 *！b2 *！b3または
a0 *！a3 * b0 * b1 * b2 *！b3 OR
！a0 *！a1 *！a2 * a3 *！b3 OR
！a0 *！a2 * a3 *！b1 *！b3または
！a1 *！a2 *！a3 *！b1 * b3または
！a0 *！a1 *！a2 *！a3 * b3または
！a2 * a3 *！b2 *！b3 OR
a0 * a1 *！a3 * b0 * b2 *！b3 OR
a1 *！a3 * b1 * b2 *！b3または
a1 * a2 *！a3 * b1 *！b3または
a0 * a3 * b0 * b1 * b2 * b3または
！a1 *！a2 * a3 *！b0 *！b3または
！a1 *！a3 *！b0 *！b2 * b3または
！a1 * a3 *！b1 *！b2 *！b3または
a1 * a2 * a3 * b1 * b3または
！a1 *！a2 * a3 *！b1 *！b3
------------ビット4 -----------------
！a0 *！a2 *！a3 * a4 *！b1 *！b4 OR
！a0 *！a3 * a4 *！b1 *！b2 *！b4または
a3 *！a4 * b3 *！b4 OR
a3 * a4 * b3 * b4 OR
！a0 *！a1 *！a3 * a4 *！b2 *！b4または
a0 * a2 *！a4 * b0 * b1 * b3 *！b4 OR
！a2 *！a3 *！a4 *！b2 * b4または
a4 *！b0 *！b1 *！b2 *！b3 *！b4または
a0 * a1 * a2 * a3 * a4 * b0 * b4 OR
！a2 *！a4 *！b2 *！b3 * b4または
！a1 *！a2 *！a4 *！b1 *！b3 * b4または
！a1 * a4 *！b1 *！b2 *！b3 *！b4または
！a1 *！a3 *！a4 *！b0 *！b2 * b4または
a0 * a1 * a2 * a3 *！a4 * b0 *！b4 OR
！a1 *！a2 *！a3 *！a4 *！b0 * b4または
a1 * a3 * a4 * b1 * b2 * b4または
a2 * a4 * b2 * b3 * b4または
a0 *！a4 * b0 * b1 * b2 * b3 *！b4 OR
！a2 * a4 *！b0 *！b1 *！b3 *！b4または
a0 * a4 * b0 * b1 * b2 * b3 * b4 OR
！a0 *！a1 *！a3 *！a4 *！b2 * b4または
a0 * a1 * a3 *！a4 * b0 * b2 *！b4 OR
a1 * a2 * a3 * a4 * b1 * b4または
a1 * a2 *！a4 * b1 * b3 *！b4 OR
a0 * a2 * a3 * a4 * b0 * b1 * b4 OR
a2 *！a4 * b2 * b3 *！b4または
a0 * a1 * a2 *！a4 * b0 * b3 *！b4 OR
！a0 *！a4 *！b1 *！b2 *！b3 * b4または
！a1 *！a2 *！a3 * a4 *！b0 *！b4または
！a0 *！a1 * a4 *！b2 *！b3 *！b4または
！a0 *！a1 *！a2 *！a3 * a4 *！b4 OR
a0 * a1 *！a4 * b0 * b2 * b3 *！b4 OR
a1 * a2 * a3 *！a4 * b1 *！b4 OR
a1 * a2 * a4 * b1 * b3 * b4または
！a1 *！a2 *！a3 *！a4 *！b1 * b4または
！a4 *！b0 *！b1 *！b2 *！b3 * b4または
a1 * a3 *！a4 * b1 * b2 *！b4 OR
a0 * a1 * a3 * a4 * b0 * b2 * b4 OR
！a2 *！a3 *！a4 *！b0 *！b1 * b4または
！a1 *！a2 * a4 *！b0 *！b3 *！b4または
！a0 *！a1 *！a2 *！a4 *！b3 * b4または
！a0 *！a1 *！a2 * a4 *！b3 *！b4または
a2 * a3 * a4 * b2 * b4または
！a1 *！a3 * a4 *！b1 *！b2 *！b4または
！a3 *！a4 *！b3 * b4または
a0 * a1 * a4 * b0 * b2 * b3 * b4 OR
！a1 *！a4 *！b1 *！b2 *！b3 * b4または
！a0 *！a3 *！a4 *！b1 *！b2 * b4または
！a1 *！a3 *！a4 *！b1 *！b2 * b4または
a2 * a3 *！a4 * b2 *！b4または
！a2 *！a3 * a4 *！b2 *！b4または
a0 * a3 *！a4 * b0 * b1 * b2 *！b4 OR
a1 *！a4 * b1 * b2 * b3 *！b4 OR
a0 * a3 * a4 * b0 * b1 * b2 * b4 OR
！a2 *！a3 * a4 *！b0 *！b1 *！b4または
！a1 * a4 *！b0 *！b2 *！b3 *！b4または
！a1 *！a2 *！a3 * a4 *！b1 *！b4または
！a3 * a4 *！b0 *！b1 *！b2 *！b4または
！a1 *！a3 * a4 *！b0 *！b2 *！b4または
！a3 *！a4 *！b0 *！b1 *！b2 * b4または
！a0 * a4 *！b1 *！b2 *！b3 *！b4または
a1 * a4 * b1 * b2 * b3 * b4または
！a0 *！a2 * a4 *！b1 *！b3 *！b4または
！a0 *！a1 *！a4 *！b2 *！b3 * b4または
！a0 *！a1 *！a2 *！a3 *！a4 * b4または
！a1 *！a2 *！a4 *！b0 *！b3 * b4または
！a2 * a4 *！b2 *！b3 *！b4または
！a0 *！a2 *！a4 *！b1 *！b3 * b4または
！a2 *！a4 *！b0 *！b1 *！b3 * b4または
a0 * a2 * a4 * b0 * b1 * b3 * b4 OR
！a0 *！a2 *！a3 *！a4 *！b1 * b4または
！a3 * a4 *！b3 *！b4 OR
！a1 *！a4 *！b0 *！b2 *！b3 * b4または
a0 * a2 * a3 *！a4 * b0 * b1 *！b4または
！a1 *！a2 * a4 *！b1 *！b3 *！b4または
a0 * a1 * a2 * a4 * b0 * b3 * b4
------------ビット5 -----------------
a0 * a1 * a4 * b0 * b2 * b3または
a2 * a3 * b2 * b4 OR
a1 * a2 * a3 * a4 * b1 OR
a2 * b2 * b3 * b4または
a0 * a1 * a3 * a4 * b0 * b2または
a0 * a4 * b0 * b1 * b2 * b3または
a1 * a4 * b1 * b2 * b3または
a0 * a2 * b0 * b1 * b3 * b4 OR
a1 * a3 * b1 * b2 * b4または
a2 * a4 * b2 * b3または
a0 * a1 * a2 * b0 * b3 * b4 OR
a0 * b0 * b1 * b2 * b3 * b4または
a0 * a1 * a3 * b0 * b2 * b4 OR
a0 * a1 * b0 * b2 * b3 * b4 OR
a1 * a2 * a3 * b1 * b4 OR
a4 * b4 OR
a2 * a3 * a4 * b2 OR
a0 * a1 * a2 * a3 * b0 * b4 OR
a1 * a2 * b1 * b3 * b4または
a1 * a2 * a4 * b1 * b3または
a3 * a4 * b3または
a0 * a1 * a2 * a3 * a4 * b0または
a1 * b1 * b2 * b3 * b4または
a1 * a3 * a4 * b1 * b2または
a0 * a3 * a4 * b0 * b1 * b2または
a0 * a2 * a3 * b0 * b1 * b4 OR
a0 * a3 * b0 * b1 * b2 * b4 OR
a0 * a2 * a3 * a4 * b0 * b1または
a0 * a1 * a2 * a4 * b0 * b3 OR
a3 * b3 * b4または
a0 * a2 * a4 * b0 * b1 * b3
！a0 * b0または
a0 *！b0
------------ビット1 -----------------
a0 * a1 * b0 * b1 OR
！a1 *！b0 * b1または
！a0 *！a1 * b1 OR
a0 *！a1 * b0 *！b1 OR
a1 *！b0 *！b1 OR
！a0 * a1 *！b1
------------ビット2 -----------------
a0 * a2 * b0 * b1 * b2 OR
！a1 * a2 *！b0 *！b2または
！a0 *！a1 *！a2 * b2または
！a2 *！b0 *！b1 * b2または
！a0 *！a2 *！b1 * b2または
！a0 *！a1 * a2 *！b2または
a0 * a1 * a2 * b0 * b2 OR
a1 * a2 * b1 * b2または
a2 *！b0 *！b1 *！b2または
！a0 * a2 *！b1 *！b2または
a0 * a1 *！a2 * b0 *！b2または
！a1 *！a2 *！b1 * b2または
！a1 *！a2 *！b0 * b2または
！a1 * a2 *！b1 *！b2または
a0 *！a2 * b0 * b1 *！b2または
a1 *！a2 * b1 *！b2
------------ビット3 -----------------
a2 * a3 * b2 * b3 OR
a2 *！a3 * b2 *！b3 OR
a3 *！b0 *！b1 *！b2 *！b3または
！a1 *！a2 *！a3 *！b0 * b3または
a0 * a1 * a2 *！a3 * b0 *！b3 OR
！a3 *！b0 *！b1 *！b2 * b3または
！a0 *！a2 *！a3 *！b1 * b3または
a1 * a3 * b1 * b2 * b3または
a0 * a2 * a3 * b0 * b1 * b3または
！a0 *！a1 *！a3 *！b2 * b3または
！a0 *！a3 *！b1 *！b2 * b3または
！a0 *！a1 * a3 *！b2 *！b3または
！a2 *！a3 *！b0 *！b1 * b3または
a0 * a1 * a3 * b0 * b2 * b3 OR
a0 * a1 * a2 * a3 * b0 * b3 OR
a0 * a2 *！a3 * b0 * b1 *！b3 OR
！a1 *！a3 *！b1 *！b2 * b3または
！a0 * a3 *！b1 *！b2 *！b3または
！a2 * a3 *！b0 *！b1 *！b3または
！a2 *！a3 *！b2 * b3または
！a1 * a3 *！b0 *！b2 *！b3または
a0 *！a3 * b0 * b1 * b2 *！b3 OR
！a0 *！a1 *！a2 * a3 *！b3 OR
！a0 *！a2 * a3 *！b1 *！b3または
！a1 *！a2 *！a3 *！b1 * b3または
！a0 *！a1 *！a2 *！a3 * b3または
！a2 * a3 *！b2 *！b3 OR
a0 * a1 *！a3 * b0 * b2 *！b3 OR
a1 *！a3 * b1 * b2 *！b3または
a1 * a2 *！a3 * b1 *！b3または
a0 * a3 * b0 * b1 * b2 * b3または
！a1 *！a2 * a3 *！b0 *！b3または
！a1 *！a3 *！b0 *！b2 * b3または
！a1 * a3 *！b1 *！b2 *！b3または
a1 * a2 * a3 * b1 * b3または
！a1 *！a2 * a3 *！b1 *！b3
------------ビット4 -----------------
！a0 *！a2 *！a3 * a4 *！b1 *！b4 OR
！a0 *！a3 * a4 *！b1 *！b2 *！b4または
a3 *！a4 * b3 *！b4 OR
a3 * a4 * b3 * b4 OR
！a0 *！a1 *！a3 * a4 *！b2 *！b4または
a0 * a2 *！a4 * b0 * b1 * b3 *！b4 OR
！a2 *！a3 *！a4 *！b2 * b4または
a4 *！b0 *！b1 *！b2 *！b3 *！b4または
a0 * a1 * a2 * a3 * a4 * b0 * b4 OR
！a2 *！a4 *！b2 *！b3 * b4または
！a1 *！a2 *！a4 *！b1 *！b3 * b4または
！a1 * a4 *！b1 *！b2 *！b3 *！b4または
！a1 *！a3 *！a4 *！b0 *！b2 * b4または
a0 * a1 * a2 * a3 *！a4 * b0 *！b4 OR
！a1 *！a2 *！a3 *！a4 *！b0 * b4または
a1 * a3 * a4 * b1 * b2 * b4または
a2 * a4 * b2 * b3 * b4または
a0 *！a4 * b0 * b1 * b2 * b3 *！b4 OR
！a2 * a4 *！b0 *！b1 *！b3 *！b4または
a0 * a4 * b0 * b1 * b2 * b3 * b4 OR
！a0 *！a1 *！a3 *！a4 *！b2 * b4または
a0 * a1 * a3 *！a4 * b0 * b2 *！b4 OR
a1 * a2 * a3 * a4 * b1 * b4または
a1 * a2 *！a4 * b1 * b3 *！b4 OR
a0 * a2 * a3 * a4 * b0 * b1 * b4 OR
a2 *！a4 * b2 * b3 *！b4または
a0 * a1 * a2 *！a4 * b0 * b3 *！b4 OR
！a0 *！a4 *！b1 *！b2 *！b3 * b4または
！a1 *！a2 *！a3 * a4 *！b0 *！b4または
！a0 *！a1 * a4 *！b2 *！b3 *！b4または
！a0 *！a1 *！a2 *！a3 * a4 *！b4 OR
a0 * a1 *！a4 * b0 * b2 * b3 *！b4 OR
a1 * a2 * a3 *！a4 * b1 *！b4 OR
a1 * a2 * a4 * b1 * b3 * b4または
！a1 *！a2 *！a3 *！a4 *！b1 * b4または
！a4 *！b0 *！b1 *！b2 *！b3 * b4または
a1 * a3 *！a4 * b1 * b2 *！b4 OR
a0 * a1 * a3 * a4 * b0 * b2 * b4 OR
！a2 *！a3 *！a4 *！b0 *！b1 * b4または
！a1 *！a2 * a4 *！b0 *！b3 *！b4または
！a0 *！a1 *！a2 *！a4 *！b3 * b4または
！a0 *！a1 *！a2 * a4 *！b3 *！b4または
a2 * a3 * a4 * b2 * b4または
！a1 *！a3 * a4 *！b1 *！b2 *！b4または
！a3 *！a4 *！b3 * b4または
a0 * a1 * a4 * b0 * b2 * b3 * b4 OR
！a1 *！a4 *！b1 *！b2 *！b3 * b4または
！a0 *！a3 *！a4 *！b1 *！b2 * b4または
！a1 *！a3 *！a4 *！b1 *！b2 * b4または
a2 * a3 *！a4 * b2 *！b4または
！a2 *！a3 * a4 *！b2 *！b4または
a0 * a3 *！a4 * b0 * b1 * b2 *！b4 OR
a1 *！a4 * b1 * b2 * b3 *！b4 OR
a0 * a3 * a4 * b0 * b1 * b2 * b4 OR
！a2 *！a3 * a4 *！b0 *！b1 *！b4または
！a1 * a4 *！b0 *！b2 *！b3 *！b4または
！a1 *！a2 *！a3 * a4 *！b1 *！b4または
！a3 * a4 *！b0 *！b1 *！b2 *！b4または
！a1 *！a3 * a4 *！b0 *！b2 *！b4または
！a3 *！a4 *！b0 *！b1 *！b2 * b4または
！a0 * a4 *！b1 *！b2 *！b3 *！b4または
a1 * a4 * b1 * b2 * b3 * b4または
！a0 *！a2 * a4 *！b1 *！b3 *！b4または
！a0 *！a1 *！a4 *！b2 *！b3 * b4または
！a0 *！a1 *！a2 *！a3 *！a4 * b4または
！a1 *！a2 *！a4 *！b0 *！b3 * b4または
！a2 * a4 *！b2 *！b3 *！b4または
！a0 *！a2 *！a4 *！b1 *！b3 * b4または
！a2 *！a4 *！b0 *！b1 *！b3 * b4または
a0 * a2 * a4 * b0 * b1 * b3 * b4 OR
！a0 *！a2 *！a3 *！a4 *！b1 * b4または
！a3 * a4 *！b3 *！b4 OR
！a1 *！a4 *！b0 *！b2 *！b3 * b4または
a0 * a2 * a3 *！a4 * b0 * b1 *！b4または
！a1 *！a2 * a4 *！b1 *！b3 *！b4または
a0 * a1 * a2 * a4 * b0 * b3 * b4
------------ビット5 -----------------
a0 * a1 * a4 * b0 * b2 * b3または
a2 * a3 * b2 * b4 OR
a1 * a2 * a3 * a4 * b1 OR
a2 * b2 * b3 * b4または
a0 * a1 * a3 * a4 * b0 * b2または
a0 * a4 * b0 * b1 * b2 * b3または
a1 * a4 * b1 * b2 * b3または
a0 * a2 * b0 * b1 * b3 * b4 OR
a1 * a3 * b1 * b2 * b4または
a2 * a4 * b2 * b3または
a0 * a1 * a2 * b0 * b3 * b4 OR
a0 * b0 * b1 * b2 * b3 * b4または
a0 * a1 * a3 * b0 * b2 * b4 OR
a0 * a1 * b0 * b2 * b3 * b4 OR
a1 * a2 * a3 * b1 * b4 OR
a4 * b4 OR
a2 * a3 * a4 * b2 OR
a0 * a1 * a2 * a3 * b0 * b4 OR
a1 * a2 * b1 * b3 * b4または
a1 * a2 * a4 * b1 * b3または
a3 * a4 * b3または
a0 * a1 * a2 * a3 * a4 * b0または
a1 * b1 * b2 * b3 * b4または
a1 * a3 * a4 * b1 * b2または
a0 * a3 * a4 * b0 * b1 * b2または
a0 * a2 * a3 * b0 * b1 * b4 OR
a0 * a3 * b0 * b1 * b2 * b4 OR
a0 * a2 * a3 * a4 * b0 * b1または
a0 * a1 * a2 * a4 * b0 * b3 OR
a3 * b3 * b4または
a0 * a2 * a4 * b0 * b1 * b3
はい、この数字にはもう1つあります。数字の合計が1つの新しいビットを与えることができます。
しかし、量の各ビットに非常に多くのメンバー
ビット0：2
ビート1：6
ビート2：16
ビート3：36
ビート4で：76
ビート5：156
ビート6：316
ビート7：636
8時：1276
ビット9：2556
ビット10：1023
ビート1：6
ビート2：16
ビート3：36
ビート4で：76
ビート5：156
ビート6：316
ビート7：636
8時：1276
ビット9：2556
ビット10：1023
用語とは、式が選言標準形に縮小された後の用語を意味します（同じ用語を思いついた）、言い換えると、形式に縮小した後、5ビットの合計が上に書き込まれます。
第2章乗算
第2章、乗算。 私たちは追加することを学んだので、それを増やすことができます！ はい、学校で教えられているように、2進数のみのコラムです。 ループでは、次のようになります。第1オペランドに、ビット単位でシフトされた第2オペランドを追加します。 $インライン$ i $インライン$ ビット、各ビットで乗算 $インライン$ i $インライン$ 第1オペランドの第1ビット。 どうやらこれは擬似コードでより明確に見えるでしょう：
var big, small // for (int i = 0; i < small.bits.size(); i++ ) { var big_tmp = big; for (int j = 0; j < big.bits.size(); j++) { big_tmp.bits[j] = big.bits[j] * small.bits[i]; } result = (result + big_tmp.operator_SHIFT_LEFT(i)); }
長さmとnビットの数を乗算すると、長さm + nビットの数になります。
乗算の結果を単純化するには多くのリソースが必要であり、非常に多項式に見えます。3ビット数の積は次のとおりです。
ショー
------------ビット0 -----------------
a0 * b0
------------ビット1 -----------------
a1 * b0 *！b1 OR
！a0 * a1 * b0または
a0 *！b0 * b1または
a0 *！a1 * b1
------------ビット2 -----------------
！a0 *！a1 * a2 * b0または
a0 *！b0 *！b1 * b2または
a0 *！a1 *！b0 * b2または
a0 * a1 * a2 * b0 * b1 *！b2 OR
a0 *！a2 *！b1 * b2または
！a0 * a1 *！a2 * b1 OR
a0 *！a2 * b0 * b2または
a0 *！a1 *！a2 * b2または
a2 * b0 *！b1 *！b2または
a1 *！b0 * b1 *！b2または
！a1 * a2 * b0 *！b2 OR
！a0 * a2 * b0 *！b1 OR
！a0 * a1 *！b0 * b1
------------ビット3 -----------------
！a0 * a1 * b0 * b2 OR
a0 * a1 * a2 *！b0 * b1 * b2または
！a1 * a2 * b1 *！b2 OR
a2 *！b0 * b1 *！b2または
a0 *！a1 * a2 * b0 *！b1 * b2または
！a0 * a1 *！a2 * b2 OR
a1 *！b0 *！b1 * b2または
！a0 *！a1 * a2 * b1 OR
a1 *！a2 *！b1 * b2または
a0 * a1 *！a2 * b0 * b1 *！b2または
！a1 * a2 *！b0 * b1 OR
！a0 * a1 *！b1 * b2
------------ビット4 -----------------
！a0 *！a1 * a2 * b2または
！a1 * a2 *！b1 * b2または
a0 * a1 * a2 * b0 * b1 * b2または
a2 *！b0 *！b1 * b2または
！a1 * a2 *！b0 * b2または
a0 * a1 *！a2 *！b0 * b1 * b2または
！a0 * a2 *！b1 * b2または
a1 * a2 * b0 * b1 *！b2 OR
a0 * a1 *！a2 * b0 * b1 * b2
------------ビット5 -----------------
a0 * a1 * a2 * b0 *！b1 * b2 OR
a1 * a2 *！b0 * b1 * b2または
a1 * a2 * b0 * b1 * b2または
a0 *！a1 * a2 * b0 * b1 * b2
a0 * b0
------------ビット1 -----------------
a1 * b0 *！b1 OR
！a0 * a1 * b0または
a0 *！b0 * b1または
a0 *！a1 * b1
------------ビット2 -----------------
！a0 *！a1 * a2 * b0または
a0 *！b0 *！b1 * b2または
a0 *！a1 *！b0 * b2または
a0 * a1 * a2 * b0 * b1 *！b2 OR
a0 *！a2 *！b1 * b2または
！a0 * a1 *！a2 * b1 OR
a0 *！a2 * b0 * b2または
a0 *！a1 *！a2 * b2または
a2 * b0 *！b1 *！b2または
a1 *！b0 * b1 *！b2または
！a1 * a2 * b0 *！b2 OR
！a0 * a2 * b0 *！b1 OR
！a0 * a1 *！b0 * b1
------------ビット3 -----------------
！a0 * a1 * b0 * b2 OR
a0 * a1 * a2 *！b0 * b1 * b2または
！a1 * a2 * b1 *！b2 OR
a2 *！b0 * b1 *！b2または
a0 *！a1 * a2 * b0 *！b1 * b2または
！a0 * a1 *！a2 * b2 OR
a1 *！b0 *！b1 * b2または
！a0 *！a1 * a2 * b1 OR
a1 *！a2 *！b1 * b2または
a0 * a1 *！a2 * b0 * b1 *！b2または
！a1 * a2 *！b0 * b1 OR
！a0 * a1 *！b1 * b2
------------ビット4 -----------------
！a0 *！a1 * a2 * b2または
！a1 * a2 *！b1 * b2または
a0 * a1 * a2 * b0 * b1 * b2または
a2 *！b0 *！b1 * b2または
！a1 * a2 *！b0 * b2または
a0 * a1 *！a2 *！b0 * b1 * b2または
！a0 * a2 *！b1 * b2または
a1 * a2 * b0 * b1 *！b2 OR
a0 * a1 *！a2 * b0 * b1 * b2
------------ビット5 -----------------
a0 * a1 * a2 * b0 *！b1 * b2 OR
a1 * a2 *！b0 * b1 * b2または
a1 * a2 * b0 * b1 * b2または
a0 *！a1 * a2 * b0 * b1 * b2
しかし、6x6ピースのビットに含まれるメンバーの数
ビット0：1
ビート1：4
ビート2：13
ビート3：41
ビート4：168
ビート5：656
ビート6：791
ビート7：778
ビート8：606
ビット9：402
ビート10で：240
11時135分
ビート1：4
ビート2：13
ビート3：41
ビート4：168
ビート5：656
ビート6：791
ビート7：778
ビート8：606
ビット9：402
ビート10で：240
11時135分
しかし、これは、面倒な複数階の式を乗算から単純化するためのオプションの1つにすぎません。 上位ビットの他の値を取得する場合がありますが、それは論理式をどれだけ単純化できるかに依存します。
したがって、加算と乗算を行うことができます。 特別な計算コストなしで再帰式を取得できます。これにより、合計、積、または数値に関するその他の複合演算が考慮されます。 しかし、判明したように、許容できる時間内に10ビットを超える数値の場合、この式を単純化することはできません。 8x8ピースの表現を単純化することはほとんどできませんでした。
この段階で、私は最初のトラブルに遭遇しました。 小さな注文の単純化された作品を見て、ある種の依存関係を見つけ、そのような公式を構築することを学ぶことは可能ですか？
加算と乗算の結果として、aとbに関して対称性がなければなりません。下位ビットでは肉眼で見ることができ、上位ビットで見るためには目を武装しなければなりません。
だから、最下位ビットを見ることで加算/乗算の最上位ビットの式を構築することは可能ですか？ 私は成功しませんでした
しかし、コインには裏返しがあります。単純化された式は間違いなく多くのスペースを占有するため、2つの1024ビット数の積を単純化するのは意味がありません。 しかし、誰もが1024ビット（特に素数）の数値を乗算することに興味がありますよね？ ネストされた論理式を操作することを学ぶ必要があります。
互いに埋め込まれたものを含む選言的標準形に縮小された論理式で動作する小さなコードを書くことは難しくありませんでした。 まあ、私は飲酒をやめ、プログラミングを学び、仕事をやめる必要がありました。
第3章、最も興味深い
md5を例にとります。 64同じラウンドについて退屈。 計算では、通常の論理演算子と上記の合計のみが使用されます。 32より古いビットのみが破棄されます。 さて、ネストされたビット式を使用してmd5を計算できます。
大体このように見えます。
たとえば、入力md5は128個の論理変数です。 ネストされた変数をtと呼び、メイン変数の後に番号を付け始めます。 この場合、メイン変数（md5関数の入力に供給される変数）は、 $インライン$ x0 $インライン$ 前に $インライン$ x127 $インライン$ 、ネストされたものは $インライン$ t128 $インライン$ 。 次に、結果の最初のビットはこのようなものになります（すべてアルゴリズムのどのポイントで式をt変数に折り畳むかによって異なります）。
たとえば、
md5 [0] =
t67168 * t70255または
t67167 * t70255または
t67163 * t67169 * t70255または
！t65928 *！t65929 *！t65930 * t65936 * t67155 * t67169 * t70255または
t65929 * t65937 * t67155 * t67169 * t70255または
！t65928 *！t65929 *！t65930 * t65938 * t67155 * t67169 * t70255または
t65928 * t65937 * t67155 * t67169 * t70255または
t65929 * t65939 * t67155 * t67169 * t70255または
t65928 * t65939 * t67155 * t67169 * t70255または
t67162 * t67169 * t70255または
t67166 * t70255または
t65937 * t65930 * t67155 * t67169 * t70255または
t65930 * t65939 * t67155 * t67169 * t70255
t67168 * t70255または
t67167 * t70255または
t67163 * t67169 * t70255または
！t65928 *！t65929 *！t65930 * t65936 * t67155 * t67169 * t70255または
t65929 * t65937 * t67155 * t67169 * t70255または
！t65928 *！t65929 *！t65930 * t65938 * t67155 * t67169 * t70255または
t65928 * t65937 * t67155 * t67169 * t70255または
t65929 * t65939 * t67155 * t67169 * t70255または
t65928 * t65939 * t67155 * t67169 * t70255または
t67162 * t67169 * t70255または
t67166 * t70255または
t65937 * t65930 * t67155 * t67169 * t70255または
t65930 * t65939 * t67155 * t67169 * t70255
ここで、各t変数は異なる式です。
そして、チェーンの終わりにこのようなもの
t219 =
！x6 * t139 * t217または
！x6 * t140 * t217または
t211 *！t135 * t217または
！x6 * t211 * t217または
！x10 * t139 * t217または
！x10 * t211 * t217または
！x8 * t211 * t217または
！x8 * t139 * t217または
！x9 * t140 * t217または
！x8 * t140 * t217または
！x9 * t139 * t217または
！x10 * t140 * t217または
！t135 * t140 * t217または
！x9 * t211 * t217または
！t135 * t139 * t217
...
t128 =
x0または
x5 OR
x6 OR
x4 OR
x8 OR
x7 OR
x9 OR
x3 OR
x10 OR
x2 OR
x1
！x6 * t139 * t217または
！x6 * t140 * t217または
t211 *！t135 * t217または
！x6 * t211 * t217または
！x10 * t139 * t217または
！x10 * t211 * t217または
！x8 * t211 * t217または
！x8 * t139 * t217または
！x9 * t140 * t217または
！x8 * t140 * t217または
！x9 * t139 * t217または
！x10 * t140 * t217または
！t135 * t140 * t217または
！x9 * t211 * t217または
！t135 * t139 * t217
...
t128 =
x0または
x5 OR
x6 OR
x4 OR
x8 OR
x7 OR
x9 OR
x3 OR
x10 OR
x2 OR
x1
ご存じのとおり、128ビットのmd5関数の複雑さはおよそ70,000に等しいため、結果として〜70,000のt変数が得られます。 判明したとおり、15、256、347、または512の変数を入力に適用すると、ネスト（つまり、t変数の数）はほぼ同じになります。 ここで重要な予約をする必要があります。 論理式の計算中にt変数を作成する操作は、論理演算子の後に適用されます $インライン$および$インライン$ そして $インライン$ AND3 $インライン$ 後 $インライン$または$インライン$ そして $インライン$ XOR3 $インライン$ 単純化が実行され、そのような結果が得られます。
したがって、md5のネストされた複雑さは70Kです。 各ビットのt変数の結果の式は、論理表現変数と呼ばれます。
そして今。 次に、次のことを行います。 ハッシュを取得し、ビット形式で表します。 ハッシュビットが0の場合、対応する論理表現変数を取得します。1は反転します（演算子 $インライン$ NOT $インライン$ ） そして、それらを演算子に追加します $インライン$または$インライン$ 。 その結果、新しいネストされた論理式を取得し、それを $インライン$ FALSE $インライン$ 。
この表現はどういう意味ですか？ そして、それは与えられたハッシュに対して可能なすべての解決策を説明しています。 また、t変数を置き換えて単純化すると、ソリューションが完全に表示されます。 それは単に単純化するだけで機能しません。 この段階では、高品質のリップシーラーを購入する必要がありました。
まあ、それを単純化することはできませんが、少なくとも1つの可能な解決策を覗き見することは、少なくともあなたの目の前ではできません。実際、なぜすべてが必要なのか、少なくとも1つが必要です... 次と等しい論理式があります $インライン$ FALSE $インライン$ 。 これは、簡素化のある段階で、あるメンバーが $インライン$ TRUE $インライン$ ハッシュには解決策がありません。 式の単純化を開始すると、何人のメンバーが自己破壊し、 $インライン$ FALSE $インライン$ 。 つまり、t変数を代入した後、次のようになります $ inline $ t67234 \ * \！t67234 * ... $ inline $ つまり、どの用語が同じであるかを事前に知っていれば $インライン$ FALSE $インライン$ 、このような用語でt変数を代入するという計算上の地獄を避けることができます。
だから、私は厳declareに宣言します。 計算上の地獄の観点からネストされた論理式を解く問題は、同じように等しい用語の定義に帰着します $インライン$ FALSE $インライン$ 。 以上です。 これを行うと、何が起こるかがわかります。 一部の暗号アルゴリズムはカボチャになります。 2つの256ビット数を乗算するネストの複雑さは、約500K、512ビット-2M、1024-8Mなどです。 はい、数字の乗算は同じネスト構造になりますが、より複雑になります。
この段階で、私はリップシール機を軽くたたきました。 いくつかのアイデアを試してみましたが、...まったく役に立ちませんでした。 これまでのところ、何らかの形で偽のメンバーを識別することができる兆候は見つかっていません。 たぶん私は少し試しました。 そして、推定、それはすでに近くのどこかにあったが、私はそれを見つけなかった、それに到達しなかった、それはwould辱になるだろう...しかし、おそらく、それは半分に行くことが私のカルマです。 そのようなもの。
PS
それがすべてであり、何がポイントであるかについての短い後書き。 正直に言って、上記のすべてが科学的な意味を持っているのか、実際的な利点を持っているのか、他の何かを持っているのかはわかりません。 私は事実上の古典的な教育を受けていません、そして、私はすべて、私の考慮事項、流入、および態度によって導かれます。
マザイ・バンザエフ。