原书出处
Introduction to Algorithms, Fourth Edition
31 第31章 数论算法
umber, say a = 3. Better yet, you could check equation (31.39) for even more values of a.
Unfortunately, even checking for several values of a does not eliminate all errors, because there exist composite integers n, known as Carmichael numbers, that satisfy equation (31.39) for all . (The equation does fail when gcd(a, n) > 1—that is, when —but demonstrating that n is composite by finding such an a can be difficult if n has only large prime factors.) The first three Carmichael numbers are 561, 1105, and 1729.
Carmichael numbers are extremely rare. For example, only 255 of them are less than 100,00
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter031.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea