📄 nbtheory_8cpp-source.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"><title>Crypto++: nbtheory.cpp Source File</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.3.2 --><div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="hierarchy.html">Class Hierarchy</a> | <a class="qindex" href="classes.html">Alphabetical List</a> | <a class="qindex" href="annotated.html">Compound List</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="namespacemembers.html">Namespace Members</a> | <a class="qindex" href="functions.html">Compound Members</a> | <a class="qindex" href="globals.html">File Members</a></div><h1>nbtheory.cpp</h1><div class="fragment"><pre>00001 <span class="comment">// nbtheory.cpp - written and placed in the public domain by Wei Dai</span>00002 00003 <span class="preprocessor">#include "pch.h"</span>00004 00005 <span class="preprocessor">#ifndef CRYPTOPP_IMPORTS</span>00006 <span class="preprocessor"></span>00007 <span class="preprocessor">#include "nbtheory.h"</span>00008 <span class="preprocessor">#include "modarith.h"</span>00009 <span class="preprocessor">#include "algparam.h"</span>00010 00011 <span class="preprocessor">#include <math.h></span>00012 <span class="preprocessor">#include <vector></span>00013 00014 NAMESPACE_BEGIN(CryptoPP)00015 00016 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> maxPrimeTableSize = 3511; <span class="comment">// last prime 32719</span>00017 <span class="keyword">const</span> word lastSmallPrime = 32719;00018 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> primeTableSize=552;00019 00020 word primeTable[maxPrimeTableSize] =00021 {2, 3, 5, 7, 11, 13, 17, 19,00022 23, 29, 31, 37, 41, 43, 47, 53,00023 59, 61, 67, 71, 73, 79, 83, 89,00024 97, 101, 103, 107, 109, 113, 127, 131,00025 137, 139, 149, 151, 157, 163, 167, 173,00026 179, 181, 191, 193, 197, 199, 211, 223,00027 227, 229, 233, 239, 241, 251, 257, 263,00028 269, 271, 277, 281, 283, 293, 307, 311,00029 313, 317, 331, 337, 347, 349, 353, 359,00030 367, 373, 379, 383, 389, 397, 401, 409,00031 419, 421, 431, 433, 439, 443, 449, 457,00032 461, 463, 467, 479, 487, 491, 499, 503,00033 509, 521, 523, 541, 547, 557, 563, 569,00034 571, 577, 587, 593, 599, 601, 607, 613,00035 617, 619, 631, 641, 643, 647, 653, 659,00036 661, 673, 677, 683, 691, 701, 709, 719,00037 727, 733, 739, 743, 751, 757, 761, 769,00038 773, 787, 797, 809, 811, 821, 823, 827,00039 829, 839, 853, 857, 859, 863, 877, 881,00040 883, 887, 907, 911, 919, 929, 937, 941,00041 947, 953, 967, 971, 977, 983, 991, 997,00042 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,00043 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,00044 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,00045 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,00046 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,00047 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,00048 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,00049 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459,00050 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,00051 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571,00052 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619,00053 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,00054 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747,00055 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,00056 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,00057 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949,00058 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003,00059 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069,00060 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,00061 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203,00062 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,00063 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311,00064 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,00065 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,00066 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503,00067 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579,00068 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657,00069 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693,00070 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,00071 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801,00072 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861,00073 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939,00074 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011,00075 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,00076 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167,00077 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221,00078 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301,00079 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347,00080 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,00081 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491,00082 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541,00083 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607,00084 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671,00085 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,00086 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797,00087 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863,00088 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923,00089 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003};00090 00091 <span class="keywordtype">void</span> BuildPrimeTable()00092 {00093 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> p=primeTable[primeTableSize-1];00094 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=primeTableSize; i<maxPrimeTableSize; i++)00095 {00096 <span class="keywordtype">int</span> j;00097 <span class="keywordflow">do</span>00098 {00099 p+=2;00100 <span class="keywordflow">for</span> (j=1; j<54; j++)00101 <span class="keywordflow">if</span> (p%primeTable[j] == 0)00102 <span class="keywordflow">break</span>;00103 } <span class="keywordflow">while</span> (j!=54);00104 primeTable[i] = p;00105 }00106 primeTableSize = maxPrimeTableSize;00107 assert(primeTable[primeTableSize-1] == lastSmallPrime);00108 }00109 00110 <span class="keywordtype">bool</span> IsSmallPrime(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p)00111 {00112 BuildPrimeTable();00113 00114 <span class="keywordflow">if</span> (p.<a class="code" href="class_integer.html#_integerz41_12">IsPositive</a>() && p <= primeTable[primeTableSize-1])00115 <span class="keywordflow">return</span> std::binary_search(primeTable, primeTable+primeTableSize, (word)p.<a class="code" href="class_integer.html#_integerz41_1">ConvertToLong</a>());00116 <span class="keywordflow">else</span>00117 <span class="keywordflow">return</span> <span class="keyword">false</span>;00118 }00119 00120 <span class="keywordtype">bool</span> TrialDivision(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p, <span class="keywordtype">unsigned</span> bound)00121 {00122 assert(primeTable[primeTableSize-1] >= bound);00123 00124 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;00125 <span class="keywordflow">for</span> (i = 0; primeTable[i]<bound; i++)00126 <span class="keywordflow">if</span> ((p % primeTable[i]) == 0)00127 <span class="keywordflow">return</span> <span class="keyword">true</span>;00128 00129 <span class="keywordflow">if</span> (bound == primeTable[i])00130 <span class="keywordflow">return</span> (p % bound == 0);00131 <span class="keywordflow">else</span>00132 <span class="keywordflow">return</span> <span class="keyword">false</span>;00133 }00134 00135 <span class="keywordtype">bool</span> SmallDivisorsTest(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p)00136 {00137 BuildPrimeTable();00138 <span class="keywordflow">return</span> !TrialDivision(p, primeTable[primeTableSize-1]);00139 }00140 00141 <span class="keywordtype">bool</span> IsFermatProbablePrime(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &n, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)00142 {00143 <span class="keywordflow">if</span> (n <= 3)00144 <span class="keywordflow">return</span> n==2 || n==3;00145 00146 assert(n>3 && b>1 && b<n-1);00147 <span class="keywordflow">return</span> a_exp_b_mod_c(b, n-1, n)==1;00148 }00149 00150 <span class="keywordtype">bool</span> IsStrongProbablePrime(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &n, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)00151 {00152 <span class="keywordflow">if</span> (n <= 3)00153 <span class="keywordflow">return</span> n==2 || n==3;00154 00155 assert(n>3 && b>1 && b<n-1);00156 00157 <span class="keywordflow">if</span> ((n.<a class="code" href="class_integer.html#_integerz41_14">IsEven</a>() && n!=2) || GCD(b, n) != 1)00158 <span class="keywordflow">return</span> <span class="keyword">false</span>;00159 00160 <a class="code" href="class_integer.html">Integer</a> nminus1 = (n-1);00161 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> a;00162 00163 <span class="comment">// calculate a = largest power of 2 that divides (n-1)</span>00164 <span class="keywordflow">for</span> (a=0; ; a++)00165 <span class="keywordflow">if</span> (nminus1.<a class="code" href="class_integer.html#_integerz41_5">GetBit</a>(a))00166 <span class="keywordflow">break</span>;00167 <a class="code" href="class_integer.html">Integer</a> m = nminus1>>a;00168 00169 <a class="code" href="class_integer.html">Integer</a> z = a_exp_b_mod_c(b, m, n);00170 <span class="keywordflow">if</span> (z==1 || z==nminus1)00171 <span class="keywordflow">return</span> <span class="keyword">true</span>;00172 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> j=1; j<a; j++)00173 {00174 z = z.Squared()%n;00175 <span class="keywordflow">if</span> (z==nminus1)00176 <span class="keywordflow">return</span> <span class="keyword">true</span>;00177 <span class="keywordflow">if</span> (z==1)00178 <span class="keywordflow">return</span> <span class="keyword">false</span>;00179 }00180 <span class="keywordflow">return</span> <span class="keyword">false</span>;00181 }00182 00183 <span class="keywordtype">bool</span> RabinMillerTest(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &n, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> rounds)00184 {00185 <span class="keywordflow">if</span> (n <= 3)00186 <span class="keywordflow">return</span> n==2 || n==3;00187 00188 assert(n>3);00189 00190 <a class="code" href="class_integer.html">Integer</a> b;00191 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0; i<rounds; i++)00192 {00193 b.Randomize(rng, 2, n-2);00194 <span class="keywordflow">if</span> (!IsStrongProbablePrime(n, b))⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -