ネストされたブール式

こんにちは この記事では、どのように混乱するかを説明します。 少数の思考が何年もあなたの頭を捕らえ、さらにあなたの人生に影響を与えることができる方法 数値を加算および乗算する方法、md5を計算する方法、およびオイラー仮説から数値を探す方法を説明します。

すべての操作を論理ビットで実行しますが、計算はしません。 論理的な変数のみで動作し、計算の複雑さから震え、無限の期待を予想します。 この世界では、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）$インライン$
...

ここで、数字を追加する方法を学びました。


はい、この数字にはもう1つあります。数字の合計が1つの新しいビットを与えることができます。


用語とは、式が選言標準形に縮小された後の用語を意味します（同じ用語を思いついた）、言い換えると、形式に縮小した後、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ビット数の積は次のとおりです。



しかし、これは、面倒な複数階の式を乗算から単純化するためのオプションの1つにすぎません。 上位ビットの他の値を取得する場合がありますが、それは論理式をどれだけ単純化できるかに依存します。

したがって、加算と乗算を行うことができます。 特別な計算コストなしで再帰式を取得できます。これにより、合計、積、または数値に関するその他の複合演算が考慮されます。 しかし、判明したように、許容できる時間内に10ビットを超える数値の場合、この式を単純化することはできません。 8x8ピースの表現を単純化することはほとんどできませんでした。

この段階で、私は最初のトラブルに遭遇しました。 小さな注文の単純化された作品を見て、ある種の依存関係を見つけ、そのような公式を構築することを学ぶことは可能ですか？

加算と乗算の結果として、aとbに関して対称性がなければなりません。下位ビットでは肉眼で見ることができ、上位ビットで見るためには目を武装しなければなりません。

だから、最下位ビットを見ることで加算/乗算の最上位ビットの式を構築することは可能ですか？ 私は成功しませんでした

しかし、コインには裏返しがあります。単純化された式は間違いなく多くのスペースを占有するため、2つの1024ビット数の積を単純化するのは意味がありません。 しかし、誰もが1024ビット（特に素数）の数値を乗算することに興味がありますよね？ ネストされた論理式を操作することを学ぶ必要があります。

互いに埋め込まれたものを含む選言的標準形に縮小された論理式で動作する小さなコードを書くことは難しくありませんでした。 まあ、私は飲酒をやめ、プログラミングを学び、仕事をやめる必要がありました。

第3章、最も興味深い

md5を例にとります。 64同じラウンドについて退屈。 計算では、通常の論理演算子と上記の合計のみが使用されます。 32より古いビットのみが破棄されます。 さて、ネストされたビット式を使用してmd5を計算できます。

大体このように見えます。

たとえば、入力md5は128個の論理変数です。 ネストされた変数をtと呼び、メイン変数の後に番号を付け始めます。 この場合、メイン変数（md5関数の入力に供給される変数）は、$$ $インライン$ x0 $インライン$ 前に$$ $インライン$ x127 $インライン$ 、ネストされたものは$$ $インライン$ t128 $インライン$ 。 次に、結果の最初のビットはこのようなものになります（すべてアルゴリズムのどのポイントで式をt変数に折り畳むかによって異なります）。


ここで、各t変数は異なる式です。


ご存じのとおり、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

それがすべてであり、何がポイントであるかについての短い後書き。 正直に言って、上記のすべてが科学的な意味を持っているのか、実際的な利点を持っているのか、他の何かを持っているのかはわかりません。 私は事実上の古典的な教育を受けていません、そして、私はすべて、私の考慮​​事項、流入、および態度によって導かれます。

マザイ・バンザエフ。