私はGPU上で暗号化アルゴリズムを開発しています。 このアルゴリズムは非常に大きな整数の加算と乗算を必要とします。これらの数字は、推定150,000ビット以上のビット長を持ちます。これらの数字は、異なるビット長を持ちます。これらの数の足し算と掛け算を実行するために使用できるアルゴリズムは何ですか？あなたの情報をください。ありがとうございました。
回答：
回答№1は2大きな整数の加算は比較的簡単です：JackOLanternはすでに投稿へのリンクを提供しました。基本的には、単に並列接頭辞sumを介してキャリー伝播を行うだけです。
CUDAでの大整数乗算では、2つの方法が考えられます。
整数をRNS（残基番号）に変換するSystem）：（RNS基数が十分に大きい限り）乗算と加算は並行して実行できます。数字を比較する必要があるときはいつでも、それらを混合基数システムに変換することができます（例えば、 剰余数系から混合基数系への変換方法）最後に、CRT（Chinese Remaindering）を使用して番号を位置番号システムに戻すことができます。
大整数乗算を直接実装する乗算はシーケンスの非巡回畳み込みと見なすことができるのでFFTを使用します（150Kビットの長さはFFTにはそれほどではありませんが、すでにある程度の高速化が可能です）。それでもGNU MPは1Mbit以上から始まるFFT乗算ルーチンに切り替えます。 FFTを介した乗算の場合も、2つの選択肢があります。
浮動小数点倍精度FFTを使用し、大きな整数ビットを仮数にエンコードする（実装が簡単）
いわゆる数論変換（有限体上のFFT）を使う
とにかく、これらのことの背後にはたくさんの理論があります。あなたも私の論文をチェックすることができます CUDAのFFTマル。しかし、特に暗号分野でこの問題に関する多くの研究論文もあります。