Đề tài 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?

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

1

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

đó, 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ọng…Vì 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à

2

thuật toán song song.

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 ;

3

Vậy n = 2cx-1 hoặc 2cx hoặc 2cx+1

 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ừ 3…că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.

4

Cấu trúc dữ liệu:

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:

.. .

.. .

.. .

SuperInt::SuperInt(char *s){ } void SuperInt::setValue(char s[]){ } bool SuperInt::checkType(){ }

SuperInt::SuperInt(){}

.. .

#include using namespace std; #include #include #define maxInt 10000 class SuperInt{ public: char supInt[maxInt]; public: };

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 section { //Hàm thực thi} #pragma omp section { //Hàm thực thi} }

#pragma omp parallel shared() private()

{ #pragma omp sections nowait }

5

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 2147483647 68718952447 274876858367 Song song (s) 11.03621 120.56385 130.56179 Tuần tự (s) 45.70646 509.29799 564.68737

6

Bảng 1 : Thống kê kết quả

Thời gian (s)

600

500

400 Tuần tự

Song song 300

200

100

Số nguyên lớn 2147483647 68718952447 274876858367 0

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à

7

thời gian cho phép,...

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

8

mật thông tin.

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] http://www.ieev.org/2009/12/kiem-tra-so-nguyen-to-primality-test.html

[9] http://vi.m.wikipedia.org/wiki/Danh_sách_số_nguyên_tố

[10] http://vi.wikipedia.org/wiki/ RSA_(mã_hóa)

9

[11] http://old.voer.edu.vn/module/khoa-hoc-xa-hoi/he-ma-rsa.html