Website: Email : Tel (: 0918.775.368
XÂY DỰNG CHƯƠNG TRÌNH KIỂM
TRA SỐ NGUYÊN TỐ BẰNG THUẬT
TOÁN MILLER- RABIN
MỤC LỤC
CHƯƠNG 1: CƠ SỞ THUẬT TOÁN
CHƯƠNG 2: PHÂN TÍCH VÀ THIẾT KẾ
CHƯƠNG 3: CÀI ĐẶT VÀ KIỂM THỬ
PHỤ LỤC
1
Chương 1
CƠ SỞ THUẬT TOÁN
1.Giới thiệu
Bài toán kiểm tra số nguyên tố là một trong những bài toán cơ bản nhưng hết sức quan
trong trọng lĩnh vực an toàn và bảo mật thông tin cụ thể là trong hệ mật RSA.Có rất nhiều
phương pháp kiểm tra số nguyên tố như : phương pháp chứng minh theo định lý Fecma,
phương pháp sàng số nguyên tố Eratosthenes, phương pháp kiểm tra theo xác suất. Thuật
toán Miller- Rabin là thuật toán dựa trên phương pháp chứng minh theo xác suất.Thuật
toán này được thao tác trên số lớn.
2.Cơ sở thuật toán Miller-Rabin
Thuật toán này dựa trên một định lý quan trong sau:
”Nếu n là số nguyên tố thì (n-1 )!≡ (n-1) mod n”.
“Với mỗi số nguyên n, Ф(n) là số các số nguyên tố cùng nhau với n mà nhỏ hơn n. Khi đó, với
mọi x, x > 0, x
Ф(n)
≡ 1 mod n ”.
3.Thuật toán
Sơ đồ thuật toán:
2
Thuật toán:
a.Đầu vào : Là một số nguyên n > 3, và một tham số an toàn t (là số lần thực hiện kiểm tra n )

b ≡1 mod n
n : prime
b = b
2
mod n;
i = i+1;
i = 0
i <
k
b≡-1 mod n
End.
3
Chương 2
PHÂN TÍCH VÀ THIẾT KẾ
1.Công cụ
Chương trình được xây dựng sử dụng VisualC++6.0.
2.Thiết kế
Chương trình được thiết kế theo lớp tên là : bigNumber.Bao gồm các thuộc tính và
phương thức sau(hình vẽ):
a.Thuộc tinh:
+ great: là một mảng dữ liệu kiểu NN_DIGIT để biểu diễn số lớn.
+ one : là một mảng dữ liệu kiểu NN_DIGIT để biểu diễn số lớn dùng thao tác trung
gian
b.Phương thức:
+ void Div (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c,UINT2 cDigits, NN_DIGIT
*d,UINT2 dDigits);
Thực hiện phép chia a = c div d and b = c mod d.
+ NN_DIGIT LShift (NN_DIGIT *a, NN_DIGIT *b, UINT2 c,UINT2 digits);
Thực hiện a = b*2^c
+ NN_DIGIT RShift (NN_DIGIT *a, NN_DIGIT *b, UINT2 c,UINT2 digits);

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
void bigNumber::Encode(UINT1 *a, UINT2 len, NN_DIGIT *b, UINT2 digits)
5
{
NN_DIGIT t;
UINT2 i, j, u;
/* @##$ unsigned/signed bug fix added JSAK - Fri 31/05/96 18:09:11 */
for (i = 0, j = 0; i < digits && j < len; i++) {
t = b[i];
for (u = 0; j < len && u < NN_DIGIT_BITS; j++, u += 8)
a[j] = (UINT1)(t >> u);
}
for (; j <len ; j++)
a[j] = 0;
}
void bigNumber::Decode(NN_DIGIT *a, UINT2 digits, UINT1 *b, UINT2 len)
{
NN_DIGIT t;
UINT2 i, j, u;
/* @##$ unsigned/signed bug fix added JSAK - Fri 31/05/96 18:09:11 */
for (i = 0, j = 0; i < digits && j < len ; i++) {
t = 0;
for (u = 0; j <len && u < NN_DIGIT_BITS; j++, u += 8)
t |= ((NN_DIGIT)b[j]) << u;
a[i] = t;
}
for (; i < digits; i++)
a[i] = 0;