問題タブ [bignum]

私の理解では、最近の多くの公開鍵暗号化アルゴリズムは、鍵を構成するために大きな素数に依存しており、2つの素数の積を因数分解するのが難しいため、暗号化が破られにくくなっています。また、このような大きな数値を因数分解することが非常に難しい理由の1つは、使用される数値のサイズが非常に大きいため、32ビットと64ビットの非常に小さいCPUが一致しないため、CPUが数値を効率的に操作できないことを意味することも理解しています。 1024、2048、さらには4096ビット数の場合。これらの数値を処理するには、特殊なBig Integer数学ライブラリを使用する必要があります。また、CPUは一度に小さなチャンク（32ビットや64ビットなど）しか保持（および処理）できないため、これらのライブラリは本質的に低速です。

それで...

8ビットから16ビット、32ビットから64ビットのCPUにスケーリングしたのと同じように、2048ビットレジスタと巨大な算術回路を備えた高度に特殊化されたカスタムチップを構築できないのはなぜですか。このチップは、従来のCPUのほとんどの回路を必要とせず、結局のところ、仮想メモリ、マルチスレッド、I/Oなどを処理する必要はありません。保存された命令をサポートする汎用プロセッサである必要はありません。膨大な数に対して必要な算術計算を実行するための最低限のことです。

ICの設計についてはよくわかりませんが、論理ゲートのしくみ、半加算器、全加算器の作成方法、および多数の加算器をリンクしてマルチビット演算を行う方法について学んだことを覚えています。スケールアップするだけです。多くの。

さて、上記が機能しないという非常に正当な理由（または17）があることはかなり確信しています（そうでなければ、私よりも賢い多くの人々の1人がすでにそれを行っているため）が、その理由を知りたいと思っていますそれは動作しません。

（注：質問が理にかなっているかどうかはまだわかりませんので、この質問にはいくつかのやり直しが必要な場合があります）

私はCを学ぼうとしていますが、本当に大きな数（つまり、100桁、1000桁など）を処理できないことに気づきました。これを行うためのライブラリが存在することは承知していますが、自分で実装してみたいと思います。

誰かが任意精度の算術の非常に詳細でばかげた説明を持っているか、提供できるかどうかを知りたいだけです。

これは、数週間前の私自身の質問とほぼ同じです。

データ型が完全な数値を保持できない場合は、16進数を10進数に変換します

今回はその逆です。私は（便利なヌル文字で終了した文字列の）番号を持っており、この番号を構成するバイトが必要です。ただし、私はマイクロコントローラーの32ビットアーキテクチャで作業しているため、32ビットを超える数であるため、atoiを使用する可能性はありません。

元の結果を取り戻すために、最初のリンクで提供されているアルゴリズムを逆にする方法について誰かが考えていますか？私の合同算術スキルは私を失敗させています。

簡単な例：155.207.231.135から0x [24] [23] [12] [66] [9F]（角かっこでバイトを区切ります）

約 20 分前に入門 C コースの試験を終えたところです。試験の最初の質問は、私をやや不意を突かれたもので、2 つの大きな数の違いを見つけるというものでした。

目標は、2 つの構造体 (N1 と N2) を値で取得し、その違いを参照渡しの構造体 (N3) に格納することでした。N3 はすべて「0」で開始されたと想定できます。MAX サイズは何でもかまいませんので、数値が 100 桁を超える場合でもソリューションは機能する必要があります。

ベースコードは次のとおりです（元は少し異なる場合があります。これはメモリからのものです）

問題は、この問題の解決策を見つけることではありませんが、完全な回答に対して約 20 行しか提供されていません。私の解決方法は、整数に変換した後に数字を 1 つずつ減算し、結果が負の場合は適切なキャリーを作成することでした。これは、提供されたものよりもかなり多くのスペースを必要としました。

この質問に与えられたわずかなマークとスペースに基づいて、私が見ていないかなり些細な解決策があると信じるに至りました。それは何ですか？私はコースを終了しましたが、この質問はまだ私を悩ませています!

完全なソリューションは必要ありません。関数の内部の仕組みだけですdifference。

念のため、ビット単位の演算子は使用しないでください。

emacs は整数に収まらない大きな数をサポートしていますか? もしそうなら、どうやってそれらを使うのですか？

符号なし 128 ビット整数をリトルエンディアン順で表す 4 つの符号なし 32 ビット整数があります。

この数値を 10 進文字列表現に変換し、ファイルに出力したいと思います。

現在、bigint_divmod10関数を使用して数値を 10 で除算し、剰余を追跡しています。この関数を繰り返し呼び出して、数値がゼロになるまで余りを数字として出力します。かなり遅いです。これが最速の方法ですか？もしそうなら、私が見ていないこの機能を実装する賢い方法はありますか? GMP を調べてみましget_str.cたが、かなり難解です。

編集: divmod10 関数について思いついた最速のコードは次のとおりです。

add 関数は次のように定義されます。

私は独自の小さな多精度ライブラリを作成しています。減算のメソッドを作成しているときに、奇妙なエラーが発生しました。これは、多精度減算のために私が書いたコード ブロックです。

p_aReverseIter->m_Value は 32 ビットの unsigned int ですが、a、b は BigInt です。値は、ビッグ エンディアン スタイルでベクター内に格納されます。temp は __int64 で、キャリーは 32 ビットの unsigned long として機能する必要があります。

a から b を減算するとします。a > b (符号なし減算) ですが、b のすべての 32 ビット ワードは a よりも大きくなります。このルーチンは、次の出力を生成します。

ただし、キャリーは常に 0xffffffff でなければなりません。ゼロになるたびに、結果は間違っている '13131314' になります。次に、キャリーを unsigned long から unsigned __int64 に変更し、

に

キャリーは常に正しく計算され、0xffffffff に設定されるようになりました。しかし、2^32 の 64 ビット値を右シフトすると、常に 32 ビットの結果が生成されます。

私の質問は、さまざまな結果を理解するために、何が欠けているのでしょうか?

どうもありがとうございました。

私はアルゴリズムにPythonのネイティブbignumを使用しており、C++に変換して高速化することにしました。ロングロングを使用した場合、C ++はPythonよりも約100倍高速でしたが、C ++でGMPバインディングを使用した場合、Pythonよりもわずか10倍高速でした（ロングロングに適合する同じケースの場合）。

多数の小さな追加を行うためのより良いbignum実装はありますか？たとえば、大きな数Nがあり、小さな+ 1、+ 21、+ 1などをたくさん追加し、ときどき別の大きな数Mを追加しますか？

私はいくつかのプロジェクトオイラーの問題を行っていますが、ほとんどの場合、計算には int、float、double などを超える大きな数値が含まれます。

まず、多数の問題を回避するために、より効率的な計算方法を探す必要があることを知っています。Bignum ライブラリについて聞いたことがあります。

しかし、学者の興味のために、この問題に対する独自のソリューションをコーディングする方法を知りたいです。

専門家が私を助けてくれますか？(私の言語は C です)

F# Interactive を使用しており、FSharp.PowerPack.dll の参照を追加しました。

次のコードのように BigNum を double に変換しようとすると、

というエラーが出ます

「System.MissingMethodException: メソッドが見つかりません: 'Double System.Numerics.BigInteger.ToDouble(System.Numerics.BigInteger)'. at Microsoft.FSharp.Math.BigNum.ToDouble(BigNum n)」

「BigNum から int」や「BigNum から double」などの変換を行いたい場合はどうすればよいですか? どうもありがとう。