Study started since 2011年10月17日 素性测试算法，素性测定(11Y11) primality testing

14.32.MONTE CARLO PRIMALITY TESTS

MONTE CARLO PRIMALITY

14.32.1.A NOTE ON MONTE CARLO PRIMALITY TESTS AND ALGORITHMIC INFORMATION THEORY

Gregory J. Chaitin

IBM Thomas J. Watson Research Center

Jacob T. Schwartz1

Courant Institute of Mathematical Sciences
Algorithmic Information Theory

14.33.Pépin's

http://calistamusic.dreab.com/p-P%C3%A9pin%27s_test

In mathematics, http://calistamusic.dreab.com/p-Mathematics Pépin's test is a primality test, http://calistamusic.dreab.com/p-Primality_test which can be used to determine whether a Fermat number http://calistamusic.dreab.com/p-Fermat_number is prime http://calistamusic.dreab.com/p-Prime_number . It is a variant of Proth's test http://calistamusic.dreab.com/p-Proth%27s_theorem . The test is named for a French mathematician, Théophile Pépin http://calistamusic.dreab.com/p-Th%C3%A9ophile_P%C3%A9pin .

14.33.1.Contents 1 Description of the test 2 Proof of correctness 3 References 4 External links

14.33.2.Description of the test

Let be the nth Fermat number. Pépin's test states that for n > 0,

F_n is prime if and only if

The expression can be evaluated modulo F_n by repeated squaring. This makes the test a fast polynomial-time algorithm. However, Fermat numbers grow so rapidly that only a handful of Fermat numbers can be tested in a reasonable amount of time and space.

Other bases may be used in place of 3, for example 5, 6, 7, or 10 (sequence  A129802).

14.33.3.Proof of correctness

For one direction, assume that the congruence

holds. Then , thus the multiplicative order of 3 modulo F_n divides , which is a power of two. On the other hand, the order does not divide (F_n − 1) / 2, and therefore it must be equal to F_n − 1. In particular, there are at least F_n − 1 numbers below F_n coprime to F_n, and this can happen only if F_n is prime.

For the other direction, assume that F_n is prime. By Euler's criterion,

,

where is the Legendre symbol. By repeated squaring, we find that , thus , and . As , we conclude from the law of quadratic reciprocity.

14.33.4.References

• 
  P. Pépin, Sur la formule , Comptes Rendus Acad. Sci. Paris 85 (1877), pp. 329–333.
  

14.34.Proth's theorem

http://calistamusic.dreab.com/p-Proth%27s_theorem
http://www.peach.dreab.com/p-Proth%27s_theorem

Proth's test http://calistamusic.dreab.com/p-Proth%27s_theorem .

In number theory, Proth's theorem is a primality test for Proth numbers.

It states that if p is a Proth number, of the form k2ⁿ + 1 with k odd and k < 2ⁿ, then if for some integer a,

then p is prime (called a Proth prime). This is a practical test because if p is prime, any chosen a has about a 50 percent chance of working.

If p is a quadratic nonresidue modulo a then the converse is also true, and the test is conclusive. Such an a may be found by iterating a over small primes and computing the Jacobi symbol until:

14.34.1.Contents 1 Numerical examples 2 History 3 See also 4 References 5 External links

14.34.2.Numerical examples

Examples of the theorem include:

• 
  for p = 3, 2¹ + 1 = 3 is divisible by 3, so 3 is prime.
  
• 
  for p = 5, 3² + 1 = 10 is divisible by 5, so 5 is prime.
  
• 
  for p = 13, 5⁶ + 1 = 15626 is divisible by 13, so 13 is prime.
  
• 
  for p = 9, which is not prime, there is no a such that a⁴ + 1 is divisible by 9.
  

The first Proth primes are (sequence  A080076):

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ….

As of 2009, the largest known Proth prime is 19249 · 2^13018586 + 1, found by Seventeen or Bust. It has 3918990 digits and is the largest known prime which is not a Mersenne prime.

14.34.3.History

François Proth (1852 – 1879) published the theorem around 1878.

14.34.4.See also

• 
  Sierpinski number
  

14.34.5.References

14.35.Random Quadratic Frobenius Test (RQFT)

14.36.Solovay- Strassen算法

Solovay–Strassen

http://calistamusic.dreab.com/p-Solovay%E2%80%93Strassen_primality_test

14.36.1.Solovay-Strassen primality test.

We now turn to an RP algorithm for compositeness, the Solovay-Strassen

algorithm. First, we need to define a generalization of the Legendre

symbol called the Jacobi symbol:

If n = p1 * p2 * ... * pt, where the pi are primes not nec. distinct,

[a/n] = [a/p1]*[a/p2]*...*[a/pt].
It turns out that the Jacobi symbol can be calculated efficiently

(essentially using a Euclidean GCD-like algorithm) via a number of

identities that are not trivial to prove. A couple easy-to-prove

identities are: [ab/n] = [a/n]*[b/n], and if a=b (mod n) then [a/n]=[b/n].

Here is the Solovay-Strassen algorithm:
* Pick random a in {1,...,n-1}

* if gcd(a,n) != 1, then COMPOSITE.

* if [a/n] != a^{(n-1)/2} then COMPOSITE.

* else say POSSIBLY PRIME.

Thm: if n is composite, then this algorithm says "composite" with

probability at least 1/2.

Proof: the proof is much like that of our "key lemma".

Let J = {a in Z_n^* : [a/n] = a^{(n-1)/2} (mod n)}.

J is a group (e.g., use fact that [ab/n] = [a/n]*[b/n]) so it suffices

to show there exists b not in J. By the assumption that n is not a

prime power and is not a perfect square, we can write n = p1^e1 * r,

where p1 and r are realatively prime, and e1 is odd. Let g be an

arbitrary non-residue mod p1, and let b = (g,1), in CRT notation. We

can see that b^{(n-1)/2} = (g^{(n-1)/2}, 1) is *not* congruent to -1

(mod n), since -1 = (-1, -1). So, it suffices to show that [b/n] = -1.

This in turn follows from the basic Jacobi symbol identities:

[b/n] = ([b/p1])^e1 * [b/r] = ([g/p1])^e1 * [1/r] = (-1)^e1 * 1 = -1.

QED

14.36.2.Solovag-Strasson

Robert Solovag和Volker Strasson开发了一种概率的基本测试算法。这个算法使用了雅可比函数来测试p是否为素数：
（1） 选择一个小于p的随机数a。

（2） 如果 gcd(a,p) <> 1，那么 p 通不过测试，它是合数。

（3） 计算j=a^(p-1)/2 mod p。

（4） 计算雅可比符号J（a,p）。

（5） 如果j<>J（a,p），那么p肯定不是素数。

（6） 如果j=J(a,p),那麽p不是素数的可能性值多是50%

数a被称为一个证据，如果a不能确定p，p肯定不是素数。如果p是合数。随机数a是证据的概率不小于50%。对a选择t个不同的随机值，重复t次这种测试。p通过所有t次测试后，它是合数的可能性不超过1/2^t。

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.

14.36.3.Contents 1 Concepts 2 Example 3 Algorithm and running time 4 Accuracy of the test 5 Average-case behaviour 6 Complexity 7 References 8 Further reading

14.36.4.Concepts

Euler proved that for an odd prime number p and any integer a,

where is the Legendre symbol. The Jacobi symbol is a generalisation of the Legendre symbol to , 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

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). This base a is called an Euler witness for n; it is a witness for the compositeness of n. The base a is called an Euler liar for n if the congruence is true while n is composite.

For every composite odd n at least half of all bases

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.

14.36.5.Example

Suppose we wish to determine if n = 221 is prime. We write (n−1)/2=110.

We randomly select an a = 47 < n. We compute:

• 
  a^(n−1)/2 mod n  =  47¹¹⁰ mod 221  =  −1 mod 221
  
• 
  mod n  =  mod 221  =  −1 mod 221.
  

This gives that, either 221 is prime, or 47 is an Euler liar for 221. We try another random a, this time choosing a = 2:

• 
  a^(n−1)/2 mod n  =  2¹¹⁰ mod 221  =  30 mod 221
  
• 
  mod n  =  mod 221  =  −1 mod 221.
  

Hence 2 is an Euler witness for the compositeness of 221, and 47 was in fact an Euler liar. Note that this tells us nothing about the factors of 221 (which are 13 and 17).

14.36.6.Algorithm and running time

The algorithm can be written in pseudocode as follows:

Inputs: n, a value to test for primality; k, a parameter that determines the accuracy of the test

Output: composite if n is composite, otherwise probably prime

repeat k times:

choose a randomly in the range [2,n − 1]

x ←

if x = 0 or then return composite

return probably prime

Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k·log³ n), where k is the number of different values of a we test.

14.36.7.Accuracy of the test

It is possible for the algorithm to 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 number n is then called a pseudoprime.

When n is odd and composite, at least half of all a with gcd(a,n) = 1 are Euler witnesses. We can prove this as follows: let {a₁, a₂, ..., a_m} be the Euler liars and a an Euler witness. Then, for i = 1,2,...,m:

Because the following holds:

now we know that

This gives that each a_i gives a number a·a_i, which is also an Euler witness. So each Euler liar gives an Euler witness and so the number of Euler witnesses is larger or equal to the number of Euler liars. Therefore, when n is composite, at least half of all a with gcd(a,n) = 1 is an Euler witness.

Hence, the probability of failure is at most 2^−k (compare this with the probability of failure for the Miller-Rabin primality test, which is at most 4^−k).

For purposes of cryptography the more bases a we test, i.e. if we pick a sufficiently large value of k, the better the accuracy of test. Hence the chance of the algorithm failing in this way is so small that the (pseudo) prime is used in practice in cryptographic applications, but for applications for which it is important to have a prime, a test like ECPP or Pocklington should be used which proves primality.

14.36.8.Average-case behaviour

The bound 1/2 on the error probability of a single round of the Solovay–Strassen test holds for any input n, but those numbers n for which the bound is (approximately) attained are extremely rare. On the average, the error probability of the algorithm is significantly smaller: it is less than

for k rounds of the test, applied to uniformly random n ≤ x. 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.

14.36.9.Complexity

The Solovay–Strassen algorithm shows that the decision problem COMPOSITE is in the complexity class RP.

14.37.Square Root Compositeness Theorem

Given integers n, x, and y:

Then n is composite, and gcd(x-y, n) is a non-trivial factor

14.38.Schwartz--Zippel test

[Schwartz 1980; Zippel 1979],

15.Papers of Others

15.1.素性检测算法研究及其在现代密码学中的应用

专　业: 系统分析与集成

关键词: 素性检测 公钥密码学 公钥密码体制 椭圆曲线 离散对数

分类号: TN918.1

形　态: 共 63 页　约 41,265 个字　约 1.974 M内容

阅　读: 获取全文

优秀研究生学位论文题录展示

内容摘要
素数问题是一个使很多数学家着迷的问题。

素数就是一个除了1和它自身以外不能被其它数整除的数。
素数的一个基本问题是如何有效地确定一个数是否是一个素数，即素性测试问题。
素性测试问题不仅在数学上是一个有挑战性的问题，而且在实际应用中也是非常重要的。
在现代密码系统中，大素数的判别和寻找对一些加密系统的建立起着关键作用。
很多公钥密码算法都用到素数，特别是160位（二进制）以上的大素数。
RSA的公共模数就是两个512位以上的大素数的乘积；基于有限域PF上离散对数的公钥密码体制，其中素数p要求在512位以上；基于椭圆曲线离散对数的公钥密码体制（ECC）中，一般要求基点的阶是一个160位以上的大整数，且是一个素数。
由此可见对大数进行的素性判断的重要性。
判定一个整数是否是素数，最为简单的想法是直接利用素数的定义，用比要判断的整数小的素数去一一试除，如果能整除被检测的数的话，那就能确定无疑为合数了．但是对于大素数来说，由于计算量太大，根本无法实现以用于具体应用。
所以科学家们根据素数判断的理论发明了许多新的算法，提高了判断一个大数是否是一个大素数的效率。
Eratosthenes筛法是对于所有素数都有效的最古老的算法，然而它的时间复杂性是输入规模的幂指数，因此在实际中使用它是不合适的。
17世纪的Fermat小定理是一些有效素性测试算法的起点，但其逆定理是不满足的。
许多科学家在费马小定理的基础上进行研究发明了很多新的素数检测方法，但是这些算法大部分都是概率性的，比如说Miller-Rabin算法和Solovay-Strassen概率素数测试法。
直2002年，印度的三位科学家发明了确定性的素数检测算法AKS算法。
但是研究表明AKS算法的时间复杂度和空间复杂度并不能满足时间中的需要。
随着椭圆曲线算法的研究的开展，许多科学家又发明了利用椭圆曲线算法进行素性检测的方法，并且成为今年来素性检测领域里的一个重要方向。
本文也对2中基本的椭圆曲线素性检测算法做了简单的分析。
本文从素性检测算法的基本理论入手，对素性将测算法做一个全面的介绍，对大部分的素性检测算法进行了分析，其中着重对实践中常用的Miller-Rabin算法进行了分析，并且对Miller-Rabin算法做了一定的优化，使Miller-Rabin算法的效率提高了一倍，生成1024位素数的效率提升至，在1．5G的计算机上每1．5秒生成一个，并且给出了Miller-Rabin算法的算法流程图和部分关键代码的实现..……

全文目录
中文摘要

符号说明

第一章 引言

第二章 素性判定的概述

第三章 素性判定的理论依据

3.1 定义

3.2 素性判定方法理论依据

3.3 本章总结

第四章 几种素性检测算法研究

4.1 概率算法的基础

4.1.1 PP类

4.1.2 Monte Carlo算法

4.1.3 Las Vegas算法

4.2 几种素性检测所需要的算法的复杂度

4.2.1 欧几里德算法

4.2.2 模指数算法

4.2.3 随机素数的生成算法

4.2.4 计算Jacobi符号的算法

4.3 素性检测算法及其分析

4.3.1 Fermat小定理作为合性检测

4.3.2 Euler判则作为合性检测

4.3.3 Lucas检测算法

4.3.4 Pocklington检测算法

4.3.5 Demytko定理

4.3.6 Monte-Carlo算法进行素性检测

4.3.7 Las Vegas算法进行素性检测

4.3.8 Solovay-Strassen概率素数测试法

4.3.9 AKS素性检测算法

4.3.10 几种椭圆曲线素性检测算法

4.4 本章总结

第五章 Miller_Rabin素性检测算法

5.1 算法描述

5.2 算法分析

5.3 Miller-Rabin算法的流程图及关键部分的代码

5.3.1 Miller-Rabin算法的工作流程

5.3.2 Miller-Rabin算法中的测试函数

5.4 Miller-Rabin算法的一些优化

5.5 有关Miller-Rabin算法的最近一些进展

第六章 素性检测算法在密码学中的重要应用

6.1 RSA公钥密码算法

6.1.1 RSA加密解密运算

6.1.2 RSA签名体制

6.1.3 Rabin签名体制

6.3 ElGamal密码体制

6.3.2 ElGamal签名体制

6.4 本章总结

第七章 结束语及展望

参考文献

16.Math Tools

16.1.Axiom

16.2.Bignum

16.3.Derive

16.4.GMP Library

16.5.GNU Octave

16.6.Kant

A library for computational number theory

16.7.LiDIA

A library for computational number theory

Ingrid Biehl Johannes Buchmann Thomas Papanikolaou

Universitat des Saarlandes

Fachbereich

Saarbrucken

16.8.Lisp

16.9.Macsyma

16.10.Magma

Modular Exponentiation in Magma

16.11.Maple

Modular Exponentiation in Maple

16.12.MathCad

16.13.Mathematica

16.14.Matlab

the command rand(1) returns a random number between 0 and 1

16.15.Maxima

16.16.MIRACL

16.17.MuPAD

16.18.NTL library

16.19.OpenMP

16.20.Pari -GP

A library for computational number theory

16.21.Reduce

16.22.Sage

Prime Numbers and Integer Factorization in Sage

16.23.Simath

A library for computational number theory

16.24.Ubasic

17.COMPARISONS

18.MY IDEAS FOR FURTHER IMPROVEMENT OF COMPLEXITY

19.RESOURCES

19.1.MAJOR NUMBER THEORISTS

19.2.KEY UNIVERSITIES

19.3.KEY RESEARCH INSTITUTIONS

19.4.SEMINARS, SYMPOSIUMS, WORKSHOPS FORUMS

19.5.JOURNALS

19.6.ACADEMIC WEB RESOURCES

20.LITERATURE –PRIMALITY

20.1.BOOKS (BK)

20.2.LECTURE SCRIPTS

20.3.THESES FOR POSTDOC, PHD, MASTER AND BACHELOR DEGREES (PDT, DT,MT,BT)

20.3.1.BT- Bachelor Thesis

20.3.2.MT – Master Thesis

20.3.3.ST - Senior Thesis

20.4.GENERAL PAPER (GP)

20.5.COLLECTIONS OF PAPERS

20.6.PRESENTATIONS/SLIDES AT SEMINARS

20.7.OTHER PAPERS

20.8.PROPOSALS / SUGGESTIONS

21.LITERATURE – OTHER RELATED

21.1.ALGEBRA

21.2.NUMBER THEORY

21.3.COMPUTER COMPLEXITY

21.4.COMPLEX ANALYSIS / FUNCTIONS

21.5.Cryptography

22.APPENDICES

22.1.CHARTS

22.2.TABLES

22.3.DATABASES

22.4.MULTIMEDIA DATA

22.5.COMPUTATION CODES

22.6.WEBSITE FOR THIS THESIS