素数を判定するいろんな方法は？

質問

素数を判定する方法はエラトステネスのふるいの他に何かあるのでしょうか。１００までは大抵の本に載っていますが、大きな数はふるいにかけても、膨大な手間がかかりそうです。

回答No.3

noname#48504

こんばんは。

フェルマーの小定理の対偶は絶対値の大きな有理整数の素数の判定法として有効らしいですよ。

参考：現代数学の入門「数論入門」（著：山本芳彦、刊：岩波書店）

お礼

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

回答No.2

oyaoya65

以下に代表的な判定法の掲載URLを載せておきます。
これらのどれかが数式処理ソフトに組み込まれていますので私はMathematica/Mapleなどであっという間に判定できます。これも先人のおかげですね。

AKS素数判定法
http://ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95

フェルマーの小定理を使う方法
http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Fermat.html

ミラーラビン法とルーカスレーマー法による素数判定法
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/STUDENT/KENKYU2004/okagaki.pdf
http://www.th.cs.meiji.ac.jp/enc/moriya/prime.html

お礼

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

回答No.1

2531kbps

http://www.google.co.jp/search?client=firefox-a&rls=org.mozilla%3Aja-JP%3Aofficial_s&hl=ja&q=%E7%B4%A0%E6%95%B0%E3%82%92%E5%88%A4%E5%AE%9A&lr=&btnG=Google+%E6%A4%9C%E7%B4%A2
http://www.ipa.go.jp/security/fy14/crypto/prime_num/invest.pdf

素数判定をたやすくできないからこそ、それを利用して暗号化技術があるのではないかな？
とすると、PCが暇なときに1から順に素数判定をしていき、それをテキストファイルにでも格納していく。

判定時はそれを検索すればよい。
もしそのときに、格納していない素数の判定リクエストが来たら、それを計算する。

お礼

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