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.

Ký hiệu Legendre và tiêu chuẩn Euler

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 :$\backslash left(\backslash frac\{a\}\{p\}\backslash right)$ là

• 0 nếu p chia hết 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.

Tiêu chuẩn Euler

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

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

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

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^\{\backslash alpha\_1\}p\_2^\{\backslash alpha\_2\}\backslash cdots\; p\_k^\{\backslash alpha\_k\}$ là dạng phân tích tiêu chuẩn của n và số nguyên a bất kỳ, ký hiẹu Jacobi :$\backslash left(\backslash frac\{a\}\{n\}\backslash right)\; =\; \backslash left(\backslash frac\{a\}\{p\_1\}\backslash right)^\{\backslash alpha\_1\}\backslash left(\backslash frac\{a\}\{p\_2\}\backslash right)^\{\backslash alpha\_2\}\backslash cdots\; \backslash left(\backslash frac\{a\}\{p\_k\}\backslash right)^\{\backslash alpha\_k\}$

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 < 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 < _a'' < n) nếu: :$\backslash left(\backslash frac\{a\}\{n\}\backslash right)\; \backslash equiv\; a^\{(n-1)/2\}\backslash pmod\; n$ trong đó $\backslash left(\backslash frac\{a\}\{n\}\backslash right)$ là ký hiệu Jacobi.

Kiểm tra Solovay-Strasen

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=$\backslash left(\backslash frac\{a\}\{n\}\backslash 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.

Xác suất sai

• Định lý: Nếu n là hợp số lẻ thì tồn tại không quá $\backslash frac\; \{\backslash 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) $\backslash le\; \backslash 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à :::P(A|B)=$\backslash frac\; \{P(B|A)$P(A)}{P(B|A)P(A)+P(\overline A)} :::$P(A|B)\backslash approx\; \backslash frac\; \{P(B|A)$(\ln n-2)}{P(B|A)*(\ln n-2)+2} (Tham khảo: Douglas R. Stisnon. Cryptography Theory and Practice.)

Kiểm tra Solovar-Strasen lặp