原书出处
Introduction to Algorithms, Fourth Edition
31 第31章 数论算法
nes 6 or 8 have not returned TRUE. The following lemma proves the correctness of WITNESS.
Lemma 31.38 If WITNESS(a, n) returns TRUE, then a proof that n is composite can be constructed using a as a witness. Proof If WITNESS returns TRUE from line 8, it’s because line 7 determined that xt = an–1 mod n ≠ 1. If n is prime, however, Fermat’s theorem (Theorem 31.31) says that an–1 = 1 (mod n) for all . Since if n is prime, Fermat’s theorem also says that an–1 = 1 (mod n) for all . Therefore, n cannot be prime, and the equation an–1 mod n ≠ 1 proves this fact. If WITNESS returns TRUE from
line 6, then it has discovered that xi–1 is a nontrivial square root of 1, modulo n, sinc
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter031.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea