Xây dựng chương trình kiểm tra số nguyên tố bằng thuật toán MILLER - RABIN

g 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: 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; b ≡1 mod n n : prime b = b2 mod n; i = i+1; i = 0 i < k b≡-1 mod n End. 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.Đầ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: 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<k ; i++) if( b≡-1 mod n ) then return “prime”; return “composite” An toàn và bảo mật thông tin trong lĩnh vực công nghệ thông tin ngày càng trở nên quan trọng và cần thiết 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); Thực hiện a = b/2^c + void Modul (NN_DIGIT *a, NN_DIGIT *b, UINT2 bDigits, NN_DIGIT *c,UINT2 cDigits); Thực hiện a = b mod c + void Multiply (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c,UINT2 digits) Thực hiện a = b*c + void ModMult (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c,NN_DIGIT *d,UINT2 digits); Thực hiện a = b * c mod d. + void ModExp (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c,UINT2 cDigits, NN_DIGIT *d,UINT2 dDigits) Thực hiện a = b^c mod d. + int Compare (NN_DIGIT *a, NN_DIGIT *b,UINT2 digits); Thực hiện so sánh a, và b + NN_DIGIT Sub (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c,UINT2 digits); Thực hiện a = b - c + NN_DIGIT Add (NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, UINT2 digits); Thực hiện a = b + c. Chương 3 CÀI ĐẶT VÀ KIỂM THỬ 1.Mã chương trình : // bigNumber.cpp: implementation of the bigNumber class. // ////////////////////////////////////////////////////////////////////// #include "bigNumber.h" #include "stdlib.h" #include #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) { 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; } NN_DIGIT bigNumber::Add(NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, UINT2 digits) { NN_DIGIT temp, carry = 0; if(digits) do { if((temp = (*b++) + carry) < carry) temp = *c++; else { /* Patch to prevent bug for Sun CC */ if((temp += *c) < *c) carry = 1; else carry = 0; c++; } *a++ = temp; }while(--digits); return (carry); } NN_DIGIT bigNumber::Sub(NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, UINT2 digits) { NN_DIGIT temp, borrow = 0; if(digits) do { /* Bug fix 16/10/95 - JSK, code below removed, caused bug with Sun Compiler SC4. if((temp = (*b++) - borrow) == MAX_NN_DIGIT) temp = MAX_NN_DIGIT - *c++; */ temp = *b - borrow; b++; if(temp == MAX_NN_DIGIT) { temp = MAX_NN_DIGIT - *c; c++; }else { /* Patch to prevent bug for Sun CC */ if((temp -= *c) > (MAX_NN_DIGIT - *c)) borrow = 1; else borrow = 0; c++; } *a++ = temp; }while(--digits); return(borrow); } 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<digits;i++) { /* Sinh p ngau nhien */ t= rand(); t = (t<<16) ^ (UINT4)rand(); a[i] = t; } } int bigNumber::Compare(NN_DIGIT *a, NN_DIGIT *b, UINT2 digits) { if(digits) { do { digits--; if(*(a+digits) > *(b+digits)) return(1); if(*(a+digits) < *(b+digits)) return(-1); }while(digits); } return (0); } 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); for (i = cDigits - 1; i >= 0; i--) { ci = c[i]; ciBits = NN_DIGIT_BITS; /* Scan past leading zero bits of most significant digit. */ if (i == (int)(cDigits - 1)) { while (! DIGIT_2MSB (ci)) { ci <<= 2; ciBits -= 2; } } for (j = 0; j < ciBits; j += 2, ci <<= 2) { /* Compute t = t^4 * b^s mod d, where s = two MSB's of ci. */ ModMult (t, t, t, d, dDigits); ModMult (t, t, t, d, dDigits); if ((s = DIGIT_2MSB (ci)) != 0) ModMult (t, t, bPower[s-1], d, dDigits); } } Assign (a, t, dDigits); } void bigNumber::Assign(NN_DIGIT *a, NN_DIGIT *b, UINT2 digits) { if(digits) { do { *a++ = *b++; }while(--digits); } } void bigNumber::ModMult(NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, NN_DIGIT *d, UINT2 digits) { NN_DIGIT t[2*MAX_NN_DIGITS]; Multiply (t, b, c, digits); Modul (a, t, (UINT2)(2 * digits), d, digits); } void bigNumber::Multiply(NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, UINT2 digits) { NN_DIGIT t[2*MAX_NN_DIGITS]; NN_DIGIT dhigh, dlow, carry; UINT2 bDigits, cDigits, i, j; AssignZero ((UINT4*)t, (UINT2)(2 * digits)); bDigits = NN_Digits (b, digits); cDigits = NN_Digits (c, digits); for (i = 0; i < bDigits; i++) { carry = 0; if(*(b+i) != 0) { for(j = 0; j < cDigits; j++) { dmult(*(b+i), *(c+j), &dhigh, &dlow); if((*(t+(i+j)) = *(t+(i+j)) + carry) < carry) carry = 1; else carry = 0; if((*(t+(i+j)) += dlow) < dlow) carry++; carry += dhigh; } } *(t+(i+cDigits)) += carry; } Assign(a, t, (UINT2)(2 * digits)); } void bigNumber::Modul(NN_DIGIT *a, NN_DIGIT *b, UINT2 bDigits, NN_DIGIT *c, UINT2 cDigits) { NN_DIGIT t[2 * MAX_NN_DIGITS]; Div (t, a, b, bDigits, c, cDigits); } void bigNumber::dmult(NN_DIGIT a, NN_DIGIT b, NN_DIGIT *high, NN_DIGIT *low) { NN_HALF_DIGIT al, ah, bl, bh; NN_DIGIT m1, m2, m, ml, mh, carry = 0; al = (NN_HALF_DIGIT)LOW_HALF(a); ah = (NN_HALF_DIGIT)HIGH_HALF(a); bl = (NN_HALF_DIGIT)LOW_HALF(b); bh = (NN_HALF_DIGIT)HIGH_HALF(b); *low = (NN_DIGIT) al*bl; *high = (NN_DIGIT) ah*bh; m1 = (NN_DIGIT) al*bh; m2 = (NN_DIGIT) ah*bl; m = m1 + m2; if(m < m1) carry = 1L << (NN_DIGIT_BITS / 2); ml = (m & MAX_NN_HALF_DIGIT) << (NN_DIGIT_BITS / 2); mh = m >> (NN_DIGIT_BITS / 2); *low += ml; if(*low < ml) carry++; *high += carry + mh; } NN_DIGIT bigNumber::RShift(NN_DIGIT *a, NN_DIGIT *b, UINT2 c, UINT2 digits) { NN_DIGIT temp, carry = 0; UINT2 t; if(c < NN_DIGIT_BITS) if(digits) { t = NN_DIGIT_BITS - c; do { digits--; temp = *(b+digits); *(a+digits) = (temp >> c) | carry; carry = c ? (temp << t) : 0; }while(digits); } return (carry); } NN_DIGIT bigNumber::LShift(NN_DIGIT *a, NN_DIGIT *b, UINT2 c, UINT2 digits) { NN_DIGIT temp, carry = 0; UINT2 t; if(c < NN_DIGIT_BITS) if(digits) { t = NN_DIGIT_BITS - c; do { temp = *b++; *a++ = (temp << c) | carry; carry = c ? (temp >> t) : 0; }while(--digits); } return (carry); } NN_DIGIT bigNumber::subdigitmult(NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT c, NN_DIGIT *d, unsigned int digits) { NN_DIGIT borrow, thigh, tlow; UINT2 i; borrow = 0; if(c != 0) { for(i = 0; i < digits; i++) { dmult(c, d[i], &thigh, &tlow); if((a[i] = b[i] - borrow) > (MAX_NN_DIGIT - borrow)) borrow = 1; else borrow = 0; if((a[i] -= tlow) > (MAX_NN_DIGIT - tlow)) borrow++; borrow += thigh; } } return (borrow); } UINT2 bigNumber::NN_Digits(NN_DIGIT *a, UINT2 digits) { if(digits) { digits--; do { if(*(a+digits)) break; }while(digits--); return(digits + 1); } return(digits); } void bigNumber::Div(NN_DIGIT *a, NN_DIGIT *b, NN_DIGIT *c, UINT2 cDigits, NN_DIGIT *d, UINT2 dDigits) { NN_DIGIT ai, cc[2*MAX_NN_DIGITS+1], dd[MAX_NN_DIGITS], s; NN_DIGIT t[2], u, v, *ccptr; NN_HALF_DIGIT aHigh, aLow, cHigh, cLow; int i; UINT2 ddDigits, shift; ddDigits = NN_Digits (d, dDigits); if(ddDigits == 0) return; shift = NN_DIGIT_BITS - NN_DigitBits (d[ddDigits-1]); AssignZero (cc, ddDigits); cc[cDigits] = LShift (cc, c, shift, cDigits); LShift (dd, d, shift, ddDigits); s = dd[ddDigits-1]; AssignZero (a, cDigits); for (i = cDigits-ddDigits; i >= 0; i--) { if (s == MAX_NN_DIGIT) ai = cc[i+ddDigits]; else { ccptr = &cc[i+ddDigits-1]; s++; cHigh = (NN_HALF_DIGIT)HIGH_HALF (s); cLow = (NN_HALF_DIGIT)LOW_HALF (s); *t = *ccptr; *(t+1) = *(ccptr+1); if (cHigh == MAX_NN_HALF_DIGIT) aHigh = (NN_HALF_DIGIT)HIGH_HALF (*(t+1)); else aHigh = (NN_HALF_DIGIT)(*(t+1) / (cHigh + 1)); u = (NN_DIGIT)aHigh * (NN_DIGIT)cLow; v = (NN_DIGIT)aHigh * (NN_DIGIT)cHigh; if ((*t -= TO_HIGH_HALF (u)) > (MAX_NN_DIGIT - TO_HIGH_HALF (u))) t[1]--; *(t+1) -= HIGH_HALF (u); *(t+1) -= v; while ((*(t+1) > cHigh) || ((*(t+1) == cHigh) && (*t >= TO_HIGH_HALF (cLow)))) { if ((*t -= TO_HIGH_HALF (cLow)) > MAX_NN_DIGIT - TO_HIGH_HALF (cLow)) t[1]--; *(t+1) -= cHigh; aHigh++; } if (cHigh == MAX_NN_HALF_DIGIT) aLow = (NN_HALF_DIGIT)LOW_HALF (*(t+1)); else aLow = (NN_HALF_DIGIT)((TO_HIGH_HALF (*(t+1)) + HIGH_HALF (*t)) / (cHigh + 1)); u = (NN_DIGIT)aLow * (NN_DIGIT)cLow; v = (NN_DIGIT)aLow * (NN_DIGIT)cHigh; if ((*t -= u) > (MAX_NN_DIGIT - u)) t[1]--; if ((*t -= TO_HIGH_HALF (v)) > (MAX_NN_DIGIT - TO_HIGH_HALF (v))) t[1]--; *(t+1) -= HIGH_HALF (v); while ((*(t+1) > 0) || ((*(t+1) == 0) && *t >= s)) { if ((*t -= s) > (MAX_NN_DIGIT - s)) t[1]--; aLow++; } ai = TO_HIGH_HALF (aHigh) + aLow; s--; } cc[i+ddDigits] -= subdigitmult(&cc[i], &cc[i], ai, dd, ddDigits); while (cc[i+ddDigits] || (Compare (&cc[i], dd, ddDigits) >= 0)) { ai++; cc[i+ddDigits] -= Sub (&cc[i], &cc[i], dd, ddDigits); } a[i] = ai; } AssignZero (b, dDigits); RShift (b, cc, shift, ddDigits); } UINT2 bigNumber::NN_DigitBits(NN_DIGIT a) { UINT2 i; for (i = 0; i >= 1) if (a == 0) break; return (i); } int bigNumber::isPrime(NN_DIGIT *a, UINT2 digits, NN_DIGIT steps) { NN_DIGIT x[NN_SIZE],t[NN_SIZE],a1[NN_SIZE]; NN_DIGIT i,ok; AssignZero(x ,NN_SIZE); AssignZero(t ,NN_SIZE); AssignZero(a1,NN_SIZE); if (! (a[0] & 1) ) return 0; /* So chan! */ Sub(a1,a,one,NN_SIZE2); /* a1 = a - 1 */ ok = 1; i = steps; do { Rand(x,NN_SIZE2/2); ModExp(t,x,a1,NN_SIZE2,a,NN_SIZE2); ok = !Compare(t,one,NN_SIZE2); } while (--i && ok); return ok; } void main(){ UINT4 i; bigNumber veryLong; veryLong.AssignZero(veryLong.great,NN_SIZE); veryLong.AssignZero(one,NN_SIZE); one[0]=1; srand(time(NULL)); i=0; /* Sinh p nguyen to */ printf("Xin vui long doi...\n"); do { veryLong.Rand(veryLong.great,NN_SIZE2); veryLong.great[NN_SIZE2-1] |= 0x80000000; veryLong.great[0] |= 1; if (!(++i&0x1F)) { printf("\r%4d",i); } } while (!veryLong.isPrime(veryLong.great, NN_SIZE2, 10)); printf("\rMot so nguyen to ngau nhien:\n\n"); for (i=NN_SIZE2;i>0; printf("%08lX",veryLong.great[--i])); printf("\n\n"); } 2.Kiểm thử Chuwong trình khi chạy: ._.