知识卡片
证人检测分解奇数部分再连平方
将奇数n的n−1写为2^t·u(u为奇数),先算x₀=a^u mod n,再连平方t次得到x_t=a^{n−1} mod n。
每次由非±1值平方得到1都提供合数证据。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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