知识卡片

普通读书笔记卡 · 3695.a.6.c

奇合数至少半数底数为证人

理解等级:高级

对奇合数n,书中定理指出合数证人至少有(n−1)/2个。

“证人”是能让算法发现费马同余失败或1的非平凡平方根的底数;非证人则暂时没暴露合性。任何非证人都必须与 n 互素,因而落在模 n 可逆群中。

证明再分两种情形:非卡迈克尔数可用满足 x^(n−1)≡1 (mod n) 的可逆元素组成真子群;卡迈克尔情形则根据连平方序列中出现 −1 的最晚位置构造另一个真子群,并用中国剩余定理找到不在其中的可逆元素。两种情形的非证人都被包含在真子群内;有限群的真子群最多占一半,故证人至少占一半。

这张卡片看不懂?

已有反馈 · 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.

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[85000,90000))。 - 结论依据:定理31.39先证明非证人必在 ℤₙ* 中,再分非卡迈克尔与卡迈克尔两种情形,分别把全部非证人包含在 ℤₙ* 的真子群中;由子群阶整除群阶,真子群至多占一半,因而非证人至多(n−1)/2个。 - 原始内容: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 a n –1 = 1 (mod n ) or, equivalently, a · a n −2 = 1 (mod n ). Thus the equation ax = 1 (mod n ) has a solution, namely a n −2 . By Corollary 31.21 on page 924, gcd( a , n ) | 1, which in turn implies that gcd( a , n ) = 1.