第六章 素性检验
6.1 拟素数
引例：根据Fermat 小定理，我们知道：如果n 是一个素数，则对任
意整数b,(b,n)=1,有
)(mod 11n b n ≡-
由此，我们得到：如果一个整数b,(b,n)=1,使得 )
(mod 11n b n ≡/-，则n 是一个合数。
定义1：设n 是一个奇合数，如果整数b,(b,n)=1使得同余式 )(mod 11n b n ≡-成立，则n 叫做对于基b 的拟素数。
引理：设d,n 都是正整数，如果d 能整除n 则
12-d 能整除12-n
定理1：存在无穷多个对于基2的拟素数。
定理2：设n 是一个奇合数，则
(i)n 是对于基b,((b,n)=1),的拟素数当且仅当b 模n 的指数整除n-1。
(ii)如果n 是对于基1b ((1b ,n)=1),和基2b ，((2b ,n)=1),的拟素数，则
n 是对于基21b b 的拟素数。
(iii)如果n 是对于基b,((b,n)=1),的拟素数，则n 是对于基1-b 的拟素数。
(iv)如果有一个整数b ，((b,n)=1),使得同余式
)(mod 11n b n ≡-不成立，则模n 的简化剩余系中至少有一半的数使得该同余式不成立。
//////////////////////////////////////////////////////////////////////////////////////////////////////////
Fermat 素性检验
给定奇整数3≥n 和安全参数t 。
1.随即选取整数
b ,22-≤≤n b ；
2.计算()n b r n mod 1-=;
3.如果1≠r ，则n 是合数；
4.上述过程重复t 次；
定义2：合数n 称为Carmichael 数，如果对所有的正整数b ，(b,n)=1,
都有同余式
()n b n mod 11≡-成立 定理3：设n 是一个奇合数。
(i)如果n 被一个大于1平方数整除，则n 不是Carmichael 数。
(ii)如果k p p n Λ1=是一个无平方数，则n 是Carmichael 数的充要条件是 11--n p i ，k i ≤≤1
定理4：每个Carmichael 数是至少三个不同素数的乘积
注：1.存在无穷多个Carmichael 数
2.当n 充分大时，区间[]n ,2内的Carmichael 数的个数大于等于72n 6.2 Euler 拟素数
引例：设n 是奇素数，根据定理，我们有同余式
)(mod 21n n b b n ⎪⎭
⎫ ⎝⎛≡- 对任意整数b 成立
因此，如果存在整数b ，(b,n)=1,使得
)(mod 21n n b b n ⎪⎭
⎫ ⎝⎛≡/- 则n 不是一个素数。
定义1:设n 是一个正奇合数，设整数b 与n 互素，如果整数n 和b 满足条件： )(mod 21n n b b n ⎪⎭
⎫ ⎝⎛≡- 则n 叫做对于基b 的Euler 拟素数。
定理1：如果n 是对于基b 的Euler 拟素数，则n 是对于基b 的拟素 数。
////////////////////////////////////////////////////////////////////////////////////////////////////////// Solovay-Stassen 素性检验
给定奇整数3≥n 和安全参数
t . 1.随即选取整数b ，
22-≤≤n b ； 2.计算);(mod 21n b r
n -= 3.如果1≠r 以及1-≠n r ，则n 是合数；
4.计算Jacobi 符号;⎪⎭⎫ ⎝⎛=n b s
5.如果s r ≠，则你是合数；
6.上述过程重复t 次。
6.3 强拟素数 引例：设n 是正奇整数，并且有t n n 2
1=-，则我们有如下因数分解式：)1)(1()1)(1(121221-+++=----t t t t n b b b b b n n Λ
因此，如果有同余式 )(mod 11n b n ≡-
则如下同余式至少有一个成立：
)
(mod 1)
(mod 1)
(mod 1)
(mod 1122n b n b n b n b t t t t n -≡-≡-≡≡-M
定义1：设n 是一个奇合数，且有表达式t n n 21=-，其中t 为奇数，
设整数b 与n 互素，如果整数n 和b 满足条件：
)(mod 1n b t ≡
或者存在一个整数，s r
<≤0使得 )(mod 12n b t r -≡
则n 叫做对于基b 的强拟素数。
定理1：存在无穷多个对于基2的强拟素数。
定理2:如果n 是对于基b 的强拟素数，n 是对于基b 的Euler 拟素数。
定理3：设n 是一个奇合数，则n 是对于基b ，11-≤≤n b ，的强拟素数的可能性至多为25%。
////////////////////////////////////////////////////////////////////////////////////////////////////////// Miller-Rabin 素性检验
给定奇整数3≥n 和安全参数k 。
写t n s
21=-，其中t 为奇整数。
1.随机选取整数22,-≤≤n b b 。
2.计算)(mod 0n b r t ≡；
3.(i )如果10=r 或10-=n r ，则通过检验，可能为素数。
回到1，
继续选取另一个随机整数22,-≤≤n b b ; (ii )否则，有10≠r 以及10-≠n r ，我们计算)(mod 201n r r ≡；
4.(i )如果11-=n r ，则通过检验，可能为素数。
回到1，继续选取另一个随机整数22,-≤≤n b b ； (ii )否则，有11-≠n r ，我们计算)(mod 212n r r ≡； 如此继续下去，
S+2.(i )如果11-=-n r s ，则通过检验，可能为素数。
回到1，继续选取另一个随机整数22,-≤≤n b b ; (ii )否则，有11-≠-n r s ，n 为合数。