0

負けを認めることにした。これが私のコードです。前処理なしで単一チャンク 512 ビット入力の SHA-2 アルゴリズムの実行のツリーを構築する必要があります。ただし、ツリーのトラバースが 64 回の反復で終了しなかったため、64 回の反復から 4 回の反復に減らしました。4回の反復でも、10,000個のノードをトラバースします-1000個しか割り当てられていない場合でも、葉であり、トラバーサルカウントにカウントされない定数の束を含みます。さらに、アサーションは非周期的であることを保証し、周期的である場合、それは決して返されず、永遠に戻ってから返されません。

このような小さな非循環ツリーをトラバースするのに永遠にかかるようにするために、このコードで一体何をしたのでしょうか?

4

1 に答える 1

2

まあ、それは予想されることです。ツリーは非常にコンパクトな方法で格納できますが、繰り返し部分が非常に多くあります。とてつもなく大きいです。

例として、次のシーケンスを検討してください。

auto s0 = la.rotate(2) ^ la.rotate(13) ^ la.rotate(22);

これで、s0ツリーの下に 3 つの元のla式が表示されます。

auto t2 = s0 + maj;

...そしてその木が入りt2ます...

la = t1 + t2;

...laループの最後で再び終了します。そのため、以前の反復のツリーlaへの参照が (少なくとも) 3 つになりました。la次の反復では、これが再び 3 倍になります。そして何度も。laこれから、最終的なツリーで元の 3^64 インスタンスの下限を導き出すことができます(ストレージに存在するのは 1 つだけですが)。3^64 は 3.43368382 × 10^30、つまり約 3 兆です。

ツリーの生成は簡単なルートをたどり、サブツリーを再利用するだけです。一方、トラバーサル関数は、同じサブツリーを何度もトラバースすることになります。

于 2012-05-17T10:17:14.630 に答える