知识卡片

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

米勒拉宾随机抽底并查平方根

理解等级:中级

米勒拉宾对多个随机底数运行证人检测,除检查a^{n−1}是否为1,还在连平方过程中寻找1的非平凡平方根。

任一检查发现证据即判合数;多次没有发现证据只提高素数判断置信度。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      randomly chosen base values a instead of just one base value. While computing each modular exponentiation, it looks for a nontrivial square root of 1, modulo n, during the final set of squarings. If it finds one, it stops and returns COMPOSITE. Corollary 31.35 from Section 31.6 justifies detecting composites in this manner. The pseudocode for the Miller-Rabin primality test appears in the procedures MILLER-RABIN and W

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[80000,85000))。 - 结论依据:原书第31.8节的素性判定方法、证人伪代码或定理;相关公式图已核对。 - 原始内容:randomly chosen base values a instead of just one base value. While computing each modular exponentiation, it looks for a nontrivial square root of 1, modulo n , during the final set of squarings. If it finds one, it stops and returns COMPOSITE . Corollary 31.35 from Section 31.6 justifies detecting composites in this manner. The pseudocode for the Miller-Rabin primality test appears in the procedures M ILLER -R ABIN and W