← 返回起始笔记位置

知识卡片

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

证人返回真必能证明合数

理解等级:中级

证人过程返回真有两种依据:

  • 末值a^{n−1} mod n不为1,违反素数的费马性质;
  • 或中途发现模n下1的非平凡平方根。

两者都证明n合数,所以合数判定没有假阳性。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Lemma 31.38 If WITNESS(a, n) returns TRUE, then a proof that n is composite can be constructed using a as a witness. Proof If WITNESS returns TRUE from line 8, it’s because line 7 determined that xt = an–1 mod n ≠ 1. If n is prime, however, Fermat’s theorem (Theorem 31.31) says that an–1 = 1 (mod n) for all . Since if n is prime, Fermat’s theorem also says that an–1 = 1 (mod n) for all . Therefore, n cannot be prime, and the equation an–1 mod n ≠ 1 proves this fact. If WITNESS returns TRUE from

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[80000,85000))。 - 结论依据:原书第31.8节的素性判定方法、证人伪代码或定理;相关公式图已核对。 - 原始内容:Lemma 31.38 If W ITNESS ( a , n ) returns TRUE , then a proof that n is composite can be constructed using a as a witness. Proof If W ITNESS returns TRUE from line 8, it’s because line 7 determined that x t = a n –1 mod n ≠ 1. If n is prime, however, Fermat’s theorem (Theorem 31.31) says that a n –1 = 1 (mod n ) for all . Since if n is prime, Fermat’s theorem also says that a n –1 = 1 (mod n ) for all . Therefore, n cannot be prime, and the equation a n –1 mod n ≠ 1 proves this fact. If W ITNESS returns TRUE from