『データ構造とアルゴリズム分析:C言語記述』復習——第十章「アルゴリズム設計技術」――質数検査
9817 ワード
2014.07.07 16:46
概要:
比較的小さい正の整数nについて,nが質量数であるか否かを個々に除去する方法で検証することに慣れている.このアルゴリズムの複雑さはO(n^0.5)である.int範囲内の整数(最大2147483647)については,開方後5万未満であり,単回計算についてはほぼ瞬時に完了するため許容できる.しかし、nが10^100のような大きな数であれば、このアルゴリズムの時間は天文数字です.この場合,質量数を判断するための新しいアルゴリズムを開発する必要がある.
説明:
まず、そんな大きな質量数がいったい何の役に立つのかを話しましょう.2つの100ビットの質量pがqに乗算されると、約200ビットの合数sが得られる.もし私があなたにsに2つの素因数pとqがあることを教えなければ、あなたは一生sが素数なのか合数なのか気にしないかもしれません.RSA暗号化アルゴリズムでは,s=pXqは,sが公開されていても一般の人はpとqを出すのが難しい(sが十分長ければ,外部の人が一時的にpとqを分解できないことを確保できる).pとqが得られると,情報を復号することができる.だからpとqは2つの鍵のようなもので、ただそれらがつながっているときの隙間はグランドキャニオンのようなもので、一人の目は全然全貌を見ることができません.
従って,選択した2つの大きな数pとqが質量数であることを確保するために,それらを検出するためにアルゴリズムを設計しなければならない.質量数の英語は「prime number」なので、指数検出は「primality testing」と呼ばれます.
このセクションの重要な知識点である「ランダムアルゴリズム」、すなわちランダム数を含むアルゴリズムです.乱数は後でアルゴリズムに表示されます.
まず,pが質量数であり,整数aとpが互いに質量を持つ場合,a^(p−1)≡1(mod p)というFermaの小さな定理を紹介する.
条件をより厳密に制限すると、pが質量数であれば、0とpの間の整数aはpと相互作用するに違いない.
この定理をよく分析すると、次の2つの点に注意する必要があります.
1. pが素数でなく,aとpが互いに質を持たない場合,上記の式も満たす可能性がある(この定理は十分で不要である)
2. aとpが互いに質的であるが,上記の式が満たされない場合,pは必ず質数ではない(逆否命題は元の命題と等価である)
第1条は深く考える価値があり、第2条は基本的な論理法則である.
341341=11*31を考慮すると、341はすべて合数です.2^340≡1(mod 341)は、上記の式に合致する.3^340≡56(mod 341)は、上記の式に合致しない.
これは素数の合数と誤認される可能性があり、Carmichael Numberと呼ばれ、中国語では偽素数と呼ばれてもよい.
従って、異なるa値を選択すると、異なる結論が得られる可能性があることがわかる.したがって、選択したaの残数が1である場合、pを表すのは質量数である可能性が高い.残数が1でない場合、pは質量数ではないに違いない.
従って、この検出アルゴリズムは、異なる(a,p)組合せに対して一定の誤り率を有し、ある固定された(a,p)組合せに対して、結果は決定される.エラー率を下げるにはどうすればいいですか?ランダムにa値を選択し、複数回テストすればよい.
何度もランダムに測定したい場合は、エラー率を自分の望む範囲に抑えることができます.
これでアルゴリズムの正確性と実行可能性には根拠がある.では、効率はどのようにして大数計算に耐えられるのでしょうか.
この式:a^(p−1)≡1(mod p)を観察してください.ここで用いられる型取り演算は,べき乗演算が大数規模の実現に比較的基礎的である.また、べき乗演算は、高速べき乗の考え方によって対数レベルを達成することができる.
例えばpが100ビット数である場合、log(p)の大まかな範囲はO(100)の時間しかかかりません.これにより、時間のオーバーヘッドは天文数字から普通のコンピュータでも許容できるレベルに下がった.
高速べき乗の強力な威力は、連続的な乗算(必ずしも乗算ではない場合がある)をべき乗演算に変換し、O(log(n))の高速べき乗アルゴリズムを用いて、O(n)時間を必要とする線形問題を解決する例が少なくない.
このアルゴリズムは,また高速べき乗に一例を加えた.
以下の実装は大数の各種操作を書かなかったが,実装編幅が多くなる可能性があるからである.
実装:
概要:
比較的小さい正の整数nについて,nが質量数であるか否かを個々に除去する方法で検証することに慣れている.このアルゴリズムの複雑さはO(n^0.5)である.int範囲内の整数(最大2147483647)については,開方後5万未満であり,単回計算についてはほぼ瞬時に完了するため許容できる.しかし、nが10^100のような大きな数であれば、このアルゴリズムの時間は天文数字です.この場合,質量数を判断するための新しいアルゴリズムを開発する必要がある.
説明:
まず、そんな大きな質量数がいったい何の役に立つのかを話しましょう.2つの100ビットの質量pがqに乗算されると、約200ビットの合数sが得られる.もし私があなたにsに2つの素因数pとqがあることを教えなければ、あなたは一生sが素数なのか合数なのか気にしないかもしれません.RSA暗号化アルゴリズムでは,s=pXqは,sが公開されていても一般の人はpとqを出すのが難しい(sが十分長ければ,外部の人が一時的にpとqを分解できないことを確保できる).pとqが得られると,情報を復号することができる.だからpとqは2つの鍵のようなもので、ただそれらがつながっているときの隙間はグランドキャニオンのようなもので、一人の目は全然全貌を見ることができません.
従って,選択した2つの大きな数pとqが質量数であることを確保するために,それらを検出するためにアルゴリズムを設計しなければならない.質量数の英語は「prime number」なので、指数検出は「primality testing」と呼ばれます.
このセクションの重要な知識点である「ランダムアルゴリズム」、すなわちランダム数を含むアルゴリズムです.乱数は後でアルゴリズムに表示されます.
まず,pが質量数であり,整数aとpが互いに質量を持つ場合,a^(p−1)≡1(mod p)というFermaの小さな定理を紹介する.
条件をより厳密に制限すると、pが質量数であれば、0とpの間の整数aはpと相互作用するに違いない.
この定理をよく分析すると、次の2つの点に注意する必要があります.
1. pが素数でなく,aとpが互いに質を持たない場合,上記の式も満たす可能性がある(この定理は十分で不要である)
2. aとpが互いに質的であるが,上記の式が満たされない場合,pは必ず質数ではない(逆否命題は元の命題と等価である)
第1条は深く考える価値があり、第2条は基本的な論理法則である.
341341=11*31を考慮すると、341はすべて合数です.2^340≡1(mod 341)は、上記の式に合致する.3^340≡56(mod 341)は、上記の式に合致しない.
これは素数の合数と誤認される可能性があり、Carmichael Numberと呼ばれ、中国語では偽素数と呼ばれてもよい.
従って、異なるa値を選択すると、異なる結論が得られる可能性があることがわかる.したがって、選択したaの残数が1である場合、pを表すのは質量数である可能性が高い.残数が1でない場合、pは質量数ではないに違いない.
従って、この検出アルゴリズムは、異なる(a,p)組合せに対して一定の誤り率を有し、ある固定された(a,p)組合せに対して、結果は決定される.エラー率を下げるにはどうすればいいですか?ランダムにa値を選択し、複数回テストすればよい.
何度もランダムに測定したい場合は、エラー率を自分の望む範囲に抑えることができます.
これでアルゴリズムの正確性と実行可能性には根拠がある.では、効率はどのようにして大数計算に耐えられるのでしょうか.
この式:a^(p−1)≡1(mod p)を観察してください.ここで用いられる型取り演算は,べき乗演算が大数規模の実現に比較的基礎的である.また、べき乗演算は、高速べき乗の考え方によって対数レベルを達成することができる.
例えばpが100ビット数である場合、log(p)の大まかな範囲はO(100)の時間しかかかりません.これにより、時間のオーバーヘッドは天文数字から普通のコンピュータでも許容できるレベルに下がった.
高速べき乗の強力な威力は、連続的な乗算(必ずしも乗算ではない場合がある)をべき乗演算に変換し、O(log(n))の高速べき乗アルゴリズムを用いて、O(n)時間を必要とする線形問題を解決する例が少なくない.
このアルゴリズムは,また高速べき乗に一例を加えた.
以下の実装は大数の各種操作を書かなかったが,実装編幅が多くなる可能性があるからである.
実装:
1 // Primality testing using Fermat's Lesser Theorem.
2 #include <cstdlib>
3 #include <ctime>
4 #include <iostream>
5 using namespace std;
6
7 int primalityTest(int a, int i, int n)
8 {
9 // a is randomly chosen between (1, n) to test the primality of n.
10 int x, y;
11
12 if (i == 0) {
13 return 1;
14 }
15
16 x = primalityTest(a, i / 2, n);
17 if (x == 0) {
18 // x == 0 means n is composite.
19 // recursively return false
20 return 0;
21 }
22
23 y = (x * x) % n;
24 if (i % 2 != 0) {
25 y = (y * a) % n;
26 }
27
28 return y;
29 }
30
31 bool isPrime(const int n)
32 {
33 if (n < 2) {
34 return false;
35 } else if (n < 4) {
36 return true;
37 }
38
39 const int NUM_OF_TRIALS = 10;
40 int i = 0;
41 while (i < NUM_OF_TRIALS) {
42 if (primalityTest(2 + rand() % (n - 3), n - 1, n) != 1) {
43 return false;
44 }
45 ++i;
46 }
47
48 return true;
49 }
50
51 int main()
52 {
53 srand((unsigned int)time(nullptr));
54 int n;
55
56 while (cin>> n && n > 0) {
57 cout << (isPrime(n) ? "Yes": "No") << endl;
58 }
59
60 return 0;
61 }