知识卡片
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 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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