Study started since 2011年10月17日 素性测试算法，素性测定(11Y11) primality testing
Yüklə 1,18 Mb.
|
- Bu səhifədəki naviqasiya:
- 14.22.4.Algorithm and running time
- 14.23.Fermat-Euler 14.24.Frobenius pseudoprimality test
- 14.30.Maurer‟s algorithm
- 14.31.1.快速判定素数-----Miller-Rabin算法
- 14.31.2.Miller-Rabin Algorithm
- 14.31.3.Miller-Rabbin素性测试[ZJUT1517]
- 14.31.8.Algorithm and running time
- 14.31.9.Accuracy of the test
- 14.31.10.Deterministic variants of the test
14.20.Demytko14.21.Euler Test14.22.Fermat素性测试http://www.doc.ic.ac.uk/~cd04/430notes/fermat.jar http://kobep525.rsjp.net/~math/notes/note02.html http://calistamusic.dreab.com/p-Fermat_primality_test
If n is prime and doesn’t divide a, then 
The Fermat primality test is a probabilistic test to determine if a number is probable prime.
14.22.2.ConceptFermat's little theorem states that if p is prime and  , then
If we want to test if p is prime, then we can pick random a's in the interval and see if the equality holds. If the equality does not hold for a value of a, then p is composite. If the equality does hold for many values of a, then we can say that p is probable prime. It might be in our tests that we do not pick any value for a such that the equality fails. Any a such that
when n is composite is known as a Fermat liar. Vice versa, in this case n is called Fermat pseudoprime to base a. If we do pick an a such that
then a is known as a Fermat witness for the compositeness of n. 14.22.3.ExampleSuppose we wish to determine if n = 221 is prime. Randomly pick 1 ≤ a < 221, say a = 38. Check the above equality: 
Either 221 is prime, or 38 is a Fermat liar, so we take another a, say 26: 
So 221 is composite and 38 was indeed a Fermat liar. 14.22.4.Algorithm and running timeThe algorithm can be written as follows: Inputs: n: a value to test for primality; k: a parameter that determines the number of times to test for primality Output: composite if n is composite, otherwise probably prime repeat k times: pick a randomly in the range [1, n − 1] if return probably prime Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k × log2n × log log n × log log log n), where k is the number of times we test a random a, and n is the value we want to test for primality. 14.22.5.FlawThere are infinitely many values of n (known as Carmichael numbers) for which all values of a for which gcd(a,n) = 1 are Fermat liars. While Carmichael numbers are substantially rarer than prime numbers, there are enough of them that Fermat's primality test is often not used in favor of other primality tests such as Miller-Rabin and Solovay-Strassen. In general, if n is not a Carmichael number then at least half of all 
are Fermat witnesses. For proof of this, let a be a Fermat witness and a1, a2, ..., as be Fermat liars. Then 
and so all 14.22.6.ApplicationsThe encryption program PGP uses this primality test in its algorithms. The chance of PGP generating a Carmichael number is less than 1 in 1050, which is more than adequate for practical purposes. 14.23.Fermat-Euler14.24.Frobenius pseudoprimality testhttp://www.peach.dreab.com/p-Frobenius_pseudoprime 14.25.Goldwasser Kilian Algorithm14.26.Gordon‟s algorithm14.27.雅克比和素性判别方法14.28.Konyagin – Pomerance n-1 Test14.29.Lehmann另一种更简单的测试是由Lehmann独自研究的。下面是它的测试算法： （1） 选择一个小于p的随机数a。 （2） 计算a^(p-1)/2 mod p （3） 如果a^(p-1)/2<>1或-1（mod p），那么p肯定不是素数。 （4） 如果a^(p-1)/2=1或-1（mod p），那麽p不是素数的可能性值多是50% 同样，重复t次，那麽p可能是素数所冒的错误风险不超过1/2^t。 14.30.Maurer‟s algorithm14.31.Miller-Rabin / Rabin-Miller素性测试算法Miller-Rabin Compositeness Testhttp://en.literateprograms.org/Category:Miller-Rabin_primality_test http://www.cryptomathic.com/Default.aspx?ID=479 http://calistamusic.dreab.com/p-Miller%E2%80%93Rabin_primality_test Verification of the Miller–Rabin probabilistic primality test This primality test is also called the Selfridge-Miller-Rabin test or the strong prime test. It is a refinement of the Fermat test which works very well in practice. 14.31.1.快速判定素数-----Miller-Rabin算法说Miller-Rabin.这是个很容易且广泛使用的简单算法，它基于Gary Miller的部分象法，有Michael Rabin发展。事实上，这是在NIST的DSS建议中推荐的算法的一个简化版。 更多的人叫它“测试”，因为通过Miller-Rabin测试的并不一定就是素数，非素数通过测试的概率是1/4。它的原理无论如何都会让人想起“费马小定理“ 费马小定理 如果P是一个素数，且0则a^(p-1)≡1(mod p) 例如，67是一个素数，则2^66mod 67=1。 利用费马小定理，对于给定的整数n，可以设计一个素数判定算法。通过计算d=2^(n-1)mod n来判定整数n的素性。当d不等于1时，n肯定不是素数；当d等于1时，n则很可能是素数。但也存在合数n使得2^(n-1)≡1(mod n)。例如，满足此条件的最小合数是n=341。为了提高测试的准确性，我们可以随机地选取整数1 费马小定理毕竟只是素数判定的一个必要条件。满足费马小定理条件的整数n未必全是素数。有些合数也满足费马小定理的条件。这些合数被称做Carmichael数，前3个Carmichael数是561,1105,1729。Carmichael数是非常少的。在1~100,000,000范围内的整数中，只有255个Carmichael数。利用下面的二次探测定理可以对上面的素数判定算法作进一步改进，以避免将Carmichael数当作素数。 二次探测定理 如果p是一个素数，0 上面是在王晓东的《计算机算法分析与设计》上抄录的，看不懂网上的文章，就这个解释费马小定理的我看懂了-___-。下面具体说一下算法的步骤吧,n是我们要测试的数据: 0、先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数 1、随机取一个b，2<=b 2、计算v=b^m mod n 3、如果v==1，通过测试，返回 4、令i=1 5、如果v=n-1，通过测试，返回 6、如果i==j，非素数，结束 7、v=v^2 mod n，i=i+1 8、循环到5
We now describe one final RP alg for compositeness. This is along the lines of using a^{n-1} =? 1 (mod n) as a test. * Let n = 2^r * B, where B is odd. * pick a in {1,...,n-1} at random. * Compute a^B, a^{2B}, ..., a^{n-1} (mod n). * If a^{n-1} != 1 (mod n), then output COMPOSITE * If we found a non {-1,+1} root of 1 in the above list, then output COMPOSITE. * else output POSSIBLY PRIME. Note that we only have to worry about Carmichael numbers (composite n such that all a in Z_n^* satisfy a^{n-1} = 1 (mod n)). For all other composite numbers, at least half of the a's don't have this property (since {a : a^{n-1} = 1 (mod n)} is a group). Here's how we can argue for Carmichael numbers: Suppose there exists a in Z_n^* satisfying a^{(n-1)/2} != 1 (mod n). Then our "Key Lemma" implies that with probability at least 1/2, we will find a non {-1,+1} root of 1 in computing a^{(n-1)/2} and output COMPOSITE. If no such a exists, but there exists b in Z_n^* such that b^{(n-1)/4} != 1 (mod n) then similarly we're OK (assuming n-1 is divisible by 4). Going down the line from right-to-left, we can now assume w.l.o.g. that all a in z_n^* satisfy a^B = 1 (mod n). We now show a contradiction: let n=p1^e1 * r, where e1 is odd and p1 and r are relatively prime. Let g be a generator mod p1^e1 (we didn't prove it, but the prime power groups are cyclic too; actually, Carmichael numbers must be products of distinct primes, but we didn't prove that either). Let a = (g,1) using CRT notation. If a^B = 1 (mod n) then g^B = 1 (mod p1^e1), which means that B must be a multiple of phi(p1^e1) since g is a generator. But B is odd and phi(p1^e1) is even, a contradiction. QED
#include #include using namespace std; inline long long mul(long long a,long long b,long long m)//a * b % m { long long ret = 0; while (b > 0) { if (b & 1) ret = (ret + a) % m; b >>= 1;
a = (a << 1) % m; } return ret; } inline long long mod(long long a,long long b,long long m)//a^b % m { long long res,t; res = 1; t = a;
while (b > 0) { if (b & 1) res = mul(res,t,m);//res = res * t % m; t = mul(t,t,m);//t = t * t % m; b >>= 1; } return res; } inline bool Miller_Rabbin(long long n) { long long a; for (int i = 0;i < 5;i++) { a = (long long)rand()*rand()*rand() % (n-2) +2; if (mod(a,n-1,n) != 1) return false; } return true; } int main() { long long n; srand((unsigned)time(NULL)); while (scanf("%I64d",&n) != EOF) { if (n == 2 || Miller_Rabbin(n)) printf("Yes\n"); else
printf("No\n"); } return 0; } 14.31.4.Rabin-Miller这是个很容易且广泛使用的简单算法，它基于Gary Miller的部分象法，有Michael Rabin发展。事实上，这是在NIST的DSS建议中推荐的算法的一个简化版。 首先选择一个代测的随机数p，计算b，b是2整除p-1的次数。然后计算m，使得n=1+(2^b)m。 （1） 选择一个小于p的随机数a。 （2） 设j=0且z=a^m mod p （3） 如果z=1或z=p-1，那麽p通过测试，可能使素数 （4） 如果j>0且z=1, 那麽p不是素数 （5） 设j=j+1。如果j （6） 如果j=b 且z<>p-1，不是素数 这个测试较前一个速度快。数a被当成证据的概率为75%。这意味着当迭代次数为t时，它产生一个假的素数所花费的时间不超过1/4^t。实际上，对大多数随机数，几乎99.99%肯定a是证据。 实际考虑： 在实际算法，产生素数是很快的。 （1） 产生一个n-位的随机数p （2） 设高位和低位为1（设高位是为了保证位数，设低位是为了保证位奇数） （3） 检查以确保p不能被任何小素数整除：如3，5，7，11等等。有效的方法是测试小于2000的素数。使用字轮方法更快 （4） 对某随机数a运行Rabin-Miller检测，如果p通过，则另外产生一个随机数a,在测试。选取较小的a值，以保证速度。做5次 Rabin-Miller测试如果p在其中失败，从新产生p，再测试。 在Sparc II上实现： 2 .8秒产生一个256位的素数 24.0秒产生一个512位的素数 2分钟产生一个768位的素数 5.1分钟产生一个1024位的素数 The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version, due to Gary L. Miller, is deterministic, but the determinism relies on the unproven generalized Riemann hypothesis; Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm.
14.31.6.ConceptsJust like the Fermat and Solovay–Strassen tests, the Miller–Rabin test relies on an equality or set of equalities that hold true for prime values, then checks whether or not they hold for a number that we want to test for primality. First, a lemma about square roots of unity in the finite field 
In other words, p divides the product (x − 1)(x + 1). It thus divides one of the factors and it follows that x is either congruent to 1 or −1 mod p. Now, let n be an odd prime. Then n−1 is even and we can write it as 2s·d, where s and d are positive integers (d is odd). For each or
To show that one of these must be true, recall Fermat's little theorem:
By the lemma above, if we keep taking square roots of an − 1, we will get either 1 or −1. If we get −1 then the second equality holds and we are done. If we never get −1, then when we have taken out every power of 2, we are left with the first equality. The Miller–Rabin primality test is based on the contrapositive of the above claim. That is, if we can find an a such that
and
 for all 
then n is not prime. We call a a witness for the compositeness of n (sometimes misleadingly called a strong witness, although it is a certain proof of this fact). Otherwise a is called a strong liar, and n is a strong probable prime to base a. The term "strong liar" refers to the case where n is composite but nevertheless the equations hold as they would for a prime. For every odd composite n, there are many witnesses a. However, no simple way of generating such an a is known. The solution is to make the test probabilistic: we choose nonzero 14.31.7.ExampleSuppose we wish to determine if n = 221 is prime. We write n − 1 = 220 as 22·55, so that we have s = 2 and d = 55. We randomly select a number a such that a < n, say a = 174. We proceed to compute:
Since 220 ≡ −1 mod n, either 221 is prime, or 174 is a strong liar for 221. We try another random a, this time choosing a=137:
Hence 137 is a witness for the compositeness of 221, and 174 was in fact a strong liar. Note that this tells us nothing about the factors of 221 (which are 13 and 17). 14.31.8.Algorithm and running timeThe algorithm can be written in pseudocode as follows: Input: n > 3, an odd integer to be tested for primality; Input: k, a parameter that determines the accuracy of the test Output: composite if n is composite, otherwise probably prime write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1 LOOP: repeat k times: pick a random integer a in the range [2, n − 2] x ← ad mod n if x = 1 or x = n − 1 then do next LOOP for r = 1 .. s − 1
if x = 1 then return composite if x = n − 1 then do next LOOP return composite return probably prime Using modular exponentiation by repeated squaring, the running time of this algorithm is O(k log3 n), where k is the number of different values of a we test; thus this is an efficient, polynomial-time algorithm. FFT-based multiplication can push the running time down to O(k log2 n log log n log log log n) = Õ(k log2 n). In the case that the algorithm returns "composite" because x = 1, it has also discovered that d2r is (an odd multiple of) the order of a — a fact which can (as in Shor's algorithm) be used to factorize n, since n then divides On average the probability that a composite number is declared probably prime is significantly smaller than 4−k. Damgård, Landrock and Pomerance compute some explicit bounds. Such bounds can, for example, be used to generate primes; however, they should not be used to verify primes with unknown origin, since in cryptographic applications an adversary might try to send you a pseudoprime in a place where a prime number is required. In such cases, only the error bound of 4−k can be relied upon. 14.31.10.Deterministic variants of the testThe Miller–Rabin algorithm can be made deterministic by trying all possible a below a certain limit. The problem in general is to set the limit so that the test is still reliable. If the tested number n is composite, the strong liars a coprime to n are contained in a proper subgroup of the group Input: n > 1, an odd integer to test for primality. Output: composite if n is composite, otherwise prime write n−1 as 2s·d by factoring powers of 2 from n−1 repeat for all then return composite return prime The running time of the algorithm is Õ((log n)4). The full power of the generalized Riemann hypothesis is not needed to ensure the correctness of the test: as we deal with subgroups of even index, it suffices to assume the validity of GRH for quadratic Dirichlet characters. This algorithm is not used in practice, as it is much slower than the randomized version of the Miller-Rabin test. For theoretical purposes, it was superseded by the AKS primality test, which does not rely on unproven assumptions. When the number n to be tested is small, trying all a < 2(ln n)2 is not necessary, as much smaller sets of potential witnesses are known to suffice. For example, Pomerance, Selfridge and Wagstaff and Jaeschke have verified that
See The Primes Page, Zhang and Tang, SPRP records and sequence  A014233 in OEIS for other criteria of this sort. These results give very fast deterministic primality tests for numbers in the appropriate range, without any assumptions.
There is a small list of potential witnesses for every possible input size (at most n values for n-bit numbers). However, no finite set of bases is sufficient for all composite numbers. Alford, Granville, and Pomerance have shown that there exist infinitely many composite numbers n whose smallest compositeness witness is at least (ln n)1/(3ln ln ln n). They also argue heuristically that the smallest number w such that every composite number below n has a compositeness witness less than w should be of order Θ(log n log log n). 14.31.11.NotesYüklə 1,18 Mb. Dostları ilə paylaş:
|
for i = 1,2,...,s are Fermat witnesses.
, where p is prime and p > 2. Certainly 1 and −1 always yield 1 
, either
for some 
randomly, and check whether or not it is a witness for the compositeness of n. If n is composite, most of the choices for a will be witnesses, and the test will detect n as composite with high probability. There is, nevertheless, a small chance that we are unlucky and hit an a which is a strong liar for n. We may reduce the probability of such error by repeating the test for several independently chosen a.
but not either factor by itself. The reason Miller–Rabin does not yield a probabilistic factorization algorithm is that if 
, which means that if we test all a from a set which generates 
:
