sunmi_nguyen

New Member
Download miễn phí Đề tài 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
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:

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 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à cách 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.cách:
+ 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 :
Code:
// 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  (MAX_NN_DIGIT - *c))

                    borrow = 1;

                else

                    borrow = 0;
Link Download bản DOC
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:

 
Last edited by a moderator:
Các chủ đề có liên quan khác
Tạo bởi Tiêu đề Blog Lượt trả lời Ngày
D Xây dựng chương trình quản lý chất lượng theo haccp cho sản phẩm pa tê thịt heo Nông Lâm Thủy sản 0
D Tìm hiểu và xây dựng chương trình HACCP cho sản phẩm tôm đông lạnh xuất khẩu Nông Lâm Thủy sản 0
D Xây dựng và sử dụng bài tập có nội dung thực tế chương “dòng điện không đổi” Luận văn Sư phạm 0
D Khảo sát, đánh giá thực trạng công tác tổ chức xây dựng chương trình, kế hoạch tại ủy ban nhân dân Văn hóa, Xã hội 0
D Nghiên cứu vấn đề điều khiển lò nhiệt. Đi sâu xây dựng chương trình giám sát nhiệt độ lò nhiệt trong phòng thí nghiệm sử dụng card PCI 1710 Công nghệ thông tin 0
D Xây dựng chương trình truyền thông cổ động cho sản phẩm sữa đậu nành Vinasoy Luận văn Kinh tế 0
D Báo cáo môn lập trình hướng đối tượng - Xây dựng chương trinh quản lí sinh viên Công nghệ thông tin 1
D Xây dựng và sử dụng hệ thống bài tập theo các mức độ tư duy trong dạy học chương Anđehit – xeton – axit cacboxylic lớp 11 THPT Ngoại ngữ 0
P Xây dựng chương trình trao đổi thông điệp trong mạng nội bộ Luận văn Kinh tế 0
B Xây dựng chương trình nhận dạng phiếu kết quả thi trắc nghiệm Luận văn Kinh tế 0

Các chủ đề có liên quan khác

Top