|
|
| 1行目: |
1行目: |
| − | {{出典の明記|date=2018年1月}} | + | {{テンプレート:20180815sk}} |
| − | '''素数判定'''（そすうはんてい）とは、ある自然数 ''n'' が[[素数]]であるか[[合成数]]であるかを判定する問題である。素数判定を行う[[アルゴリズム]]のことを'''素数判定法'''という。
| |
| − | | |
| − | [[RSA暗号]]の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは[[計算理論]]において強い関心の対象である。
| |
| − | | |
| − | 仮定なしで決定的かつ多項式時間で終了する素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された（[[AKS素数判定法]]）。しかし多項式の次数が高く、実用上は{{ill2|APR判定法|en|Adleman–Pomerance–Rumely primality test}}などのほうが高速であることが多い。
| |
| − | | |
| − | なお、[[メルセンヌ数]]など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。
| |
| − | | |
| − | == 確率的素数判定法 ==
| |
| − | 素数判定法の中には[[乱択アルゴリズム|確率的アルゴリズム]]に基づいた、与えられた自然数 ''n'' を「合成数である」または「良く分からない」と判別する判定法がある。この判定法を'''確率的素数判定法''' (probabilistic primality test) ということがある。これに対して「素数である」あるいは否と判定する[[決定的アルゴリズム]]は決定的素数判定法 (deterministic primality test) ということがある。
| |
| − | | |
| − | 「合成数である」と判定した場合には、''n''は合成数であると確定するが、「良く分からない」と判断した場合には、それだけではあまり有用な情報は得られない。しかし、判定を適当な回数だけ繰り返し、その間一度も「合成数である」と出力されないならば、その ''n'' は素数である見込みが大きいと言える。このようにして得られた「素数ではないかと思われる数」のことを'''確率的素数''' (probable prime) という。
| |
| − | | |
| − | 一般に確率的素数判定法は、決定的素数判定法よりもはるかに高速であるので、実用上は確率的素数判定法の繰り返しをもって素数判定法に代える場合も多い。
| |
| − | | |
| − | また、[[ミラー-ラビン素数判定法|Miller-Rabinの素数判定法]]はある種の一般化された[[リーマン予想]]のもとでは多項式時間で動く素数判定法として動作することが知られている。
| |
| − | | |
| − | == 様々な判定法 ==
| |
| − | * 一般的な数に対する判定法
| |
| − | ** 決定的素数判定法
| |
| − | *** 試し割り、[[エラトステネスの篩]]
| |
| − | *** [[最大公約数]]
| |
| − | *** [[ウィルソンの定理]]
| |
| − | *** [[ミラー-ラビン素数判定法#決定的アルゴリズム|Millerテスト]] - 多項式時間アルゴリズムだが、GRHのもとで正当性が示される。
| |
| − | *** {{ill2|Adleman–Pomerance–Rumely primality test|en|Adleman–Pomerance–Rumely primality test}} - 高速だが、多項式時間アルゴリズムではない。
| |
| − | *** ECPP
| |
| − | *** [[AKS素数判定法]] - 多項式時間アルゴリズム
| |
| − | ** 確率的素数判定法
| |
| − | *** [[フェルマーの小定理#フェルマーテスト|フェルマーテスト]]
| |
| − | *** Solovay-Strassenテスト
| |
| − | *** [[ミラー–ラビン素数判定法]]
| |
| − | * 特殊な条件の数に対する判定法
| |
| − | ** {{ill2|Pocklingtonの判定法|en|Pocklington_primality_test}} - N = FR+1, F> sqrt(N), Fの素因数分解が既知の場合の判定法
| |
| − | ** [[メルセンヌ数#リュカ・テスト|リュカ・テスト]] - {{mvar|p}}が{{math|(4''j'' + 3)}}型素数の[[メルセンヌ数]]に対する判定法
| |
| − | ** [[メルセンヌ数#リュカ–レーマー・テスト|リュカ–レーマー・テスト]] - {{mvar|p}} が奇素数の[[メルセンヌ数]]に対する判定法
| |
| − | ** {{ill2|リュカ–レーマー–リーゼル・テスト|en|Lucas–Lehmer–Riesel_test}}
| |
| − | * 特殊な形の数に対する判定法
| |
| − | ** {{ill2|Prothの判定法|en|Proth%27s_theorem}} - [[プロス数]]に対する判定法
| |
| − | ** {{ill2|Pépinの判定法|en|Pépin%27s_test}} - [[フェルマー数]]に対する判定法
| |
| − | | |
| − | == プログラム例==
| |
| − | [[C言語]]による素数判定（試し割り）のプログラム例を示す。
| |
| − | <source lang="c">
| |
| − | int IsPrime (int n)
| |
| − | {
| |
| − | int i;
| |
| − | | |
| − | if (n < 2)
| |
| − | return 0;
| |
| − | else if (n == 2)
| |
| − | return 1;
| |
| − | | |
| − | if (n % 2 == 0)
| |
| − | return 0;
| |
| − | | |
| − | for (i = 3; i <= n / i; i += 2)
| |
| − | if (n % i == 0)
| |
| − | return 0;
| |
| − | return 1;
| |
| − | }
| |
| − | </source>
| |
| − | 入力nが素数である場合1が返り、それ以外の場合0が返る。
| |
| − | | |
| − | [[Common Lisp]]による素数判定([[エラトステネスの篩]])のプログラム例を示す。
| |
| − | <source lang="lisp">
| |
| − | (defun eratosthenes (n)
| |
| − | (labels ((foo (i ls)
| |
| − | (if (= i 1)
| |
| − | ls
| |
| − | (foo (1- i) (cons i ls))))
| |
| − | (spam (ls0 ls1)
| |
| − | (if (> (expt (car ls1) 2) (car (last ls0)))
| |
| − | (revappend ls1 ls0)
| |
| − | (let ((ls2
| |
| − | (remove-if #'(lambda (x)
| |
| − | (zerop (mod x (car ls1))))
| |
| − | ls0)))
| |
| − | (spam (cdr ls2) (cons (car ls2) ls1))))))
| |
| − | (let ((lst (foo n nil)))
| |
| − | (spam (cdr lst) (list (car lst))))))
| |
| − | </source>
| |
| − | 入力nまでの素数のリストを返す。
| |
| − | | |
| − | [[Scheme]]による素数判定([[エラトステネスの篩]])のプログラム例を示す。
| |
| − | <source lang="scheme">
| |
| − | (require (lib "1.ss" "srfi"))
| |
| − | ;;;上は[[MzScheme]]の[[SRFI]]の呼び出し例。
| |
| − | ;;;例えば[[Gauche]]の場合は
| |
| − | ;;;(use srfi-1)
| |
| − | ;;;となる
| |
| − | | |
| − | (define (eratosthenes n)
| |
| − | (let ((ls (iota (- n 2) 3)))
| |
| − | (letrec ((func0 (lambda (x lst)
| |
| − | (filter (lambda (y)
| |
| − | (not (zero? (modulo y x))))
| |
| − | lst)))
| |
| − | (func1 (lambda (z)
| |
| − | (apply max z))))
| |
| − | (let loop ((ls0 '(2)) (ls1 (func0 2 ls)))
| |
| − | (if (< (func1 ls1) (expt (func1 ls0) 2))
| |
| − | (append (reverse ls0) ls1)
| |
| − | (let ((w (car ls1)))
| |
| − | (loop (cons w ls0) (func0 w (cdr ls1)))))))))
| |
| − | </source>
| |
| − | 入力nまでの素数のリストを返す。
| |
| − | | |
| − | [[category:数論アルゴリズム|そすうはんてい]]
| |
| − | [[Category:数学に関する記事|そすうはんてい]]
| |
| − | [[Category:素数|そすうはんてい]]
| |