Website: http://www.docs.vn Email :
[email protected] 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
2
3
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
4
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:
5
Begin
+ n : số lớn cần kiểm tra
+ t : số lần kiểm tra
n – 1 = 2k * m;
a = Random();
b = am mod n;
i =0
i 3, và một tham số an toàn t
(là số lần thực hiện kiểm tra n )
b.Đầu ra : Trả lời câu hỏi n có là số nguyên tố không ?Câu trả
lời là “prime” nếu là số nguyên tố ngƣợc lại là “composite”
c.Thuật toán:
6
Bƣớc 1: Thực hiện tính n -1 = 2k.m. Trong đó:
n : số cần kiểm tra
s : số nguyên
m : số nguyên lẻ.
Bƣớc 2: Chọn số ngẫu nhiên a. Với 1 < a < n-1.
Bƣớc 3: Tính b ≡ am mod n
If( b ≡ 1 mod n) then return “prime”;
Else
for( I =1 ; i
#include
#define NN_SIZE 32
#define NN_SIZE2 16
NN_DIGIT one[NN_SIZE];
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
void bigNumber::Encode(UINT1 *a, UINT2 len, NN_DIGIT
*b, UINT2 digits)
12
{
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 (MAX_NN_DIGIT - *c))
borrow = 1;
else
borrow = 0;
c++;
}
*a++ = temp;
}while(--digits);
return(borrow);
}
17
void bigNumber::AssignZero(NN_DIGIT *a, UINT2 digits)
{
if(digits) {
do {
*a++ = 0;
}while(--digits);
}
}
void bigNumber::Rand(NN_DIGIT *a, NN_DIGIT digits)
{
NN_DIGIT i,t;
for (i=0;i *(b+digits))
return(1);
if(*(a+digits) < *(b+digits))
return(-1);
}while(digits);
}
return (0);
}
19
void bigNumber::ModExp(NN_DIGIT *a, NN_DIGIT *b,
NN_DIGIT *c, UINT2 cDigits, NN_DIGIT *d, UINT2
dDigits)
{
NN_DIGIT bPower[3][MAX_NN_DIGITS], ci,
t[MAX_NN_DIGITS];
int i;
UINT2 ciBits, j, s;
/* Store b, b^2 mod d, and b^3 mod d.
*/
Assign (bPower[0], b, dDigits);
ModMult (bPower[1], bPower[0], b, d, dDigits);
ModMult (bPower[2], bPower[1], b, d, dDigits);
NN_ASSIGN_DIGIT (t, 1, dDigits);
cDigits = NN_Digits (c, cDigits);
20