1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Nguyễn Thanh Hào
XỬ LÝ SONG SONG QUÁ TRÌNH SINH KHÓA
CỦA HỆ THỐNG CẤP PHÁT CHỨNG THỰC SỐ
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2010
2
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thanh Hào
XỬ LÝ SONG SONG QUÁ TRÌNH SINH KHÓA
CỦA HỆ THỐNG CẤP PHÁT CHỨNG THỰC SỐ
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: PGS.TSKH Phạm Huy Điển
HÀ NỘI - 2010
TÓM TẮT NỘI DUNG
Khóa luận có trình bày về một số vấn đề của an toàn thông tin hiện đại. Các vấn đề
đó đều dẫn đến một nhu cầu bức thiết là phải xây dựng một hệ thống chứng thực số, tạo
điều kiện cho các ứng dụng chữ ký số phát triển. Phần tiếp theo là các lý thuyết về
chứng thực và chữ ký số, hệ thống chứng thực số CA ứng dụng hệ mã RSA mà cốt lõi là
quá trình sinh khóa. Thực chất của quá trình sinh khóa là sinh ra một cặp số nguyên tố
qp,
thỏa mãn được các tính chất là số nguyên tố xác suất mạnh. Với yêu cầu về số
nguyên tố như thế, phần tiếp theo khóa luận có đề cập đến các lý thuyết về số nguyên tố,
việc kiểm tra số nguyên tố, và các tính chất để một số nguyên tố được gọi là mạnh. Với
một khối lượng tính toán trên số nguyên lớn như vậy, xử lý tuần tự là không đáp ứng

2.3. Chìa khóa an toàn .........................................................................................30
Chương 3. Tính toán song song................................................................................32
3.1. Xử lý song song, cơ hội và thách thức [8]......................................................32
3.1.1. Cơ hội.....................................................................................................33
3.1.2. Những thách thức: Các vấn đề khó khăn gặp phải khi xử lý song song...34
3.1.3. Giải pháp: Các công nghệ song song trong Visual Studio 2010 Microsoft
.........................................................................................................................36
3.2. Lập trình song song với Visual Studio 2010 [8].............................................37
3.2.1. Thư viện ........................................................................................37
3.2.2. Các mô hình lập trình song song và ví dụ................................................38
3.2.3. Kết luận..................................................................................................42
Chương 4. Kết quả triển khai và tính thử nghiệm .....................................................43
4.1. Giới thiệu về chương trình ứng dụng ............................................................43
4.1.1. Mục đích và hoạt động của chương trình................................................43
4.1.2. Một số hình ảnh về chương trình.............................................................44
4.2. Một số thống kê khi chạy chương trình trên chip intel core2duo 2.2 GHZ......47
PHỤ LỤC ....................................................................................................................48
A. Thuật toán Miller-Rabin.......................................................................................48
B. Thuật toán Lucas..................................................................................................48
4
C. Thuật toán kiểm tra nguyên tố mạnh....................................................................49
KẾT LUẬN..................................................................................................................51
TÀI LIỆU THAM KHẢO............................................................................................52
LỜI MỞ ĐẦU
Hiện nay, ở các nước phát triển cũng như đang phát triển, mạng máy tính đóng vài
trò quan trọng trong mọi lĩnh vực hoạt động của xã hội, và một 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. Nhu
cầu này không chỉ có ở các bộ máy của nhà nước, mà đã trở thành bức thiết trong nhiều
hoạt động kinh tế xã hội: tài chính, ngân hàng, thương mại … Những ứng dụng trong
dân sự của an toàn thông tin ngày càng được phát triển, mở rộng đặc biệt là chữ ký số.

Thời gian trước, công nghệ xử lý song song được thực hiện trên các cụm nhiều
máy chủ do thời ấy một CPU (central processing unit) không có nhiều nhân. Ngày nay,
với sự phát triển vượt bậc của công nghệ phần cứng, các hãng phần cứng nổi tiếng thế
giới đã nghiên cứu và liên tục cho ra đời nhiều bộ xử lý tích hợp nhiều lõi bên trong (2,
4, 8 thậm chí 16 lõi). Đây là một thời điểm thuận lợi để ứng dụng công nghệ xử lý song
song trên một CPU có nhiều nhân. Một phương án khác có lợi hơn về mặt kinh tế là tính
toán trên card đồ họa (graphic card). Card đồ họa tuy có thế mạnh về xử lý vector (xử lý
nhiều bộ số một lúc) nhưng công nghệ song song còn chưa phát triển (chưa có thư viện
cần thiết để sinh được một cặp số nguyên tố lớn và kiểm tra tính nguyên tố mạnh của
chúng). Vì vậy, xử lý song song trên CPU nhiều nhân là một phương án hợp lý, cân đối
về mặt kinh tế và công nghệ hỗ trợ cũng như là tốc độ. Tập đoàn Microsoft mới cho ra
đời bộ công cụ Visual Studio 2010 hỗ trợ xử lý song song trên CPU nhiều nhân, đồng
thời có thư viện xử lý số nguyên lớn. C Sharp (C#) – một ngôn ngữ lập trình trong bộ
công cụ này sẽ được sử dụng để phát triển giai đoạn quan trọng ban đầu của một hệ
thống CA – sinh khóa.
6
Chương 1. Những vấn đề của an toàn thông tin hiện đại
NỘI DUNG
Chương 1. Những vấn đề của an toàn thông tin hiện đại
1.1. An toàn thông tin hiện đại
Hiện nay, ở tất cả các nước phát triển cũng như đang phát triển, mạng máy tính
đang đóng vài trò thiết yếu trong mọi lĩnh vực hoạt động của toàn xã hội, và một 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. Nhu cầu này không chỉ có ở các bộ máy An ninh, Quốc phòng, Quản lý Nhà
nước, mà đã trở thành bức thiết trong nhiều hoạt động kinh tế xã hội: tài chính, ngân
hàng, thương mại …
An toàn thông tin ngày nay không đơn thuần là việc giữ bí mật những thông tin
quan trọng (được áp dụng trong quân đội, bộ quốc phòng, an ninh quốc gia …) mà còn
là chứng thực thông tin (thông tin đó thuộc về một cá nhân, tập thể cụ thể nào đó).
Những ứng dụng của an toàn thông tin dân sự, đặc biệt là chữ ký số ngày càng phát

(bằng chìa
k
E
) ta sẽ được một văn bản mã ký hiệu là
( )
k
C E P
=
. Văn bản này chỉ
có thể được giải mã bằng chìa khóa
k
D
(cùng cặp với
k
E
), nghĩa là
( ) ( ( ))
k k k
D C D E P P
= =
.
Chương 1. Những vấn đề của an toàn thông tin hiện đại
Khi một cá thể
i
nào đó muốn giử thông điệp
M
cho đối tác
k
thì anh ta dùng
chìa khóa lập mã

của cá thể
K
.
Ký điện tử trong hệ mã khóa công khai [3][5][13]
Với hệ mã khóa công khai, một quy trình ký văn bản điện tử được thiết lập dựa
trên ý tưởng của hai nhà khoa học Diffie và Hellman [5][13]:
 Người gửi (chủ nhân văn bản) ký văn bản bằng cách mã hóa nó với khóa bí mật
của mình rồi gửi cho người nhận.
 Người nhận văn bản (đã ký) tiến hành kiểm tra chữ ký bằng cách sử dụng chìa
khóa công khai của người gửi để giải mã văn bản. Nếu giải mã thành công thì
văn bản ký là đúng của người gửi.
Giao thức này mang đầy đủ các thuộc tính của thủ tục ký thông thường. Thật vậy:
 Chữ ký là sản phẩm của người đã chủ động tạo ra nó, tức là người đã dùng chiếc
chìa khóa bí mật của mình để mã hóa văn bản.
 Chữ ký cho biết chủ nhân của nó chính là người sở hữu chiếc chìa khóa bí mật đã
được dùng để mã văn bản (kiểm tra bằng cách cho giải mã bằng chìa khóa công
khai của người đó). Không ai làm giả được “chữ ký” vì rằng chỉ có duy nhất một
người có chìa khóa bí mật đã dùng để “ký” (mã hóa).
 Chữ ký cho văn bản này không thể “tái sử dụng” cho văn bản khác. Thật vậy,
việc biết chữ ký (văn bản mã) không cho phép tìm ra được chìa khóa bí mật của
người gửi (để có thể ký một văn bản khác).
 Văn bản đã ký không thể thay đổi (xuyên tạc) được nội dụng. Thật vậy, nếu đã
mở ra để thay đổi thì không thể “ký lại” được nữa, vì không có chiếc chìa khóa
bí mật của “người đã ký” (như đã nói ở trên).
 Người ký văn bản không thể thoái thác việc mình “đã ký”, vì ngoài ông ta ra
không còn ai có cái chìa khóa đã được dùng để “ký” văn bản.
Chương 1. Những vấn đề của an toàn thông tin hiện đại
Rõ ràng, về mặt logic thì quy trình ký như trên là rất hợp lý. Mọi thành viên tham gia sử
dụng một hệ mã khóa công khai đều có được khả năng ký văn bản điện tử (bằng chìa
khóa bí mật của riêng mình) và kiểm tra chữ ký của những người khác (bằng chìa khóa

P
).
Tức là tuân theo sơ đồ sau:
Chương 1. Những vấn đề của an toàn thông tin hiện đại
Hình 1.1: Quy trình ký điện tử [13]
Dễ dàng thấy rằng chữ ký số được tạo ra trong quy trình trên có đầy đủ các thuộc
tính đã nêu trong mục đầu. Thời gian tạo chữ ký được giảm đi rất nhiều và gần như
không phụ thuộc vào độ dài của văn bản. Thật vậy, do thời gian tính đặc trưng văn bản
là không đáng kể, thời gian tạo chữ ký chỉ còn là việc mã hóa đặc trưng của văn bản (có
độ dài như nhau với mọi văn bản, và nhỏ hơn độ dài văn bản nhiều lần).
Một người nào đó, nhận được văn bản
P
cùng với chữ ký số đi kèm, muốn tiến
hành kiểm tra thì cần tiến hành các bước sau [3][13]:
 Tính đặc trưng của văn bản
P
(bằng hàm chiết xuất có sẵn trên hệ thống).
 Giải mã chữ ký số (bằng chìa khóa công khai của ông A) để có một đặc trưng
nữa của
P
, rồi so sánh nó với đặc trưng thu được ở bước trên. Nếu chúng khớp
nhau thì chứng tỏ văn bản nhận được chính là văn bản đã được ông A ký và nội
dung của nó không bị thay đổi so với khi ký.
Tức là tuân theo sơ đồ sau:
Chương 1. Những vấn đề của an toàn thông tin hiện đại
Hình 1.2: Quy trình kiểm tra chữ số ký số [13]
Như vậy, chữ ký số không phải là một nét vẽ ngoằn ngoèo khó bắt chước (như chữ
ký tay thông thường trên giấy) mà là một dãy số được tạo nên từ đặc trưng của văn bản
bằng phép mã hóa với chìa khóa bí mật của người ký.
So với thủ tục ký thông thường (trên văn bản giấy), thủ tục ký điện tử có những ưu

giúp người ta khẳng định được một chìa khóa công khai nào đó thuộc về thực thể nào
[7].
Một chứng thực số chuẩn mực thường bao gồm chìa khóa công khai và một số
thông tin về thực thể sở hữu chìa khóa đó (tên, địa chỉ,…). Như vậy, thông tin trên
chứng thực số không chỉ cho biết một chìa khóa công khai nào đó thuộc về ai, ta còn có
thể biết được các thông tin liên quan khác, mà đôi khi cũng rất quan trọng trong một hệ
thống cụ thể, như là danh phận, chức vụ,… của người sở hữu [3].
Trong một mô hình với hạ tầng khóa công khai (PKI) chuẩn mực, chữ ký trong
chứng thực thuộc về nhà cung cấp chứng thực số (Cerfiticate Authority, viết tắt là CA).
Chữ ký trong chứng thực là sự đảm bảo của người ký về mối liên hệ giữa chìa khóa
công khai và thực thể được chứng nhận.
Nội dung của chứng thực số theo chuẩn X.509 [3][13]
Tiêu chuẩn về chứng thực số trên cơ sở hạ tầng khóa công khai phổ biến nhất hiện
nay là X.509 được ban hành bởi ITU-T (International Telegraph Union – Telecom, tổ
chức viễn thông quốc tế (về lĩnh vực viễn thông), thuộc liên hợp quốc). Bao gồm:
 Version: Chỉ định phiên bản của chứng nhận X.509.
 Serial Number: Số loạt phát hành được gán bởi CA. Mỗi CA nên gán một mã số
loạt duy nhất cho mỗi giấy chứng nhận mà nó phát hành.
 Signature Algorithm: Thuật toán chữ ký và chỉ rõ thuật toán mã hóa được CA sử
dụng để ký giấy chứng nhân. Trong chứng nhận X.509 thường là sự kết hợp giữa
Chương 1. Những vấn đề của an toàn thông tin hiện đại
thuật toán băm (chẳng hạn như MD5) và thuật toán khóa công khai (chẳng hạn
như RSA).
 Issuer Name: Tên tổ chức CA phát hành chứng thực. Hai CA khác nhau không
được sử dụng cùng một tên phát hành.
 Validity Period: gồm hai giá trị chỉ định khoảng thời gian mà giấy chứng nhận có
hiệu lực: not-before và not-after. Not-before: thời gian chứng nhận bắt đầu có
hiệu lực; Not-after: thời gian chứng nhận hết hiệu lực.
Các giá trị thời gian này được đo theo chuẩn thời gian Quốc tế, chính xác đến
từng giây.

lật tẩy. Trong mô hình hạ tầng khóa công khai thì T chính là nhà cung cấp chứng số (CA
– Certificate Authority).
1.3.2. Sử dụng chứng thực số
Chương 1. Những vấn đề của an toàn thông tin hiện đại
Khi áp dụng chứng thực số ở quy mô lớn, có rất nhiều CA cùng hoạt động. Vì vậy
một cá thể A có thể không quen thuộc (không đủ tin tưởng) với CA của một cá thể B
khác. Do đó chứng thực của B có thể phải bao gồm chữ ký của CA ở mức cao hơn. Quá
trình này dẫn đén việc hình thành một mạng lưới quan hệ phức tạp và phân tầng giữa
các CA. Trong tiêu chuẩn X.509 về hệ thống hạ tầng khóa công khai, mạng lưới CA tạo
thành cây từ trên xuống với gốc là một CA trung tâm mà không cần được chứng thực
bởi một bên thứ 3 nào khác.
Cũng giống như giấy CMND, một chứng thực điện tử cũng có thời hạn lưu hành
nhất định, và có thể bị thu hồi trước thời han. Một chứng thực số có thể bị thu hồi nếu
như chìa khóa bí mật (cùng cặp với chìa khóa công khai của nó) đã bị lộ, hoặc mối liên
hệ giữa khóa công khai và chủ thể sở hữu đã thay đổi. Điều này có thể xảy ra ở mức độ
không thường xuyên, nhưng người sử dụng phải luôn kiểm tra tính pháp lý của chứng
thực số mỗi khi sử dụng. Việc kiểm tra có thể thực hiện bằng cách so sánh chứng thực
với danh sách các chứng thực bị thu hồi (Certificate Revocation List – CRL). Việc đảm
bảo danh sách này luôn chính xác và được cập nhật kịp thời là chức năng cơ bản của hạ
tầng khóa công khai tập trung [13].
1.3.3. Các chức năng cơ bản của CA
Hình 1.4: Các chức năng của hệ thống CA [13]
Cấp phát chứng thực [13]
Chương 1. Những vấn đề của an toàn thông tin hiện đại
Cấp phát chứng thực là nhiệm vụ đầu tiên của một CA. Công việc này được thực
hiện trên cơ sở một yêu cầu được đưa ra từ phía người dùng. Trong các hệ thống không
lớn lắm, các yêu cầu này được trực tiếp gửi cho CA để trực tiếp xử lý, còn với các hệ
thống lớn thường có thêm một khâu trung gian (đăng ký – registration) nhận yêu cầu từ
phía người dùng chuyển cho CA và nhận chứng thực từ CA trả về cho người dùng. Để
tạo ra một chứng thực số, CA phải sinh được một cặp chìa khóa phi đối xứng có độ an

giới thám mã. Nước ta đã đưa ra chuẩn chữ ký số, trong đó RSA được sử dụng như một
hệ mã chuẩn trong một thời gian dài sắp tới. Việc sinh khóa trong hệ mã RSA về thực
chất là tạo ra một cặp số lớn
qp,
là các số nguyên tố mạnh. Để sinh được một cặp số
nguyên tố như vậy, chúng ta phải tìm hiểu các lý thuyết toán học có liên quan đến số
nguyên tố, số giả nguyên tố như: các định lý của số nguyên tố, kiểm tra số nguyên tố và
số giả nguyên tố, và cách kiểm tra số giả nguyên tố mạnh sẽ được đề cập ở chương tiếp
theo.
Chương 2. Một số công cụ toán học liên quan
Chương 2. Một số công cụ toán học liên quan
2.1. Số nguyên tố và hệ mã khóa công khai RSA
2.1.1. Hệ mã khóa công khai RSA
Trước khi đi vào các lý thuyết toán học có liên quan đến việc sinh, kiểm tra số
nguyên tố để làm khóa cho CA, ta tìm hiểu kỹ hơn về hệ mã RSA được ứng dụng trong
hệ thống chứng thực số.
Hệ mã đối xứng và hệ mã phi đối xứng [1]
Khái niệm mã đối xứng được dùng để chỉ các hệ mã mà trong đó, khi biết khóa lập
mã, ta có thể tìm ra khóa giải mã, đồng thời, việc giải mã cùng đòi hỏi thời gian như
việc lập mã. Cho đến những năm cuối của thập niêm 70 của thế kỉ 20, người ta mới chỉ
biết đến một loại mã như vậy. Đối với các hệ mã này, cần phải giữ bí mật khóa lập mã,
vì để lộ nó cũng tức là để lộ cách giải mã. Do đó, chỉ những người hoàn toàn chia sẻ
mọi thông tin mật với nhau mới có thể trao đổi với nhau bằng mật mã. Điều này giải
thích nguyên nhân của việc cho đến rất gần đây mật mã thường chỉ được dùng trong
quân sự, ngoại giao, tức là khi những đối tượng cần trao đổi thông tin mật với nhau là
khá it, hơn nữa, lại cùng chung quyền lợi nên sẵn sàng bảo vệ bí mật cho nhau trong quá
trình trao đổi thông tin.
Sự phát triển của xã hội dẫn đến việc ngày nay mật mã không những chỉ được
dùng trong bí mật quân sự và ngoại giao, mà còn dùng, và có thể chủ yếu là dùng trong
bí mật kinh tế, tài chính, thương mại. Vì thế xuất hiện những đòi hỏi mới đối với các hệ

là số
nghịch đảo của
e
modulo
)(n
φ
. Số
n
là tích của hai số nguyên tố rất lớn
qp,
nào đó,
qpn .=
, còn
e
được chọn là số nguyên tố cùng nhau với
)(n
φ
, trong đó
)(n
φ
là giá trị
hàm Euler của
n
. Để mã hóa một thông báo, trước tiên ta chuyển nó sang dạng số và
nhóm thành các khối với độ dài lớn nhất có thể (tùy thuộc khả năng tính toán và tốc độ
yêu cầu) với một số chẵn chữ số. Để mã hóa một khối
P
trong văn bản, ta tính
)(mod:)( nPCPE
e

,
khi
1),( =nP
. Chú ý rằng, xác suất để
P
và
n
không nguyên tố cùng nhau là hết sức
nhỏ, vì điều này chỉ có thể xảy ra khi
P
là bội của
p
hoặc
q
. Thông thường
P
chỉ là
những “khối văn bản” có độ dài không lớn, nói chung là nhỏ hơn hẳn
p
và
q
, cho nên
điều kiện
1),( =nP
là luôn xảy ra, và công thức trên cho thấy việc giải mã một khối
trong văn bản mật cũng chính là việc nâng lên lũy thừa bậc
d
rồi rút gọn theo modulo
n
. Cặp

Chương 2. Một số công cụ toán học liên quan
Từ các công thức đó để tìm được
p
và
q
thì với khả năng của con người, thậm chí là
máy tính có tốc độ xử lý cao là không thể.
Độ an toàn của RSA [1]
Nếu ta chọn các số
p
và
q
khoảng 100 chữ số thập phân, thì
n
sẽ có khoảng 200
chữ số thập phân. Để phân tích một số nguyên cỡ lớn như thế, với các thuật toán nhanh
nhất hiện này và với những máy tính hiện đại nhất, ta mất hàng tỷ năm!
Sau khi tìm ra hệ mã, Rivesst, Shamir và Adleman có viết một bài báo công bố
phát minh dưới dạng một thông báo khoa học của MIT và, trên cột Martin Gardner’s
của tờ báo Scienfitic American, họ có đưa ra lời thách thức bạn đọc bẻ khóa một mẩu
tin nhỏ đã được mã hóa với:
n=114381625757888867669235779976146612010218296721242362562561842935706
935245733897830597123563958705058989075147599290026879543541
e = 9007.
Mẩu tin
“first solver wins one hundred dollars”
xuất hiện trong dạng mã hóa (với A = 01, B=02, C=03 …) chỉ được giải mã vào ngày
26/4/1994, bằng một cố gắng tổng lực mang tính quốc tế (qua Internet) với việc sử dụng
1600 workstations, mainframes, và supercomputers tấn công trong 8 tháng liên tục để
phân tích số nêu trên ra thừa số nguyên tố.

ngoài 1 và chính nó. Số nguyên lớn hơn 1 không phải là số nguyên tố được gọi là hợp
số.
Chương 2. Một số công cụ toán học liên quan
Các Định lý về số nguyên tố [2]
Mọi hợp số
n
đều có ước nguyên tố nhỏ hơn
n
.
Mọi số nguyên tố lớn hơn 1 đều phân tích được một cách duy nhất thành tích các
số nguyên tố, trong đó các thừa số được viết với thứ tự không giảm.
Định lý số nguyên tố được Gauss phát biểu năm 1773:
Với mỗi số thực dương
x
cho trước, ta ký hiệu
)(x
π
là số các số nguyên tố không
vượt quá x. Khi đó, ta có:
1
log
/)(
lim
=
∞→
x
x
x
x
π

φ
.
Rõ ràng, khi
p
là số nguyên tố thì mọi số tự nhiên bé hơn nó đều là nguyên tố
cùng nhau với nó và do đó ta có
1)( −= pp
φ
. Tổng quát hơn, khi
p
là số nguyên tố và
r
là một số tự nhiên bất kỳ thì
)/11()1()(
1
ppppp
rrr
−=−=
−
φ
.
Có thể chứng minh được rằng khi
nm,
là các số nguyên tố cùng nhau thì ta có
)().().( nmnm
φφφ
=
và do đó để tính
φ
của một số tự nhiên nào đó người ta phân tích nó ra các thừa số

ΖΖ m/
(
Z
là tập các số nguyên) và chứa đúng
m
phần tử. Mỗi lớp trong tập
ΖΖ m/
có đúng 1 số nằm trong đoạn
]1,0[ −m
, cho nên mỗi số nguyên trong đoạn này
được xem “đại diện” của một lớp.
Một số tính chất của phép tính đồng dư:
Chương 2. Một số công cụ toán học liên quan

)(modmaa ≡
;
 Nếu
)(modmba ≡
thì
)(modmab ≡
;
 Nếu
)(modmba ≡
và
)(modmcb ≡
thì
)(modmca ≡
;
 Nếu
)(modmba ≡

1−
x
, hay
x/1
.
Định lý Fermat (bé)[2]: Nếu
p
là một số nguyên tố còn
a
là một số nguyên thì
)(mod paa
p
≡
. Nếu
a
không chia hết cho
p
(tức là
0)(mod ≠pa
) thì
)(mod1
1
pa
p
≡
−
.
Ví dụ. Dễ dàng thấy rằng
)7(mod44
7

và số nguyên bất kỳ
a
người ta ký hiệu
pa
p
a
paL
p
mod:),(
2
1−
=






=
Và chỉ ra rằng
),( paL
sẽ bằng 0 khi
a
chia hết cho
p
, bằng 1 khi
a
là một thặng dư
bình phương
)(mod p

1 k
paxLxpaLnaJ =
.
Như vậy trong trường hợp riêng khi
n
là số nguyên tố thì ký hiệu Jacobi trùng với ký
hiệu Legendre.
2.2. Việc tính toán số nguyên tố và khái niệm số giả nguyên tố. Kiểm tra số
giả nguyên tố mạnh.
Chương 2. Một số công cụ toán học liên quan
2.2.1. Thuật toán kiểm tra số nguyên tố thông thường và khái niệm số giả nguyên
tố
Thuật toán: Sàng Eratosthenes [2]
Để kiểm tra
n
có phải là số nguyên tố hay không, ta thực hiện phép chia cho tất cả
các số nguyên tố không vượt quá
n
.
Độ phức tạp: Theo định lý số nguyên tố của Gauss, số các số nguyên tố không vượt quá
n
là vào khoảng
n
n
n
n
log
2
log
=

. Do đó nếu tồn tại số
b
sao cho
)(mod nbb
n
≠
thì
n
phải là hợp số. Như
vậy, nếu một số nguyên thỏa mãn các giả thiết của định lý Fermat bé thì “có nhiều khả
năng” nó là một số nguyên tố! Ta có định nghĩa sau:
Giả sử
b
là một số nguyên dương. Nếu
n
là hợp số nguyên dương và
)(modnbb
n
≡
, thì
n
được gọi là số giả nguyên tố cơ sở
b
.
Nói chung các số giả nguyên tố ít hơn nhiều so với các số nguyên tố. Chẳng hạn,
có tất cả 455052512 số nguyên tố bé hơn
10
10
, nhưng chỉ có 14884 số giả nguyên tố cơ
sở 2 trong khoảng đó. Sự kiện này giải thích cách nói ở trên: Các số thỏa mãn định lý

j
nào đó,
10 −≤≤ sj
.
Số nguyên
n
được gọi là giả nguyên tố mạnh cơ sở
b
nếu nó là hợp số và trải qua
được kiểm tra Miller cơ sở
b
.
Chương 2. Một số công cụ toán học liên quan
Cách làm trên có thể kiểm tra nguyên tố những số không lớn lắm. Đối với những
số lớn, ta có thể dùng thuật toán xác suất dựa trên định lý :
Nếu
n
là một hợp số dương lẻ thì tồn tại không quá
4
1−n

b
,
11 −≤≤ nb
, sao cho
n
trải qua được kiểm tra Miller đối với các cơ sở đó.
Từ định lý trên suy ra rằng, nếu số
b
được chọn ngẫu nhiên trong khoảng

toán xác suất sau:
Thuật toán Miller-Rabin [9], [11]
RGB là bộ sinh bít ngẫu nhiên
Input:
1.
w
The odd integer to be tested for primality. This will be
either
p
or
q
, or one of the auxiliary primes
121
,, qpp

or
2
q
.
2.
iterations
The number of iterations of the test to be performed; the
value shall be consistent with Table 3 or 4.
Output:
1.
status
The status returned from the validation procedure, where
status is either PROBABLY PRIME or COMPOSITE.
Process:
1. Let

wb
.
4.2 If
))1()1(( −≥≤ wborb
, then go to step 4.1.
4.3
wbz
m
mod=
.
4.4 If
))1()1(( −== wzorz
, then go to step 4.7.
4.5 For
1=j
to
1−a
do
4.5.1
wzz mod
2
=
.
4.5.2 If
)1( −= wz
, then go to step 4.7.
4.5.3 If
)1( =z
, then go to step 4.6.
4.6 Return COMPOSITE.