Xây dựng chương trình xử lý song song để xác định một số nguyên lớn có phải là nguyên tố hay không

1 XÂY DỰNG CHƯƠNG TRÌNH XỬ LÝ SONG SONG ĐỂ XÁC ĐỊNH MỘT SỐ NGUYÊN LỚN CÓ PHẢI LÀ SỐ NGUYÊN TỐ HAY KHÔNG? SV. Nguyễn Thị Hoài Thương Email: nguyenthuong100492@gmail.com Võ Minh Tiến Email: vmtien88@gmail.com Lớp ĐHCNTT10, Khoa SP Toán – Tin GVHD: ThS. Nguyễn Thị Thùy Linh Tóm tắt nội dung: Gần đây, sự phát triển của kiến trúc máy tính song song đi kèm theo nó là các thuật toán song song đã làm thay đổi nhiều quan niệm về khả năng giải quyết các bài toán lớn hiện nay. Nhiều ứng dụng trong thực tế yêu cầu phải bảo mật và an toàn dữ liệu nên vấn đề bảo mật và an ninh mạng được quan tâm hàng đầu. Để tăng khả năng xử lý song song của máy tính song song thì phải khai thác tối đa năng lực của các bộ xử lý (CPU). Vì vậy, nhằm tăng khả năng tính toán của các CPU và nâng cao hiệu quả của giải thuật, chúng tôi lựa chọn nghiên cứu “Xây dựng chương trình xử lý song song để xác định một số nguyên lớn có phải là số nguyên tố hay không?”. Đề tài có thể giải quyết được vấn đề về cải thiện tốc độ xử lý, đáp ứng yêu cầu mã hóa trong lĩnh vực an toàn và bảo mật thông tin, đặc biệt là hệ mật mã RSA. 1. Mở đầu Tại sao phải xử lý song song? Hiện nay, với sự xuất hiện ngày càng nhiều các hệ thống điện tử đã làm cho lượng thông tin trong mọi lĩnh vực phát triển nhanh chóng, có cấu trúc đa dạng và phức tạp, đòi hỏi máy tính phải xử lý một lượng dữ liệu rất lớn với tốc độ cao. Có thể nói rằng những máy tính xử lý tuần tự theo kiểu Von Neumann (có 1CPU) khó có thể đáp ứng được yêu cầu về thời gian và khối lượng công việc thực hiện. Xử lý song song là quá trình xử lý gồm nhiều tiến trình được kích hoạt đồng thời và cùng tham gia giải quyết một bài toán. Nói chung, xử lý song song được thực hiện trên những hệ thống đa bộ xử lý (hay còn gọi là máy tính song song như hiện nay). Do 2 đó, thực hiện xử lý song song trên các máy tính song song để tăng hiệu quả và tốc độ tính toán của giải thuật. Mô hình xử lý song song đã và đang phát triển mạnh mẽ, giải quyết những vấn đề bế tắc mà mô hình xử lý tuần tự gặp phải như: vấn đề thời gian thực hiện chương trình, tốc độ xử lý, khả năng lưu trữ của bộ nhớ, Trong bối cảnh đó chúng tôi quyết định “Xây dựng chương trình xử lý song song xác định một số nguyên lớn có phải là số nguyên tố hay không?” nhằm giải quyết vấn đề trên. 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 khá quan trọng trong khoa học máy tính, đặc biệt là lĩnh vực an toàn và bảo mật thông tin. Thuật toán song song “xác định một số nguyên lớn có phải là số nguyên tố hay không?” sẽ đáp ứng được nhu cầu tính toán ngày càng cao về thời gian, tốc độ, quy mô,.. của bài toán. Nếu không có giải thuật song song cho bài toán này thì thời gian, tốc độ xử lý chậm, khả năng lưu trữ, quy mô nhỏ và đặc biệt là làm hạn chế việc ứng dụng bài toán cho các ứng dụng quan trọngVì vậy nhu cầu thực hiện tính toán song song để có thể tính toán, giải quyết một vấn đề nào đó cùng một lúc trên nhiều vi xử lý khác nhau đã trở nên cấp thiết và cần được nghiên cứu. 2. Kết quả chính 2.1. Đặt vấn đề Kiểm tra một số có phải số nguyên tố hay không là một bài toán khá quan trọng trong lĩnh vực bảo mật thông tin. Vì số nguyên tố được sử dụng rất rộng rãi trong các giải thuật mã hóa dùng khóa mở (public key cryptography algorithms), ứng dụng trong các bộ phát sinh số giả ngẫu nhiên (pseudorandom) và bảng hash (hash table). Vấn đề đặt ra là phải kiểm tra số nguyên tố lớn. Việc tính toán trên số nguyên lớn mất rất nhiều thời gian, đòi hỏi phải xử lý song song cho quá trình xác định số nguyên lớn có phải là số nguyên tố không? Muốn vậy thì giải thuật đi kèm theo nó phải là thuật toán song song. 3 2.2. Thiết kế thuật toán song song cho bài toán “xác định một số nguyên lớn có phải là số nguyên tố hay không?” 2.2.1. Định nghĩa số nguyên tố Số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó. Theo định nghĩa này số nguyên tố là số tự nhiên và chỉ có hai ước số phân biệt, đó chính là số 1 và bản thân nó. 2.2.2. Thiết kế thuật toán Input: Số nguyên dương x; Output = True, nếu x là số nguyên tố Flase, ngược lại Xử lý: B1: //Chữ số cuối của x là: 0,2,4,5,6,8 if ( (x chia hết cho 2) hoặc (x >5 và x chia hết cho 5) ) return false; B2: //Chữ số cuối của x là: 1,3,7,9 Gọi cx = số ký tự (căn bậc 2 của x); n = số ký tự của x; cx = (n+1)/2 (lấy phần nguyên); /*Chứng minh: Giả sử √x =a ; cx = số ký tự của a; n = số ký tự của x; x sẽ có tối đa: cx + (cx+1) ký tự, tối thiểu cx+(cx-1) ký tự, Ví dụ: a=84  cx=2, x=a*a=84*84 x có tối đa 2+2+1=5 ký tự, tối thiểu 2+2-1=3 ký tự  84*10 < x < 84*100 ; Vậy n = 2cx-1 hoặc 2cx hoặc 2cx+1 4  cx = (n+1)/2 hoặc n/2 hoặc (n-1)/2 Ta chọn cx = (n+1)/2 (lớn nhất trong 3 kết quả vì tìm một số gần với kết quả căn(x) , cho cx lớn nhất mà phải đảm bảo kết quả tìm được lớn hơn căn(x). Thuật toán sẽ chia từ 3,...căn(x), được quyền chia khỏi căn(x) nhưng không bỏ sót phần từ nào từ 3căn(x)) Ví dụ: √125 có (3+1)/2 = 2 ký tự x=125, n=3, cx=2 (căn(x) có 2 chữ số, nhưng không biết chính xác là số nào, nên chọn số nguyên lớn nhất có 2 chữ số là 99, khi đó thuật toán sẽ chia x cho khoảng (3,99). B3: // Ta có cx là số ký tự của √x Gọi m là số nguyên lớn nhất có cx ký tự Thực hiện chia x cho S, với S={3,5,7,9,. . ,m} Phân hoạch tập S thành S1,S2,S3,S4 tùy ý và ngẫu nhiên. Phân công cho các nhân CPU xử lý trên 4 tập S1,S2,S3,S4. với mỗi nhân thực thi lệnh sau: if ( x chia hết cho i) return false; Nếu 1 nhân trả về False thì dừng các nhân còn lại và chương trình trả về False, ngược lại thì True. 2.3. Cài đặt thuật toán OpenMP (Open Multi-Processing) đã được các nhà phát triển tích hợp thành chuẩn trong các ngôn ngữ lập trình phổ biến như: C/C++,Và được hỗ trợ trong hầu hết các hệ điều hành. OpenMP là một giao diện lập trình ứng dụng (API - Application Program Interface) được sử dụng để điều khiển các luồng (Thread) dựa trên cấu trúc chia sẻ bộ nhớ chung. Do đó, để cài đặt thuật toán cho bài toán chúng tôi sử dụng ngôn ngữ lập trình C++ với OpenMP trên Visual Studio 2010. Cấu trúc dữ liệu: 5 Xây dựng class SuperInt, để khai báo kiểu số nguyên lớn với tối đa 10000 ký tự, hoặc lớn hơn. Với các phương thức cơ bản: Cộng, Trừ, Nhân, Chia, Chia lấy dư có cấu trúc như sau: #include using namespace std; #include #include #define maxInt 10000 class SuperInt{ public: char supInt[maxInt]; public: SuperInt::SuperInt(char *s){ .. . } void SuperInt::setValue(char s[]){ .. . } bool SuperInt::checkType(){ .. . } SuperInt::SuperInt(){} .. . }; Hàm kiểm tra số nguyên tố: bool isChan(SuperInt a){ .. . } void isNgto(SuperInt s, SuperInt a, SuperInt b){ .. . } Chương trình chính sử dụng thư viện quan trọng: #include "stdafx.h" #include "targetver.h" #include #include #include #include "SuperInt.h" Đoạn chương trình xử lý song song: #pragma omp parallel shared() private() { #pragma omp sections nowait { #pragma omp section { //Hàm thực thi} #pragma omp section { //Hàm thực thi} } } 6 2.4. Kết quả thực hiện Chương trình đã được thực nghiệm trên máy Server của Trường Đại học Đồng Tháp với cấu hình máy: - Vi xử lý: Intel (R) Xeon (R) CPU E5540 @2.53GHz (8CPUs), ~2.5GHz - Bộ nhớ trong: 6132 MB RAM - Hệ điều hành: Windows Server® 2008 Standard (6.0, Build 6002) Kết quả thực nghiệm: Số nguyên lớn Song song (s) Tuần tự (s) 2147483647 11.03621 45.70646 68718952447 120.56385 509.29799 274876858367 130.56179 564.68737 Bảng 1 : Thống kê kết quả 7 Hình 1: Đồ thị so sánh kết quả Nhận xét: Thời gian thực hiện chương trình rút ngắn (tốc độ xử lý song song nhanh hơn khoảng 4 lần so với tốc độ xử lý tuần tự). Tốc độ này tính bằng giây (s) và còn tùy thuộc vào lượng công việc hiện có trong hệ thống. Giải thuật chỉ tối ưu với số nguyên dương lớn hơn 10 chữ số trong cùng giải thuật và xử lý song song, vì các phép toán cơ bản phải thực hiện qua bước trung gian của class SuperInt. Phương pháp kiểm tra số nguyên tố cổ điển là đơn giản và dễ thực hiện, đương nhiên nó được áp dụng đối với bài toán có dữ liệu nhỏ, độ phức tạp bình thường và thời gian cho phép,... 2147483647 68718952447 274876858367 0 100 200 300 400 500 600 Số nguyên lớn Tuần tự Song song Thời gian (s) 8 Phương pháp xây dựng thuật toán song song “xác định một số nguyên lớn có phải là số nguyên tố hay không? đã giải quyết được những vấn đề: - Kiểm tra được số nguyên lớn là số nguyên tố. - Tận dụng tối đa sức mạnh của các máy tính đa xử lý hiện nay. - Tốc độ xử lý song song nhanh hơn nhiều lần so tốc độ xử lý tuần tự. - Tăng tốc các ứng dụng, tăng hiệu suất làm việc cho người sử dụng. Việc áp dụng kết quả nghiên cứu đã tạo điều kiện cho sinh viên chuyên nghành CNTT nói chung và sinh viên chuyên ngành CNTT Trường Đại học Đồng Tháp nói riêng, khai thác được tối đa năng lực các CPU, tạo tiền đề cho giải quyết các bài toán lớn, đặc biệt là tăng tốc độ xử lý và mang lại hiệu quả trong lĩnh vực an toàn và bảo mật thông tin. 9 Tài liệu tham khảo [1] Đoàn Văn Ban, Nguyễn Mậu Hân, Xử lý song song và phân tán, NXB KH&KT, 2006. [2] TS. Trần Văn Hoài, Bài giảng môn học sau đại học Tính toán song song. [3] PGS.TS. Trần Văn Lăng, Bài giảng Tính toán song song và phân tán. [4] PGS.TS. Nguyễn Đức Nghĩa, Bài giảng môn Tính Toán song song, NXB Đại học Bách Khoa Hà Nội, 2008. [5] Hội nghị sinh viên nghiên cứu khoa học năm 2013 Lĩnh vực Khoa học Tự nhiên, Trường Đại Học Đồng Tháp. [6] Gunnar Staff. “Convergence and Stability of the Parallel algorithm: A numerical and theoretical investigation” – Department of Mathematical Sciences, Norwegian University of Science and Technology, N-7491 Trondheim, Norway. [7] “Introduction to OpenMP” – subpercomputing Institute of Minnesota University [8] [9] ách_số_nguyên_tố [10] RSA_(mã_hóa) [11]