Kiểm tra Solovay-Strassen

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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[sửa | sửa mã nguồn]

Ký hiệu Legendre[sửa | sửa mã nguồn]

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

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

  • 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 k2a (mod p);
  • −1 nếu a không là bình phương đúng modulo p.

Tiêu chuẩn Euler[sửa | sửa mã nguồn]

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

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

Ký hiệu Jacobi[sửa | sửa mã nguồn]

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ủa n 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ố giả nguyên tố Euler[sửa | sửa mã nguồn]

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:
\left(\frac{a}{n}\right) \equiv a^{(n-1)/2}\pmod n

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

Kiểm tra Solovay-Strasen[sửa | sửa mã nguồn]

Solovay-Strasen test[sửa | sửa mã nguồn]

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.

Xác suất sai[sửa | sửa mã nguồn]

  • Đị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.)

Kiểm tra Solovar-Strasen lặp[sửa | sửa mã nguồn]

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]