代表作常用主要专业术语、记号
:
通过基 b 的Fermat 测试,
通过基 b 的概素数(probable prime, prp(b)), 通过基 b 的伪素数 (pseudoprime, psp(b)), Carmichal 数;
通过基 b 的 Miller 测试, 通过基 b 的强概素数
(strong probable prime, 简记 sprp(b)), 通过基 b 的强伪素数(strong pseudoprime, 简记spsp(b)),
Kk-数, C3-数
通过双参数基 (P, Q) 的 Lucas 测试, 通过双参数基 (P, Q) 的 Lucas 概素数 (Lucas probable prime, 简记 lprp(P, Q)).
通过双参数基 (P, Q) 的 强 Lucas 测试,
通过双参数基 (P, Q) 的 强 Lucas 概素数 (strong Lucas probable
prime, 简记 slprp(P, Q)).
通过双参数基 (P, Q) 的 Lucas 伪素数 (Lucas pseudoprime, 简记
lpsp(P, Q)). 通过双参数基 (P, Q) 的强Lucas 伪素数(strong
Lucas pseudoprime,简记
slpsp(P, Q)).
-------------------------------------------------------------------------------------------------------------------------------------
如果 n 是素数, 那么对于任一个与n 互素的整数 b, 同余式
(1)
bn−1 ≡1 mod n
都成立. 这就是Fermat 小定理.
由Fermat
小定理， 我们可以证明一个整数是合数. 例如
262 = 22(26)10 =
4 ·
6410 ≡4 mod
63, 所以由 Fermat 小定理得知63是合数.
Fermat 小定理的逆不真. 我们不能用它来证明一个整数是素数.
给定正整数 n, 如果有整数 b使得 (1)成立,我们就说 n 通过了基b的 Fermat 测试,
称 n 是通过基 b 的概素数 (probable prime), 简记 prp(b).
它可能是素数也可能是合数, 如果 n是合数, 就称 n是通过基 b 的伪素数 (pseudoprime), 简记 psp(b).
例如由Fermat
小定理,
210 ≡1 mod 11 ==> 2340 ≡1 mod 11. 另一方面, 2340 = (25)68 ≡1
mod 31 ==> 2340 ≡1 mod 11 ·
31
==> 2340 ≡1 mod 341
==> 341通过了基 2 Fermat 测试
==> 341是 prp(2).
但 7340 ≡56
mod 341 ==> 341通不过基 7 的 Fermat 测试 ==> 341 是合数
==> 341是 psp(2).
也有这样的
奇合数 n, 称为 Carmichal 数, 它是通过每个与 n 互素基的伪素数. 例如, 561=3· 11· 17是 Carmichal 数, 它对于任一个与561 互素的整数 b 都是psp(b). 1992年, Alford, Granville 和 Pomerance 证明了有无穷多个Carmichal 数. 因此, 对于这些合数就不能用Fermat 测试来证明它们的合性.
-------------------------------------------------------------------------------------------------------------------
给定奇数 n > 1,
写 n−1=2sd ,
d 奇数.
如果 n 是素数,
那么对于每一个与n 互素的整数 b, 同余式
(2)
bd
≡1
mod n 成立, 或对于某个 r =0,1,…,s−1
有 b ^(d˙2r) ≡−1 mod n..
如果 (2) 对于整数对 (n,
b) 成立, 我们就说 n 通过了关于基 b 的 Miller 测试, 称 n 是 通过基 b 的强概素数 (strong probable prime ), 简记 sprp(b).
它可能是素数也可能是合数, 如果 n是合数, 就称 n是 通过基 b 的强伪素数 (strong
pseudoprime), 简记 spsp(b). 易见, 强概素数是概素数, 强伪素数是伪素数.
-----------------------------------------------------------------------------------------------------
具有形式：
(3) n = pq,
p < q 奇素数且 q−1 = k
(p−1), k 为正整数或正分数, 的数称为 Kk-数. 例如 1891=31 · 61 是 K2-数, 因为 61−1=2 · (31−1).
又如, 77=7· 11 是 K5/3 -数, 因为 11−1= (7−1)
· 5/3.
----------------------------------------------------------------
Carmichal 数 n=q1q2q3 称为 C3-数, 如果 每个素数 qi ≡3
mod 4, i = 1, 2, 3.
例如, 8911 = 7· 19· 67 是 (最小的) C3-数.
Lucas 伪素数和强Lucas 伪素数传统地通过双参数Lucas序列来定义. 令 P 和 Q 是整数, D = P2 − 4Q ≠ 0. Lucas 序列 Ui 和Vi 定义为
(4)
U0 = 0; U1 = 1; V0 =
2; V1 = P; 对于 i ≥ 2: Ui = PUi−1 − QUi−2，Vi = PVi−1 −Q Vi−2.
如果 n 是素数且 gcd(n, 2QD) =1, 则
(5)
Un−(D/n) ≡ 0 mod n; ((D/n) 是 Jacobi 符号)
且
(6) n|Uq 或对于某个i, 0≤i<k 有n|Vq · 2i, 这里 n−(D/n) =2kq ,
q 奇数.
给定正整数 n, 如果有整数对 (P, Q) 使得 (5)成立,就说 n 通过了双参数基 (P, Q) 的 Lucas 测试, 称 n 是 通过双参数基 (P, Q) 的 Lucas 概素数 (Lucas probable prime), 简记 lprp(P, Q).
它可能是素数也可能是合数,如果 n是合数,就称 n 是通过双参数基 (P, Q)的 Lucas 伪素数 (Lucas pseudoprime), 简记 lpsp(P, Q).
给定正整数 n, 如果有整数对 (P, Q) 使得 (6)成立,就说 n 通过了双参数基 (P, Q) 的 强 Lucas 测试,
称 n 是 通过双参数基 (P, Q) 的 强Lucas 概素数 (Lucas probable
prime), 简记
slprp(P, Q).
它可能是素数也可能是合数,如果 n是合数,就称 n 是通过双参数基 (P, Q) 的 强 Lucas 伪素数 (strong Lucas pseudoprime), 简记 slpsp(P, Q).
易见, 强Lucas概素数是Lucas概素数, 强Lucas伪素数是Lucas伪素数.
其它术语、记号，请看英文原文.2020-11-30 2021-12-08