← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

31 第31章 数论算法

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.762Z

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