Tài liệu Xây dựng chương trènh kiểm tra số nguyấn tố bằng thuật toán miller- rabin

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