2024年1月4日发(作者：温江教师招聘小学数学试卷)

第六章 素性检验

6.1 拟素数

引例：根据Fermat小定理，我们知道：如果n是一个素数，则对任意整数b,(b,n)=1,有

n1b1(modn)

由此，我们得到：如果一个整数b,(b,n)=1,使得

n1b1(modn) ，则n是一个合数。

定义1：设n是一个奇合数，如果整数b,(b,n)=1使得同余式

bn11(modn)成立，则n叫做对于基b拟素数。

引理：设d,n都是正整数，如果d能整除n则定理1：存在无穷多个对于基2拟素数。

定理2：设n是一个奇合数，则

(i)n是对于基b,((b,n)=1),拟素数当且仅当b模n指数整除n-1。

(ii)如果n是对于基b1((b1,n)=1),和基b2，((b2,n)=1),拟素数，则n是对于基b1b2拟素数。

1b(iii)如果n是对于基b,((b,n)=1),拟素数，则n是对于基拟素数。

21能整除21

dn(iv)如果有一个整数b，((b,n)=1),使得同余式bn11(modn)不成立，则模n简化剩余系中至少有一半数使得该同余式不成立。

//////////////////////////////////////////////////////////////////////////////////////////////////////////

1 / 5

Fermat 素性检验

给定奇整数n3和安全参数t。

1.随即选取整数b,2bn1modn;

rb2.计算n2；

3.如果r1，则n是合数；

4.上述过程重复t次；

定义2：合数n称为Carmichael数，如果对所有正整数b，(b,n)=1, 都n1b1modn成立

有同余式定理3：设n是一个奇合数。

(i)如果n被一个大于1平方数整除，则n不是Carmichael数。

(ii)如果n是

p1pk是一个无平方数，则n是Carmichael数充要条件

pi1n1，1ik定理4：每个Carmichael数是至少三个不同素数乘积

注：1.存在无穷多个Carmichael数

2.当n充分大时，区间2,n内Carmichael数个数大于等于n27

6.2 Euler拟素数

引例：设n是奇素数，根据定理，我们有同余式

bn12b(modn)

n对任意整数b成立

因此，如果存在整数b，(b,n)=1,使得

2 / 5

bn12b(modn)

n则n不是一个素数。

定义1:设n是一个正奇合数，设整数b与n互素，如果整数n和b满足条件：

bn12b(modn)

n则n叫做对于基bEuler拟素数。

定理1：如果n是对于基bEuler 拟素数，则n是对于基b拟素 数。

//////////////////////////////////////////////////////////////////////////////////////////////////////////

Solovay-Stassen素性检验

给定奇整数n3和安全参数t.

1.随即选取整数b，22.计算r3.如果rbn2；

bn12(modn);

1以及rn1，则n是合数；

bs;4.计算Jacobi符号n

5.如果rs，则你是合数；

6.上述过程重复t次。

n 6.3 强拟素数

引例：设n是正奇整数，并且有n12t，则我们有如下因数分解式：bn11(b2n1t1)(b2n2t1)(bt1)(bt1)

3 / 5

因此，如果有同余式

bn11(modn)

则如下同余式至少有一个成立：

bt1(modn)b1(modn)b1(modn)

2n1t2ttb1(modn)nn12t，其中t为奇数，定义1：设n是一个奇合数，且有表达式设整数b与n互素，如果整数n和b满足条件：

tb1(modn)

或者存在一个整数，0

rs使得

b2rt1(modn)

则n叫做对于基b强拟素数。

定理1：存在无穷多个对于基2强拟素数。

定理2:如果n是对于基b强拟素数，n是对于基bEuler拟素数。

定理3：设n是一个奇合数，则n是对于基b，1bn1，强拟素数可能性至多为25%。

//////////////////////////////////////////////////////////////////////////////////////////////////////////

Miller-Rabin素性检验

给定奇整数n3和安全参数k。

4 / 5

写n12st，其中t为奇整数。

1.随机选取整数b,2bn2。

t2.计算r0b(modn)；

3.(i)如果r01或r0n1，则通过检验，可能为素数。回到1，继续n2;

2选取另一个随机整数b,2b (ii)否则，有r01以及r0n1，我们计算r1r0(modn)；

4.(i)如果r1n1，则通过检验，可能为素数。回到1，继续选取另一个随机整数b,2bn2；

r(modn)；

21 (ii)否则，有r1n1，我们计算r2 如此继续下去，

S+2.(i)如果rs1n1，则通过检验，可能为素数。回到1，继续选取另一个随机整数b,2bn2;

(ii)否则，有rs1n1，n为合数。

5 / 5


更多推荐

整数,素数,选取,回到,检验,合数,定理,可能