質問: 素数は自前で? RSA暗号の暗号化・復号化・解読をSwiftでプログラミングしています。32bit(2^16未満の素数を利用)までは作れましたが、64bitに挑戦するとパソコンが固まります。 アルゴ
回答: OpenSSLのRSA鍵生成では、Miller-Rabin素数判定法というのを用いて、ランダムに選んだ巨大な数が素数であるかどうかを確率的に判断しているそうです。 参考:「RSA鍵の生成時に確率的素数判定法を使って問題ないのか」 ミラー–ラビン素数判定法 Miller-Rabin素数判定法は、素数ではないことをチェックするアルゴリズムなので、否定的な結果が得られたからと行って素数であるとは言えないのですが、確率的にはその可能性はだいぶ低いはずなので良しとしているそうです。