Mục lục
Mục lục …………………………………………………………..…………..
i
Lời cam kết…………………………………………………………………...
iii
Lời cảm ơn……………………………………………………………………
iv
Danh mục viết tắt…………………………………………………...……………....
v
Danh mục các hình vẽ và bảng biểu………………………………………………...
vi
Lời nói đầu………………………………………………………………………… vii
Chương 1: Số nguyên tố và các bài toán liên quan……………………….
1
1.1. Định nghĩa về số nguyên tố…………………………………………..
1
8
2.1.2. Kiểm tra tính nguyên tố bằng thuật toán Miller…………………
11
2.1.3. Kiểm tra tính nguyên tố của số bằng phép kiểm tra xác suất……
11
2.1.4. Kiểm tra trên cơ sở định luật nhỏ Fermat……..………………….
12
2.1.5. Kiểm tra bằng Miller – Ranbin…………………………………
15
2.1.6. Kiểm tra bằng Solovay – Stransen………………………………
17
2.1.7. Kiểm tra tính nguyên tố của số bằng thuật toán đa thức…………
19
2.2. Thuật toán sinh số nguyên tố……………………………….…………
21
Kết luận của luận văn ……………………………………………………
48
TÀI LIỆU THAM KHẢO………………………………………………….
49
ii
Lời cam kết
Tài liệu được sử dụng trong luận văn được thu thập từ các nguồn kiến thức
hợp pháp, có trích dẫn nguồn tài liệu tham khảo. Chương trình sử dụng mã
nguồn mở, có xuất xứ.
Dưới sự giúp đỡ nhiệt tình và chỉ bảo chi tiết của giáo viên hướng dẫn, tôi đã
hoàn thành luận văn của mình. Tôi xin cam kết luận văn này là của bản thân tôi
làm và nghiên cứu, không hề trùng hay sao chép của bất kỳ ai.
iii
Lời cảm ơn
Trước hết tôi xin gửi lời cảm ơn đến TS. Nguyễn Thị Hồng Minh, Phó
Chủ nhiệm khoa Sau đại học, Đại học Quốc gia Hà Nội người đã hướng dẫn và
giúp đỡ tôi rất nhiều trong suốt quá trình tìm hiểu nghiên cứu và hoàn thành
Đpcm
Điều phải chứng minh
CMKTTTT
Chứng minh không tiết lộ thông tin
UCLL
Ước chung lớn nhât
TTĐT
Thanh toán điện tử
CT
Cử Tri
KP
Kiểm Phiếu
TMĐT
Thương mại điện tử
GMR
Hình 1.1: Sơ đồ quy trình bỏ lá phiếu điện tử…………………………….
35
Hình 1.2: Sơ đồ giai đoạn đăng ký bỏ phiếu……………………………… 36
Hình 1.3: Sơ đồ giai đoạn bỏ phiếu………………………………………. 38
vi
Lời nói đầu
Ngày nay, công nghệ thông tin đang phát triển mạnh mẽ, Internet đã trở
thành một phần không thể thiếu trong cuộc sống hàng ngày thì các hoạt động
trao đổi thông tin, mua bán,…trên mạng Internet diễn ra thường xuyên và ngày
phổ biến hơn. Chính vì vậy mà việc bảo mật, đảm bảo an toàn thông tin đang là
nhu cầu cấp thiết. Trước các nhu cầu cấp thiết đó, lý thuyết về mật mã thông tin
đã ra đời nhằm đảm bảo tính an toàn dữ liệu tại nơi lưu trữ cũng như khi dữ liệu
đang được truyền trên mạng. Mật mã học là một trong những vấn đề quan trọng
trong lĩnh vực bảo mật và an toàn thông tin.Trên thế giới mật mã học được ra
đời từ thời La Mã cổ đại và ngày càng được nghiên cứu, phát triển đạt những
thành tựu to lớn. Trong mật mã học thì vấn đề bảo mật luôn đi đôi với vấn đề
xác thực thông tin, đặc biệt trong hệ thống mã hóa khóa công khai vấn đề xác
thực là vô cùng quan trọng, để giải quyết vấn đề trên người ta đưa ra một cách
giải quyết hiệu quả, đó là phương pháp chứng minh không tiết lộ thông tin. Với
sự bùng nổ của mạng Internet hiên nay, mạng máy tính đang ngày càng đóng vai
trò thiết yếu trong lĩnh vực hoạt động xã hội, và khi nó trở thành phương tiện
điều hành các hệ thống thì nhu cầu bảo mật thông tin được đặt lên hàng đầu.
số kết quả thực nghiệm để kiểm chứng hiệu quả của thuật toán trên hệ thống
máy tính để kiểm tra và sinh số nguyên tố lớn, lồng ghép vào chương trình
chứng minh không tiết lộ thông tin trong việc mô tả quá trình bỏ lá phiếu điện
tử.
viii
1
Chương 1: Số nguyên tố và các bài toán liên quan
1.1. Định nghĩa số nguyên tố
Số tự nhiên p, lớn hơn 1 gọi là số nguyên tố nếu như nó chỉ chia hết cho 1 và
chính nó. Định lý cơ bản của số học nói rằng, bất kỳ số tự nhiên n, lớn hơn 1 có
thể phân tích thành tích các số nguyên tố. Tức là một số tự nhiên n có thể biểu
diễn dưới dạng sau:
n p1 1 ... pk k ,
ở đây p1 p2 ... pk - là các số nguyên tố khác nhau, 1 ,..., k N .
1.2. Tính chất của số nguyên tố
Ký hiệu "b a" nghĩa là b là ước của a, ký hiệu a b nghĩa là a chia hết cho b.
Ước tự nhiên khác 1 nhỏ nhất của một số tự nhiên là số nguyên tố.
Chứng minh: Giả sử d a; d nhỏ nhất; d 1.
Nếu d không nguyên tố d = d1.d2; d1, d2 > 1
d1|a với d1
pháp này.
Thế nhưng, các nhà toán học chưa thỏa mãn với việc dùng phương pháp
này để tìm ra số nguyên tố, bởi vì nó có chút mò mẫm nhất định, bạn không thể
biết trước được số nguyên sẽ “sàng” ra số nào. Điều mà các nhà toán học muốn
là tìm ra quy luật của số nguyên tố để nghiên cứu sâu hơn về nó.
Từ trong bảng các số nguyên tố, chúng ta có thể thấy chúng được phân bố
như sau: từ 1 đến 1000 có 168 số nguyên tố; từ 1000 đến 2000 có 135 số; từ
2000 đến 3000 có 127 số; từ 3000 đến 4000 có 120 số; từ 4000 đến 5000 có 119
số. Khi số các số tự nhiên càng lớn thì tỉ lệ phân bố các số nguyên tố càng thưa.
Số nguyên tố đã "hoá trang" cho mình rồi lẩn khuất trong các số tự nhiên, khiến
việc tìm ra chúng trở nên khó khăn hơn.
Ví dụ, 101, 401, 601, 701 đều là số nguyên tố, nhưng 301 và 901 thì lại
không phải. Có người thử tính như thế này: 12 + 1 + 41 = 43, 22 + 2 + 41 = 47,
32 + 3 + 41 = 53, ..., 392 + 39 + 41 = 1601. Có 39 số từ 43 cho đến 1601 đều là
số nguyên tố, thế nhưng tiếp sau đó: 402 +40 +41 =1681 = 41 x 41 thì lại là một
hợp số.
2
Nhà toán học người Pháp Ferma từng nghiên cứu lâu dài về số nguyên tố,
ông từng đưa ra một suy đoán thế này: số (22n + 1) (với n là số nguyên) thì nhất
định là số nguyên tố. Ferma đã thử 5 "số Ferma" đầu thì đều là số nguyên tố,
nhưng đến số "ferma" thứ sáu thì lại là hợp số, hơn nữa từ số "Ferma thứ 6" trở
đi, không thể phát hiện thấy số nguyên tố nào nữa, toàn là hợp số. Xem ra số
nguyên tố đã cố trêu đùa Ferma.
Năm 1644, nhà toán học người Pháp Mason đã đưa ra "số Mason", hình
thức của nó là (2p - 1). Khi ông còn sống, ông tìm ra 11p để cho (2p - 1) là số
nguyên tố, người ta tiến hành kiểm chứng đối với 8p, chúng đều là số nguyên tố.
250 năm sau, năm 1903, các nhà toán học tìm ra số Mason thứ 9 không phải là
đã cống hiến một năng lực xử lý nhiều hơn bất cứ ai: tương đương với khả năng
xử lý của của một máy tính Pentium 90MHz chạy liên tục trong... 67.000 năm.
Hai giáo sư Curtis Cooper và Steven Boone là những người phụ trách dự án này.
Con số nguyên tố được phát hiện lần này là số nguyên tố Mersenne thứ 43 được
tìm ra.
1.3.2. Phân tích ra thừa số nguyên tố
Các số có dạng Mq = 2q - 1 (với q là nguyên tố) được gọi là các số
Mersenne và đã được nghiên cứu công phu.
Vào năm 1640 , Mersenne đã cho rằng Mq là số nguyên tố đối với
q=13,17,19,31,67,127,257; ông đã nhầm đối với 67 và 257 và đã không đưa 61,
89 và 107 vào danh sách trên. Những số này còn sinh ra các số nguyên tố
Mersenne. Phát hiện của ông thực sự đáng kinh ngạc về mặt độ lớn của các số.
Một bài toán khá hiển nhiên là: Xét xem một số Mersenne có là số nguyên tố
không, và nếu không thì xác định các thừa số của nó ( hay còn gọi là bài toán
phân tích ra thừa số). Một kết quả cổ điển do Euler đưa ra năm 1750 và sau đó
được Lagrange (1775) và Lucas (1875) chứng minh là:
Nếu q là một số nguyên tố đồng dư modul log 4(q(3) (mod 4)) thì Mq chia hết
cho 2q + 1 khi và chỉ khi 2q + 1 là nguyên tố; trong trường hợp này, nếu q> 3 thì
Mq là hợp số.
4
Thật vậy: Cho n = 2q + 1 là một thừa số của M q Vì 22# 1 (mod n) nên 2q# 1
(mod n), và 22q - 1 = (2q+1)Mqº0 (mod n), từ đó bằng phép thử của Lucas suy ra
n là một số nguyên tố.
Ngược lại, cho p = 2q + 1 là một số nguyên tố. Vì pº7(mod 8) nên
(2/p)=1, do vậy tồn tại m sao cho 2ºm2 (mod p). Điều này chứng tỏ rằng 2qº2(p1)/2
ºmp - 1º1(mod p) Vì vậy Mq chia hết cho p.
5
Như vậy khi phân tích một số a > 1thành một tích những thừa số nguyên tố,
ta có thể gặp cùng một thừa số nhiều lần. Nếu p1,p2,...,pn xuất hiện theo thứ
tự α1,...,αn lần thì ta có: a = p1α1 p2α2... pnαn.
Đây là dạng phân tích chính tắc tiêu chuẩn của a.
Ví dụ: 360 = 23.32.5.
Giả sử a = p1α1 p2α2... pnαn là dạng phân tích chính tắc của số tự nhiên a > 1.
Khi đó nếu d là một ước dương của a
d = p1β1 p2β2... pnβn với 0 ≤ βi ≤ αi ; i = 1, n
Vậy nên nếu cho n số tự nhiên lớn hơn 1
a1 p111 p212 ...pm1m
an p1m1 p2m2 ...pmmn
Khi đó: (a1, ..., an) = p1β1 ... pmβm với βj = min (αij); i = 1, n ; j = 1, m .
[a1, ..., an] = p1ƴ1 ... pmƴm, ƴj = max(αij); i= 1, n ; j = 1, m .
1.4. Kết luận chương
Như vậy, chương 1 đã tổng quan về số nguyên tố và phân tích thừa số
nguyên tố. Đây là kiến thức cơ sở chuẩn bị cho những nghiên cứu tiếp theo của
bản luận văn này.
Phần đầu nói về định nghĩa và các tính chất của số nguyên tố.
Tiếp theo là những vấn đề về sinh số nguyên tố và phân tích số nguyên tố
đó ra thừa số.
Nội dung chính chương giúp hiểu được số nguyên tố và mô hình hóa lập kế
hoạch giải quyết các bài toán về số nguyên tố. Đây là cơ sở quan trọng để tiến
hành xây dựng các thuật toán kiểm tra số nguyên tố và sinh số nguyên tố lớn
đảm bảo hiệu quả, sẽ trình bày ở các chương tiếp theo.
thêm và điều chỉnh một số lệnh như sau:
- Thêm lệnh kiểm tra trường hợp n là số chẵn (n%2==0) kết thúc thuật
toán trả về giá trị 0.
- Điều chỉnh vòng lặp for với i chạy từ 2 tới n mà vẫn nhận được kết
quả đúng. Vì nếu một số n không là nguyên tố có ước a thì sẽ có ước n/a, một
trong hai giá trị a hoặc n/a sẽ có nhỏ hơn n , vậy chúng ta chỉ cần thực hiện
vòng lặp đến n để tìm ra ước của n nếu có. Giải thuật 2 có thể được viết lại
như sau:
7
Giải thuật 2: Kiểm tra số nguyên tố
Input: n (lớn hơn 2)
Output: 1 nếu n là số nguyên tố, 0 nếu ngược lại
Begin
if (n%2==0) return 0;
for (i=2; i
5. Nếu như F (a) n , thì n là số nguyên tố.
6. Nếu như a log 2 n, thì quay về tầng 2 với a là giá trị tiếp theo. Nếu
như a log 2 n 1 , thì n là hợp số.
Đánh giá độ phức tạp của thuật toán Konigin- Pomerans
k
Nếu giả sử n N , n 1 , n là số lẻ, n 1 q aj .Lúc này việc kiểm tra tính
j
j 1
log n 17 / 7
.Thật vậy với n N , n 1 , n là số
log log n
nguyên tố của n có thể có chi phí là O
lẻ, n 1 F1 .R1 , ở đây UCLN ( F1 , R1 ) 1 , và biết được sự phân chia F1 ra thừa số
nguyên tố. Nếu F1 n
1
4n
, với là số dương không đổi, thì việc kiểm tra tính
nguyên tố của n có thể chi phí là O((log n) c ( ) ) ( c( ) là số nguyên dương không
đổi, phụ thuộc vào .
thỏa mãn không
A 1(mod n) .
Nếu như đúng thì nhảy sang bước 4. Ngược lại
p
M : Mp j , A : A j ;
Và chuyển đến giá trị tiếp theo của l trong chu trình.
4. Nếu như j
11
nhiên hay thuật toán xác suất. Trong các thuật toán loại này, dùng để kiểm tra
ngẫu nhiên không bao giờ kết luận một số nguyên tố là hợp số nhưng có thể kết
luận một hợp số là số nguyên tố. Xác suất sai của phép kiểm tra có thể giảm
xuống nhờ việc chọn một dãy độc lập các số a nếu với mỗi số a xác suất để
thuật toán kết luận một hợp số là số nguyên tố là nhỏ hơn một nửa thì sau k lần
thử độc lập, xác suất sai là nhỏ hơn 2 k,độ tin cậy của thuật toán sẽ tăng lên theo
k.
Cấu trúc cơ bản của một phép kiểm tra ngẫu nhiên là:
Input: n
Output: Số n cần kiểm tra là hợp số hay là số nguyên
Thuật toán kiểm tra xác suất
1: Chọn một số ngẫu nhiên a.
2: Kiểm tra một hệ thức nào đó giữa số a và số n đã cho. Nếu hệ
thức sai thì chắc chắn n là một hợp số (số a là "bằng chứng" chứng
tỏ n là hợp số) và dừng thuật toán.
3: Lặp lại bước 1 cho đến khi đạt được số lần đã định hoặc gặp
bước 2.
Sau một loạt lần kiểm tra, nếu không tìm được bằng chứng chứng tỏ n là hợp
số thì ta kết luận n là số nguyên tố.
Các phép kiểm tra tính nguyên tố ngẫu nhiên là: Phép kiểm tra tính nguyên tố
của Fermat (kiểm tra Fermat). Đây là phép thử heuristic, tuy nhiên ít người sử
dụng phép thử này. Được sử dụng nhiều hơn là Kiểm tra Miller-Rabin và Kiểm
tra Solovay-Strassen.Với mỗi hợp số n, ít nhất 3/4 (với kiểm tra Miller-Rabin)
hoặc 1/2 (Với kiểm tra Solovay-Strassen) các số a là bằng chứng chứng tỏ n là
hợp số).
2.1.4. Kiểm tra trên cơ sở định luật nhỏ của Fermat
Phương pháp này dựa trên định luật nhỏ của Fermat: Nếu như n là số nguyên
5: Nếu như đẳng thức đúng thì trả lời là chưa biết, nhưng có thể kiểm tra
lại một số lần với các a khác nhau.
Giải thuật Fermat kiểm tra tính nguyên tố của số
13
Input: n: giá trị để kiểm tra tính nguyên tố; k: tham số tham gia vào quá trình
kiểm tra .
Output: Số n cần kiểm tra là hợp số, hay là nguyên tố xác suất.
Begin
repeat k times:
lấy a ngẫu nhiên trong [1, n 1]
if an 1 mod n ≠ 1 then
return hợp số
return nguyên tố xác suất
End.
Khi dùng thuật toán tính nhanh luỹ thừa theo mođun, thời gian thi hành của
thuật toán là O(k × log3n), ở đó k là số lần kiểm tra với mỗi số a ngẫu nhiên, và
n là giá trị ta muốn kiểm tra. Và từ việc kiểm tra này dẫn ta đến phần sau.
Cho n>1 là số tự nhiên lẻ, n 1 22.d , ở đây d là số lẻ. Số n gọi là số giả
nguyên tố
Chặt chẽ trong cơ sở a, a N , nếu như UCLN (a, n) 1 hoặc a d 1(mod n) , hoặc
r
a d .2 1(mod n) , với 0 r s .
s
Vậy cho nên nếu n là số nguyên tố, thì a n 1 1(mod n) , tức là a 2 d 1(mod n) .
Từ đây ta có a 2
Như vậy chúng ta thấy việc kiểm tra trên cơ sở tính chặt chẽ giả nguyên tố là
hiệu quả đối với việc tìm số hợp số, thế nhưng cách này cũng chỉ đúng trong
một điều kiện cần thiết.
2.1.5. Kiểm tra bằng Miller-Rabin
Kiểm tra Miller-Rabin là một thuật toán xác suất để kiểm tra tính nguyên tố.
Nó được đề xuất đầu tiên bởi Gary L. Miller như một thuật toán tất định, dựa
trên giả thiết Riemann tổng quát; Michael O. Rabin đã sửa chữa nó thành một
thuật toán xác suất.
Khi sử dụng kiểm tra Miller-Rabin chúng ta căn cứ vào một mệnh đề
Q(p,a)đúng với các số nguyên tố p và mọi số tự nhiên a A N và kiểm tra xem
chúng có đúng với số n muốn kiểm tra và một số a A được chọn ngẫu nhiên
hay không? Nếu mệnh đề Q(n,a) không đúng, tất yếu n không phải là số nguyên
tố, còn nếu Q(n,a) đúng, số n có thể là số nguyên tố với một xác suất nào đó.
Khi tăng số lần thử, xác suất để n là số nguyên tố tăng lên.
Giải thuật kiểm tra Miller-Rabin
Input : Số tự nhiên lẻ n.
Output : FALSE nếu n là hợp số, nếu không TRUE
Begin
1. Phân tích n - 1 = 2 s m trong đó s 1 và m là số tự nhiên lẻ
2. Chọn ngẫu nhiên số tự nhiên a {2,...,n-1}.
3. Đặt b = am(mod n)
4. Nếu b 1(mod n) thì trả về TRUE. Kết thúc.
5. Cho k chạy từ 0 đến s-1:
a. Nếu b 1(mod n) thì trả về TRUE. Kết thúc.
b. Thay b:=b2(mod n).
6. Trả lời FALSE.
End.
15
s 1
m
có a 2
s 1
m
là căn bậc 2 của 1 modulo n, theo bổ đề ta có hoặc
1(mod n) hoặc a 2
s 1
m
s 1
m
1(mod n) , nên a 2
1(mod n) . Mà theo giả thuyết chứng minh ta
s 1
m
Gọi A là biến cố "Số n là hợp số". B là biến cố "Kiểm tra Miller-Rabin trả lời
n là số nguyên tố". Khi đó xác suất sai của kiểm tra này là xác suất để số n là
hợp số trong khi thuật toán cho câu trả lời TRUE, nghĩa là xác suất điều kiện
P(A|B).
16
Copyright: Tài liệu đại học ©