知识卡片
奇合数至少半数底数为证人
对奇合数n,书中定理指出合数证人至少有(n−1)/2个。
“证人”是能让算法发现费马同余失败或1的非平凡平方根的底数;非证人则暂时没暴露合性。任何非证人都必须与 n 互素,因而落在模 n 可逆群中。
证明再分两种情形:非卡迈克尔数可用满足 x^(n−1)≡1 (mod n) 的可逆元素组成真子群;卡迈克尔情形则根据连平方序列中出现 −1 的最晚位置构造另一个真子群,并用中国剩余定理找到不在其中的可逆元素。两种情形的非证人都被包含在真子群内;有限群的真子群最多占一半,故证人至少占一半。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第31章 数论算法 · 查看原书依据
Theorem 31.39 If n is an odd composite number, then the number of witnesses to the compositeness of n is at least (n – 1)/2. Proof The proof shows that the number of nonwitnesses is at most (n – 1)/2, which implies the theorem. We start by claiming that any nonwitness must be a member of . Why? Consider any nonwitness a. It must satisfy an–1 = 1 (mod n) or, equivalently, a · an−2 = 1 (mod n). Thus the equation ax = 1 (mod n) has a solution, namely an−2. By Corollary 31.21 on page 924, gcd(a, n) | 1, which in turn implies that gcd(a, n) = 1.