← 返回起始笔记位置

知识卡片

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

费马伪素数检测只给单侧保证

理解等级:中级

对奇数n检验2^{n−1} mod n:

  • 结果不为1即可断定n合数;
  • 等于1只说明n通过基数2的费马检验,仍可能是伪素数。

不能把程序返回的PRIME当成确定性素数证明。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      This procedure can make errors, but only of one type. That is, if it says that n is composite, then it is always correct. If it says that n is prime, however, then it makes an error only if n is a base-2 pseudoprime. How often does PSEUDOPRIME err? Surprisingly rarely. There are only 22 values of n less than 10,000 for which it errs, the first four of which are 341, 561, 645, P

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[75000,80000))。 - 结论依据:原书第31.8节的素性判定方法、证人伪代码或定理;相关公式图已核对。 - 原始内容:This procedure can make errors, but only of one type. That is, if it says that n is composite, then it is always correct. If it says that n is prime, however, then it makes an error only if n is a base-2 pseudoprime. How often does P SEUDOPRIME err? Surprisingly rarely. There are only 22 values of n less than 10,000 for which it errs, the first four of which are 341, 561, 645, P