c++ - 大きな数字はどうですか？（素数性テスト）

Question

これは「実際の」タスクであり、任意の言語（C / C ++など）で記述できますか？

だから、私の仕事は50桁を超える長さの乱数を「生成」することです（最大= 200）？

次に、素数性テストでこの数を確認する必要があります。

それで、このタスクは「本物」であり、どれだけの時間/リソースを消費するのでしょうか？

別の方法は、特別なクラスから素数または他の数を生成することです（どのクラスを使用できますか？）

Answer 1

Miller-Rabinのような素数性テストには、通常そのような目的で使用される効率的な確率的アルゴリズムがあります。

乱数を選択し、ランダム化アルゴリズムを使用して素数性をテストすると効率的です。素数の密度により、nビット数の場合はn個の数を選択してテストする必要があることが保証されるためです。

Answer 2

Miller-Rabin素数性検定を使用します。また、50桁の数値はネイティブのデータ型に適合しないため、小数点以下の桁数のライブラリが必要になります。

これはミラーラビンのJavascript実装であり、ミラーラビンを50回繰り返します。数秒で完了します。