信息安全数学基础 第六次作业
by 18340087 李晨曦
(3)
我们有
3
90
≡ 1 (mod 91)
但是
91 = 7 × 13
是一个合数。所以91是基3的伪素数
(6)
由于课上没有介绍， 我们这里首先证明一下Korselt定理：
定理 1. 一个合数是Carmichael 数， 当且仅当对其每一个素因子p都有：
1. p
2
- n
2. p − 1|n − 1
证明.
充分性：
如果一个合数n是Carmichael数， 那么， 对任意与n互素的b， 都有：
b
n−1
≡ 1 (mod n)
将n分解为
p
1
k
1
: : :p
i
k
i
: : :p
t
k
t
我们有：
b
n− 1
≡ 1 (mod p
i
k
i
)
所以
Ord
p
i
k
i
(b)|n − 1
由原根的存在性， 对任意的i存在一个p
i
k
i
与互素的b
i
， 使得b
i
是模p
i
k
i
的原根。
任取b
1
: : :b
j
: : :b
n
(j =/ i)， 使得b
j
与p
i
k
i
互素， 那么，
b ≡ b
1
(mod p
1
k
1
)
: : :
b ≡ b
i
(mod p
i
k
i
)
: : :
b ≡ b
n
(mod p
t
k
t
)
1
评论0