2
ĐẠI HỌC CÔNG NGHỆ
ĐẠI HỌC QUỐC GIA HÀ NỘI
MẬT MÃ VÀ AN TOÀN DỮ LIỆU
Phương pháp “Xác Suất” kiểm tra số nguyên tố lớn
Thuật toán Soloway-Strassen
Giảng viên: PGS.TS Trịnh Nhật Tiến
Thực hiện: Nguyễn Thị Dung
Hà Nội, 2014
4
Thuật toán Soloway-Strassen
1 Thuật toán Soloway-Strassen
1.1. Modulo số học
Về cơ bản a ≡ b(mod n) nếu a = b+kn trong đó k là một số nguyên. Nếu a và
b dương và a nhỏ hơn n, ta có thể nghĩ rằng a là phần dư của b khi chia cho n. Nói
chung a và b đều là phần dư khi chia cho n. Đôi khi b gọi là thặng dư của a,
modulo n, đôi khi a gọi là đồng dư của b, modulo n. Tập hợp các số nguyên từ 0
đến n-1 còn được gọi là tập hợp thặng dư hoàn toàn modulo n. Điều này có nghĩa
là, với mỗi số nguyên a, thì thặng dư modulo n là một số từ 0 đến n-1.
Modulo số học cũng giống như số học bình thường, bao gồm các phép giao
hoán, kết hợp và phân phối. Mặt khác giảm mỗi giá trị trung gian trong suốt quá
trình tính toán.
(a+b) mod n = ((a mod n) + (b mod n)) mod n
(a-b) mod n = ((a mod n) - (b mod n)) mod n
(a×b) mod n = ((a mod n) × (b mod n)) mod n
(a×(b + c)) mod n = (((a × b) mod n) + ((a × c) mod n)) mod n
Hệ thống mã hoá sự dụng nhiều sự tính toán modulo n, bởi vì vấn đề này
giống như tính toán logarithm rời rạc và diện tích hình vuông là khó khăn. Mặt
khác nó làm việc dễ hơn, bởi vì nó bị giới hạn trong tất cả giá trị trung gian và kết
quả. Ví dụ : a là một số k bits, n là kết quả trung gian của phép cộng, trừ, nhân sẽ
không vượt quá 24 bits. Như vậy chúng ta có thể thực hiện hàm mũ trong modulo



p
a
như sau:
=
Kí hiệu Lagrăng được sử dụng trong tiêu chuẩn Euler do Euler chứng minh:
= a
(p-1)/2
(mod p)
1.4. Ký hiệu Jacobi
Định nghĩa: với n
≥
1 lẻ và mọi số nguyên a
≥
0. Giả sử n có triển khai chính tắc
thành thừa số nguyên tố là n = p
1
e1
p
2
e2
p
3
e3
… p
k
ek
, thì ký hiệu Jacobi được định
nghĩa như sau:



n
a
mà không cần phải phân tích n thành thừa số nguyên tố:
BigInteger jacobi(BigInteger a, BigInteger b)
{
if (a == 0) return 0;
if (a == 1) return 1;
if (a == 2)
{
BigInteger b8 = b % 8;
if (b8 == 3 || b8 == 5) return -1;
else return 1;
}
if ((a % 2) == 0) return jacobi(2, b) * jacobi(a / 2, b);
if (a >= b) return jacobi(a % b, b);
if ((a % 4) == 3 && (b % 4) == 3) return -jacobi(b, a);
else return jacobi(b, a);
}
7
1.5. Thuật toán Soloway-Strassen
INPUT: n là một số tự nhiên lẻ
OUTPUT: FALSE nếu n là hợp số
TRUE nếu n không phải hợp số
int SolowayStrassen(BigInteger n, int k)
{
if (n % 2 == 0) return 0;
int i = 0;
do

n). Các toán
tử so sánh có thời gian chạy coi như không đáng kể, vì vậy độ phức tạp thời gian
của thuật toán euler-witness là O(log
2
n). Kiểm tra Solovay-Strassen thực hiện
thuật toán k lần nên có thời gian thực hiện là O(k. log
2
n).
Với thuật toán Solovay-Strassen, chúng ta có (1/2)
k
khả năng phân loại sai
cho thời gian thực hiện O(k. log
2
n).
8
1.6. Xác suất sai
Định lý: Nếu n là hợp số lẻ thì tồn tại không quá 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.
Định lý: nếu n là hợp số dương lẻ thì trong các số a {2, ,n-1} tồn tại
không quá (n-1)/4 cơ sở a để n là số giả nguyên tố mạnh Fermat.
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 Soloway-
Strassen trả lời TRUE".
Xác suất điều kiện P(B|A) .
Theo định lý trên nếu n là hợp số thì khả năng kiểm tra này trả lời TRUE
xảy ra với xác suất không vượt quá , nghĩa là P(B|A) . Tuy nhiên để tính xác suất
sai của kiểm tra Soloway-Strassen cần tính xác suất diều kiện P(A|B). Dựa trên
định lý về ước lượng số các số nguyên tố ta đưa ra ước lượng
P(A) 1-
Theo định lý Bayes trong lý thuyết xác suất ta có công thức để tính xác suất
sai của kiểm tra Soloway-Strassen là:

tố.
Với n lẻ và là hợp số, ít nhất, một nửa các số a (a thỏa mãn gcd(a,n) = 1) là
bằng chứng Euler. Chúng ta có thể chứng minh điều này như sau: cho {a
1
, a
2
, …,
a
m
} là các giả mạo Euler và a là một bằng chứng Euler. Thì với i = 1, 2, …, m:
(a.a
i
)
(n-1)/2
= a
(n-1)/2
. a
i
(n-1)/2
= a
(n-1)/2
. (mod n).
Vì = , nên (a.a
i
)
(n-1)/2
(mod n).
Như vậy mỗi số a
i
cho một a.a

8145716547254754712572451785471634735472
5472645763471841746173647135473547153747
1354716354754754716761741355509
This is Prime number
F2fafadfa3 Not is number
11