知识卡片

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

证人检测分解奇数部分再连平方

理解等级:中级

将奇数n的n−1写为2^t·u(u为奇数),先算x₀=a^u mod n,再连平方t次得到x_t=a^{n−1} mod n。

每次由非±1值平方得到1都提供合数证据。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Let n – 1 = 2tu where t ≥ 1 and u is odd. That is, the binary representation of n – 1 is the binary representation of the odd integer u followed by exactly t zeros. Therefore, , so that one way to compute an−1 mod n is to first compute au mod n and then square the result t times successively. MILLER-RABIN(n, s) // n > 2 is odd 1 for j = 1 to s 2 a = RANDOM(2, n – 2) 3 if WITNESS(a, n) 4 return COMPOSITE // definitely 5 return PRIME // almost surely WITNESS(a, n

    参考来源

    - 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[80000,85000))。 - 结论依据:原书第31.8节的素性判定方法、证人伪代码或定理;相关公式图已核对。 - 原始内容:Let n – 1 = 2 t u where t ≥ 1 and u is odd. That is, the binary representation of n – 1 is the binary representation of the odd integer u followed by exactly t zeros. Therefore, , so that one way to compute a n −1 mod n is to first compute a u mod n and then square the result t times successively. M ILLER -R ABIN ( n , s ) // n > 2 is odd 1 for j = 1 to s 2 a = R ANDOM (2, n – 2) 3 if W ITNESS ( a , n ) 4 return COMPOSITE // definitely 5 return PRIME // almost surely W ITNESS ( a , n