知识卡片

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

CRT构造真子群外证人

理解等级:高级

在定理31.39的卡迈克尔分支,写 n−1=2^t·u,其中 u 为奇数。若 v 与 n 互素,且 v^(2^j·u)≡−1 (mod n),就称 (v,j) 可接受。选所有可接受对中最大的 j,并定义

B={x∈ℤ_n* : x^(2^j·u)≡±1 (mod n)}

非证人的连平方序列要么全为1,要么至迟在第j位出现−1,所以全部非证人都在B中。再取非平凡互素分解n=n₁·n₂,其中n₁,n₂>1,用CRT构造w≡v (mod n₁)、w≡1 (mod n₂)。于是w^(2ʲ·u)在两个模下分别为−1与1;因两模数都大于1,这两个剩余类不同,不可能在模n下等于统一的±1,故w∉B。因而B是包含所有非证人的真子群,规模最多占ℤₙ*的一半。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第31章 数论算法 · 查看原书依据

      We now use the existence of v to demonstrate that there exists a , and hence that B is a proper subgroup of . Since , we also have by Corollary 31.29 to the Chinese remainder theorem. By Corollary 31.28, there exists a w simultaneously satisfying the equations w = v (mod n1), w = 1 (mod n2). Therefore, Corollary 31.29 gives that implies and also that implies . Hence, we conclude that , and so w ∉ B. It remains to show that . We start by working separately

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[90000,95000))。 - 结论依据:Art_P1256 将 B 定义为可逆类中满足 x^{2ʲu}≡±1 (mod n) 的子群,原文证明非证人均在 B。Art_P1259–P1261 与 CRT 给出 w^{2ʲu}≡−1 (mod n₁)、w^{2ʲu}≡1 (mod n₂);Art_P1266–P1268 说明 w^{2ʲu}≢±1 (mod n),且 w 仍可逆。因此 w∉B,B 为真子群;|B| 整除 |ℤₙ*|,所以至多占一半。 - 原始内容:We now use the existence of v to demonstrate that there exists a , and hence that B is a proper subgroup of . Since , we also have by Corollary 31.29 to the Chinese remainder theorem. By Corollary 31.28, there exists a w simultaneously satisfying the equations w = v (mod n 1 ), w = 1 (mod n 2 ). Therefore, Corollary 31.29 gives that implies and also that implies . Hence, we conclude that , and so w ∉ B . It remains to show that . We start by working separately