Bài giảng Nhập môn Số học thuật toán - Nguyễn Đạt Thông

Dịnh nghĩa

Giả sử n là số nguyên dương lẻ, ta viết n — 1 = 2% với s > 1 và t lẻ.

Ta nói n trải qua được kiểm tra Miller cơ sở b, nếu bl = 1 mod n hoặc b2Jt = — 1 mod n với 0 < j <5 — 1.

■ Nếu n là số nguyên tố thì n trải qua dược kiểm tra Miller với mọi cơ sỏ b không chia hết cho n.

■ Nếu hợp số n trải qua dược kiểm tra Miller cơ sở b thì nó được gọi là số giả nguyên tố mạnh cơ sở b.

■ Tồn tại vô hạn số giả nguyên tố mạnh cơ sở 2.

■ Ví dụ:

■ Số giả nguyên tố mạnh lẻ cơ sỏ 2 bé nhất là 2047.

■ Số giả nguyên tố mạnh lẻ cơ sở 2 và 3 bé nhất là 1373653.

■ Số giả nguyên tố mạnh lẻ cơ sỏ 2, 3 và 5 bé nhất là 25326001.

■ Số giả nguyên tố mạnh lẻ cơ sở 2, 3, 5 và 7 bé nhất là 3215031751.

■ Ta kết luận số n là số nguyên tố nếu nó trải qua được kiểm tra Miller với hơn (n — l)/4 cơ sở.

■ Nếu n là hợp số và số b được chọn ngầu nhiên sao cho

1 < ò < n — 1. thì xác suất để n trải qua được kiểm tra Miller cơ sở b sẽ không quá 1/4.

■ Nếu n là hợp số và k số được chọn ngẫu nhiên trong

{1., n — 1}, thì xác suất để n trải qua được kiểm tra Miller đối với k cơ sở này sẽ không quá 4_fc.

■ Với k đủ lớn (ví dụ k = 20), và n trải qua được kiểm tra Miller đối với k cơ sở ngẫu nhiên, thì ta có thể tin "gần như chắc chắn" n là số nguyên tố.

■