Kiểm tra Solovay-Strassen

Bách khoa toàn thư mở Wikipedia

Kiểm tra Solovay-Strassen là một trong các phương pháp kiểm tra tính nguyên tố theo xác suất do Robert M. Solovay và Volker Strassen phát triển.

Mục lục

1 Ký hiệu Legendre và tiêu chuẩn Euler
- 1.1 Ký hiệu Legendre
- 1.2 Tiêu chuẩn Euler
2 Ký hiệu Jacobi và số giả nguyên tố Euler
- 2.1 Ký hiệu Jacobi
- 2.2 Số giả nguyên tố Euler
3 Kiểm tra Solovay-Strasen
- 3.1 Solovay-Strasen test
- 3.2 Xác suất sai
4 Kiểm tra Solovar-Strasen lặp
5 Xem thêm

[sửa] Ký hiệu Legendre và tiêu chuẩn Euler

[sửa] Ký hiệu Legendre

Legendre đưa ra ký hiệu mang tên ông cho số nguyên tố lẻ p và số nguyên a

$\left(\frac{a}{p}\right)$

là

0 nếu p chia hết cho a;
1 nếu a là một bình phương đúng modulo p — nghĩa là nếu tồn tại số nguyên k sao cho k² ≡ a (mod p);
−1 nếu a không là bình phương đúng modulo p.

[sửa] Tiêu chuẩn Euler

Euler chứng minh rằng với mọi số nguyên tố p và số a, $1 \le a < p$ ,

$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}\pmod p$

[sửa] Ký hiệu Jacobi và số giả nguyên tố Euler

[sửa] Ký hiệu Jacobi

Ký hiệu Jacobi là mở rộng của Ký hiệu Legendre cho số tự nhiên lẻ n. Giả sử

$p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$

là dạng phân tích tiêu chuẩn củan và số nguyên a bất kỳ, ký hiẹu Jacobi

$\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{\alpha_1}\left(\frac{a}{p_2}\right)^{\alpha_2}\cdots \left(\frac{a}{p_k}\right)^{\alpha_k}$

[sửa] Số giả nguyên tố Euler

Xem tiêu chuẩn Euler là mệnh đề Q(p,a). Khi đó Q(p,a) đúng với mọi số nguyên tố p và mọi số tự nhiên a, $1 \le a < p$ . Thay số nguyên tố p bằng số lẻ n và ký hiệu Legendre bằng ký hiệu Jacobi, ta định nghĩa:

Đinh nghĩa: Hợp số n được gọi là số giả nguyên tố Euler cơ sở a( $1 \le a < p$ ) nếu:

$\left(\frac{a}{n}\right) \equiv a^{(n-1)/2}\pmod n$

trong đó $\left(\frac{a}{n}\right)$ là ký hiệu Jacobi.

[sửa] Kiểm tra Solovay-Strasen

[sửa] Solovay-Strasen test

INPUTS: n: là số tự nhiên lẻ

OUTPUT: FALSE nếu n là hợp số, nếu không TRUE

Chọn a ngẫu nhiên trong khoảng[1,n-1]
Tính ký hiệu Jacobi J= $\left(\frac{a}{n}\right)$
Tính x = $a (n - 1) / 2 (mod n)$
Nếu J ≠ x thì trả về FALSE

nếu khác trả về TRUE.

[sửa] Xác suất sai

Định lý: Nếu n là hợp số lẻ thì tồn tại không quá $\frac {\phi n} 2$ số tự nhiên dương a nhỏ hơn n, nguyên tố cùng nhau với n sao cho n là số giả nguyên tố Euler cơ sở a.
Gọi A là biến cố "Số nguyên lẻ n là hợp số"; B là biến cố: "Thuật toán Solova-Strassen trả lời TRUE".
Xác suất điều kiện P(B|A) $\le \frac 1 2$ .
Tương tự phép thử Miller-Rabin tính được xác suất sai của phép thử Solova-Strasen là