← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

31 第31章 数论算法

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

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