原书出处
Introduction to Algorithms, Fourth Edition
31 第31章 数论算法
rstand how WITNESS works, and then we’ll see how the Miller-Rabin primality test uses it.
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
) 1 let t and u be such that t ≥ 1, u is odd, and n – 1 = 2tu 2 x0 = MODULAR-EXPONENTIATIO
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter031.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea