← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3695.a.2

非平凡平方根证明模数合数

理解等级:中级

若x²≡1(mod n),而x既不等于1也不等于−1(mod n),则x是1的非平凡平方根,足以证明n为合数。

此判据是素性检测的合数证据;没有找到这种根不等于已证明n为素数。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Corollary 31.35 If there exists a nontrivial square root of 1, modulo n, then n is composite. Proof By the contrapositive of Theorem 31.34, if there exists a nontrivial square root of 1, modulo n, then n cannot be an odd prime or a power of an odd prime. Nor can n be 2, because if x2 = 1 (mod 2), then x = 1 (mod 2), and

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[50000,55000))。 - 结论依据:原文对中国剩余定理、模幂性质或重复平方法给出定理与算法;公式图已核对。 - 原始内容:Corollary 31.35 If there exists a nontrivial square root of 1, modulo n , then n is composite. Proof By the contrapositive of Theorem 31.34, if there exists a nontrivial square root of 1, modulo n , then n cannot be an odd prime or a power of an odd prime. Nor can n be 2, because if x 2 = 1 (mod 2), then x = 1 (mod 2), and