素性检测算法收集

无心人

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime. It has been largely superseded by the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. Euler proved that for an odd prime number p and any integer a, [img=http://upload.wikimedia.org/math/a/8/a/a8ac36031e42f80ef378e14370d2927e.png]a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p[/img]where [img=http://upload.wikimedia.org/math/f/4/6/f4634283776435166feb8a4aa1bedd04.png]\left(\frac{a}{p}\right)[/img]is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to [img=http://upload.wikimedia.org/math/f/7/2/f72eaa241f8de63f6a59861c45239e3c.png]\left(\frac{a}{n}\right)[/img]where n can be any odd integer. The Jacobi symbol can be computed in time O((log n)²) using Jacobi's generalization of law of quadratic reciprocity. Given an odd number n we can contemplate whether or not the congruence [img=http://upload.wikimedia.org/math/b/1/f/b1f44b5ce18a810b4afcc171e9433443.png] a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod n[/img]holds for various values of the "base" a. If n is prime then this congruence is true for all a. So if we pick values of a at random and test the congruence, then as soon as we find an a which doesn't fit the congruence we know that n is not prime (but this does not tell us a nontrivial factorization of n). Call a base a an Euler witness for n if the above congruence with the Jacobi symbol does not hold at a — that is to say that a is a witness for the compositeness of n. For every composite odd n at least half of all bases [img=http://upload.wikimedia.org/math/6/a/4/6a43d7eee2ddf3119154692487ba0469.png]a \in (\mathbb{Z}/n\mathbb{Z})^* [/img]are (Euler) witnesses: this contrasts with the Fermat primality test, for which the proportion of witnesses may be much smaller. Therefore, there are no (odd) composite n without lots of witnesses, unlike the case of Carmichael numbers for Fermat's test. [edit] Algorithm and running timeThe algorithm can be written as follows: Inputs: n: a value to test for primality; k: a parameter that determines the accuracy of the testOutput: composite if n is composite, otherwise probably primerepeat k times:choose a at random in the interval [1,n − 1]x ← (a/n)if x = 0 or a(n − 1)/2 mod n ≠ x then return compositereturn probably primeUsing fast algorithms for modular exponentiation, the running time of this algorithm is [img=http://upload.wikimedia.org/math/5/a/d/5adebe89a8ab990233e92f8b8a657e2e.png]\mathcal O(k \times \log^3 n)[/img], where k is the number of "rounds", that is random choices of base a, and n is the value we want to test for primality. It is possible for the algorithm to "fail", that is, return an incorrect answer. If the input n is indeed prime, then the output will always correctly be probably prime. However, if the input n is composite then it is possible for the output to be incorrectly probably prime. The probability of failure is at most 2−k. For purposes of cryptography if we pick a sufficiently large value of k,such as 100, the chance of the algorithm failing in this way is sosmall that we can use the prime in cryptographic applications withoutworrying. [edit] Average-case behaviourThe bound 1/2 on the error probability of a single round of the Solovay–Strassen test holds for any input n, but those numbers nfor which the bound is (approximately) attained are extremely rare. Onthe average, the error probability of the algorithm is significantlysmaller: it is less than [img=http://upload.wikimedia.org/math/1/f/3/1f3e126f85de2c442b152d9400737c72.png]2^{-k}\exp\left(-(1+o(1))\frac{\log x\,\log\log\log x}{\log\log x}\right)[/img]for k rounds of the test, applied to uniformly random n ≤ x.[1][2] The same bound also applies to the related problem of what is the conditional probability of n being composite for a random number n ≤ x which has been declared prime in k rounds of the test.

无心人

Miller-Rabin和Fermat算法因为经常被提到，所以略过 有兴趣的帮我在这里补充 =================================== 另外，这里的算法大部分是从英文资料拷贝过来的 但很容易翻译，看明白 汉语资料很少，有知道的提供，我再改到中文

无心人

Baillie-PSW primality test From Wikipedia, the free encyclopedia Jump to: navigation, search In number theory, the Baillie-PSW primality test is a probabilistic primality testing heuristic: it determines if a number is composite or a probable prime.The authors of the test offered \$30 for the discovery of a compositenumber that passed this test. As of today, the value was raised to \$620(Guy 1994, p. 28) and no pseudoprime was found up to $10^15$, consequently this can be considered a sound primality test on numbers below that upper bound. A primality testing implementation (PRIMO) uses this algorithm to check for probable primes,and no certification of this test has yet failed. The author, MarcelMartin, estimates by those results that the test is accurate fornumbers below 10000 digits. There is a heuristic argument (Pomerance 1984) suggesting that there may be infinitely many counterexamples. [edit] The testPerform a base 2 strong pseudoprimality test. If it fails; n is composite. If it doesn't, find the first a in the sequence 5, -7, 9, -11... for which the Jacobi symbol [img=http://upload.wikimedia.org/math/9/b/4/9b4efea22607b8ac8f781ce1351a1fa6.png]\left(\frac{a}{n}\right) = -1[/img]. Then, perform a Lucas pseudoprimality test with discriminant a on n. If this test does not fail, n is likely a prime. Optionally, one can first perform trial division to check if the number isn't a multiple of a small prime number.

无心人

Lucas pseudoprime（Lucas素性测试） From Wikipedia, the free encyclopedia In number theory, the classes of Lucas pseudoprime and Fibonacci pseudoprime comprise sequences of composite integers that passes certain tests that all primes pass: in this case, criteria relative to some Lucas sequence. DefinitionGiven two integer parameters P and Q which satisfy [img=http://upload.wikimedia.org/math/d/3/e/d3e982438078471ba39770d7260420a9.png]D = P^2 - 4Q \neq 0 ,[/img] the Lucas sequences of the first and second kind, Un(P,Q) and Vn(P,Q) respectively, are defined by the recurrence relations [img=http://upload.wikimedia.org/math/8/b/0/8b08175c9e31647813a13ddc98b374c4.png]U_0(P,Q)=0 \,[/img] [img=http://upload.wikimedia.org/math/9/8/b/98ba9238398ec3c91d8441e5826194d1.png]U_1(P,Q)=1 \,[/img] [img=http://upload.wikimedia.org/math/9/a/4/9a46a8ecbb888eb6501179bdb5f6b765.png]U_n(P,Q)=PU_{n-1}(P,Q)-QU_{n-2}(P,Q) \mbox{ for }n>1 \,[/img] and [img=http://upload.wikimedia.org/math/d/a/6/da6477c58672e5f5623ac18b803ed499.png]V_0(P,Q)=2 \,[/img] [img=http://upload.wikimedia.org/math/5/3/3/53345185887ea556882e1f24c287b30f.png]V_1(P,Q)=P \,[/img] [img=http://upload.wikimedia.org/math/4/5/2/452270dd8e50a060a8875956ad0d68a5.png]V_n(P,Q)=PV_{n-1}(P,Q)-QV_{n-2}(P,Q) \mbox{ for }n>1 \,[/img] We can write [img=http://upload.wikimedia.org/math/1/e/3/1e345f4b1a7a69a8aa4b88aefd7978d9.png]U_n(P,Q) = \frac{a^n-b^n}{a-b} \,[/img] [img=http://upload.wikimedia.org/math/3/9/9/3998f696038a67c212febef42406c121.png]V_n(P,Q) = a^n + b^n \,[/img] where a and b are roots of the auxiliary polynomial $X^2 - PX + Q$, of discriminant D. If p is an odd prime number then Vp is congruent to P modulo p.and if the Jacobi symbol [img=http://upload.wikimedia.org/math/7/2/6/726ae3b242cf982e658bc00769726abb.png]\left(\frac{D}{p}\right) = \varepsilon \ne 0[/img], then p is a factor of Up-ε. [edit] Lucas pseudoprimesA Lucas pseudoprime is a composite number n for which n is a factor of Un-ε. (Riesel adds the condition that D should be −1.) In the specific case of the Fibonacci sequence, where P = 1, Q = 1 and D = 5, the first Lucas pseudoprimes are 323 and 377; [img=http://upload.wikimedia.org/math/8/4/2/842c77a349e7bd8b1e4c9b7e12085eb8.png]\left(\frac{5}{323}\right)[/img] and [img=http://upload.wikimedia.org/math/a/6/3/a633dee94d7f67af1aceab21ad654abb.png]\left(\frac{5}{377}\right)[/img] are both −1, the 324th Fibonacci number is a multiple of 323, and the 378th is a multiple of 377. A strong Lucas pseudoprime is an odd composite number n with (n,D)=1, and n-ε=2rs with s odd, satisfying one of the conditions n divides Usn divides V2jsfor some j ≤ r. A strong Lucas pseudoprime is also a Lucas pseudoprime. An extra strong Lucas pseudoprime is a strong Lucas pseudoprime for a set of parameters (P,Q) where Q = 1. [edit] Fibonacci pseudoprimesA Fibonacci pseudoprime is a composite number n for which Vn is congruent to P modulo nwhen Q = ±1. A strong Fibonacci pseudoprime may be defined as a composite number which is a Fibonacci pseudoprime for all P. It follows (see Müller and Oswald) that in this case:

• An odd composite integer n is also a Carmichael number
• 2(pi + 1) | (n − 1) or 2(pi + 1) | (n − pi) for every prime pi dividing n.

The smallest example of a strong Fibonacci pseudoprime is443372888629441, which has factors 17, 31, 41, 43, 89, 97, 167 and 331. It is conjectured that there are no even Fibonacci pseudoprimes (see Somer).

无心人

椭圆曲线素性检测算法（确定性） ECPP Elliptic Curve Primality Proving (ECPP) is a method based on elliptic curves to prove the primality of a number. It is a general-purpose algorithm,meaning it does not depend on the number being a special form. ECPP iscurrently in practice the fastest known algorithm for testing theprimality of general numbers, but the worst-case execution time is not known. ECPP heuristically runs in time:[1] O((lnn)5 + ε)for some ε > 0. This exponent may be decreased to 4 + ε for some versions by heuristic arguments. This exponent is less than that of the AKS method. ECPP works the same way as most other primality tests do, finding a group and showing its size is such that p is prime. For ECPP the group is an elliptic curve over a finite set of quadratic forms such that p − 1 is trivial to factor over the group. ECPP generates an Atkin-Goldwasser-Kilian-Morain certificate of primality by divide and conquer and then attempts to verify the certificate. The step that takes the most CPU time is the certificate generation, because factoring over a class field must be performed. The certificate can be verified quickly, allowing a check of operation to take very little time. As of April 2008 the largest prime that has been proved with ECPP is the 20,562-digit Mills' prime:[2][3] (((((((((23 + 3)3 + 30)3 + 6)3 + 80)3 + 12)3 + 450)3 + 894)3 + 3636)3 + 70756)3 + 97220The distributed computation with software by François Morain started in September 2005 and ended in June 2006. The cumulated time corresponds to one AMD Opteron Processor 250 at 2.39 GHz for 2219 days (near 6 years).[4] 详细叙述其原理，要写的东西太多，上论文 atkin93elliptic.rar (295.13 KB, 下载次数: 9)

2008-11-23 10:14 上传

点击文件名下载附件

无心人

AKS算法其相关资料看 http://bbs.emath.ac.cn/viewthrea ... fromuid=80#pid11628

无心人

Adleman–Pomerance–Rumely primality test The Adleman–Pomerance–Rumely primality test (APR) is a deterministic algorithm that tests if a positive integer is prime. It is named after its discoverers, Leonard Adleman, Carl Pomerance, and Robert Rumely. It was later improved by Henri Cohen and Arjen Lenstra and called APRT-CL. It is often used with UBASIC under the name APRT-CLE (APRT-CL extended) and has complexity [img=http://upload.wikimedia.org/math/9/2/4/924cde8cc73d318f51c120971342ca1a.png](\log n)^{O(\log\,\log \,\log n)}.[/img] 详细的看这个论文 http://bbs.emath.ac.cn/viewthrea ... fromuid=80#pid11628

random84

7# 无心人 正在找这一类的东西，感谢，下载来看看

mathematica

在概率中生存，顶baillie PSW算法，再使用几个随机的Miller Rabin作为补充，已经完全能够满足实际使用的需求。这个思想也就是pari/gp的思想，我喜欢pari/gp的这个思想，但是不喜欢它的使用界面，觉得太丑了