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

[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)

  • 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 k2a (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
  1. Chọn a ngẫu nhiên trong khoảng[1,n-1]
  2. Tính ký hiệu Jacobi J=\left(\frac{a}{n}\right)
  3. Tính x =a(n − 1) / 2(mod n)
  4. Nếu Jx 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à
P(A|B)=\frac {P(B|A)*P(A)}{P(B|A)P(A)+P(\overline A)}
P(A|B)\approx \frac {P(B|A)*(\ln n-2)}{P(B|A)*(\ln n-2)+2}

(Tham khảo: Douglas R. Stisnon. Cryptography Theory and Practice.)

[sửa] Kiểm tra Solovar-Strasen lặp

[sửa] Xem thêm