特別に細工されたCPUを使用して多数の素因数を見つける
https://stackoverflow.com/questions/1206277
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
最近の多くの公開鍵暗号化アルゴリズムは、鍵を構成するために大きな素数に依存していることであり、2つの素数の積を因数分解することが暗号化を困難にしていることです。また、このような大きな数値を因数分解するのが難しい理由の1つは、使用する数値のサイズが大きいため、CPUが効率的に数値を操作できないことです。これは、32ビットと64ビットのごくわずかなCPUが一致しないためです1024、2048、さらには4096ビット数の場合。これらの数値を処理するには、特殊なBig Integer数学ライブラリを使用する必要があり、CPUは一度に小さなチャンク（32ビットや64ビットなど）のみを保持（および処理）できるため、これらのライブラリは本質的に低速です。
そう...
8ビットから16ビット、32ビットから64ビットCPUにスケーリングしたのと同じように、2048ビットのレジスターと巨大な算術回路を備えた高度に特化したカスタムチップを構築できないのは、LOTを大きくするだけです？このチップは、仮想メモリ、マルチスレッド、I / Oなどを処理する必要がないため、従来のCPUのほとんどの回路を必要としません。格納された命令をサポートする汎用プロセッサである必要さえありません。膨大な数で必要な算術計算を実行するための最低限のことです。
ICの設計についてはあまり知りませんが、論理ゲートの仕組み、半加算器、全加算器の構築方法、そして多数の加算器をリンクしてマルチビット演算を行う方法について学習したことを覚えています。スケールアップするだけです。たくさん。
今、私は上記がうまくいかないという非常に正当な理由（または17）があることをかなり確信しています（そうでなければ、私よりも賢い多くの人々のうちの1人がすでにそれをしているでしょうから）なぜ機能しないのかなぜ知っている。
（注：質問が意味をなすかどうかはまだわからないので、この質問には再作業が必要になる場合があります）
解決
@cubeが言ったことと、巨大な算術論理演算装置が論理信号が安定するまでに時間がかかり、デジタル設計に他の複雑な要素が含まれるという事実。デジタルロジックデザインには、ソフトウェアで当たり前のこと、つまり組み合わせロジックを介した信号が伝播し、安定するまでにゼロではない小さな時間を要するものが含まれます。 32x32乗算器は慎重に設計する必要があります。 1024x1024乗算器は、チップ内の膨大な物理リソースを消費するだけでなく、32x32乗算器よりも遅くなります（おそらく、1024x1024乗算を実行するために必要なすべての部分積を計算する32x32乗算器よりも高速です）。さらに、ボトルネックとなるのは乗数だけではありません。メモリパスウェイがあります。わずか32ビット幅のメモリ回路から1024ビットを収集し、その結果得られた2048ビットをメモリ回路に保存するのに多くの時間を費やす必要があります。
ほぼ確実に、「従来型」の束を取得する方が良いでしょう。並行して動作する32ビットまたは64ビットシステム：ハードウェア設計の複雑さなしに高速化を実現します。
編集： ACMアクセスを持っている人（持っていない場合）は、おそらくこのペーパーでその内容を確認してください。
他のヒント
この高速化はO（n）のみで行われるためですが、数値の因数分解の複雑さはO（2 ^ n）のようなものです（ビット数に関して）。したがって、この＆＃252; berprocessorを作成し、数値を1000倍高速化した場合、数値を10ビット大きくするだけで、再び最初からやり直すことができます。
上で示したように、主な問題は単純に、数を因数分解するためにいくつの可能性を経なければならないかです。そうは言っても、この種のことを行う専用のコンピューターは存在します。
この種の暗号化の真の進歩は、数値ファクタリングアルゴリズムの改善です。現在、最も速い既知の一般的なアルゴリズムは、一般的な数値フィールドのふるいです。
歴史的には、10年ごとに2倍の数を因数分解できるようです。その一部はより高速なハードウェアであり、その一部は単に数学とファクタリングの実行方法をよりよく理解することです。
あなたが説明したアプローチとまったく同じアプローチの実現可能性についてコメントすることはできませんが、人々はFPGAを使用して非常に頻繁に類似することをしています：
シャミール＆amp; Tromer は、グリッドコンピューティングを使用して、同様のアプローチを提案します。
この記事では、カスタムハードウェアの新しい設計について説明します ふるい分けステップの実装 [TWINKLEと比較したふるい分けのコスト]を約1,000万ドルに削減します。新しいデバイス、 TWIRLと呼ばれ、の拡張として見ることができます TWINKLEデバイス。ただし、TWINKLEとは異なり 光電子部品がなく、できます したがって、標準のVLSI技術を使用して製造される シリコンウェーハ上。基本的な考え方は、使用することです 多くのサブ問題を解決するための入力の単一コピー 並行して。入力ストレージがコストを支配するため、 並列化のオーバーヘッドは低く抑えられ、結果として スピードアップは基本的に無料で得られます。確かに、 主な課題は、入力のコンパクトなストレージを可能にしつつ、この並列処理を効率的に達成することです。 これに対処するには、無数の考慮事項が必要です。 数論からVLSI技術まで。
超量子コンピュータを構築して、 Shorのアルゴリズムを実行してみませんかその上で？
＆quot; ...十分な数のキュービットを持つ量子コンピューターを構築する場合、 Shorのアルゴリズムを使用して、広く使用されているRSAスキームなどの公開鍵暗号化スキームを破ることができます。 RSAは、大きな数を因数分解することは計算上実行不可能であるという仮定に基づいています。知られている限り、この仮定は古典的な（非量子）コンピューターに有効です。多項式時間を考慮することができる古典的なアルゴリズムは知られていません。ただし、Shorのアルゴリズムは、量子コンピューターでは因数分解が効率的であることを示しているため、十分に大きい量子コンピューターはRSAを破ることができます。 ...＆quot; -Wikipedia
