Archives academic 素数判定プログラム(2)定理についての詳細はフェルマーの小定理 - faireal.net(転載リソース)を参照。ここでは追求しない。 判定したい数をpとして、適当な数nについて上の結果が1なら、その数を素数と判定する。この方法なら、十分大きな領域ではほぼ100％の確率で素数を判別できる。まれに素数でないにも関わらずフェルマーの小定理を満たす擬素数と呼ばれる合成数があるが、巨大自然数ではその確率は無視できる。 フェルマーテストを用いた素数判定プログラム 2005/08/20 このデモは巨大数演算Ver.0.3 alpha9で実装。設定では、一重のフェルマーテストを実行する。前述のように、素数ではないにも関わらずテストをパスする擬素数が存在するため、100％の正確性は保障されない。 桁数が多いと処理に時間がかかるので注意。50桁以下の自然数なら、手元の環境ではそれなりの時間で処理できる。 フェルマーテスト 調査する
