TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
_______________________________

BÀI TẬP LỚN
LÝ THUYẾT MÃ HÓA THÔNG TIN
Đề tài:
BÀI TOÁN SỐ NGUYÊN TỐ VÀ CÁC PHƯƠNG PHÁP
PHÂN TÍCH RA THỪA SỐ NGUYÊN TỐ

Sinh viên thực hiện:

Trịnh Xuân Hinh
Trần Hậu Tin
Phạm Văn Thành
Nhóm 5
Lớp KHMT1-K4

Giảng viên hướng dẫn: Ths. Mai Thanh Hồng

Hà Nội, 5/2013


MỤC LỤC
MỤC LỤC........................................................................................................................... 2
LỜI NÓI ĐẦU..................................................................................................................... 1
CHƯƠNG I: TỔNG QUAN LÝ THUYẾT VÀ MÃ HÓA THÔNG TIN....................................2
I.Lý thuyết thông tin.........................................................................................................2
CHƯƠNG II: SỐ NGUYÊN TỐ VÀ CÁC PHƯƠNG PHÁP PHÂN TÍCH RA THỪA SỐ
NGUYÊN TỐ...................................................................................................................... 7
Kết Luận........................................................................................................................... 21

xét hình thức liên lạc phổ biến nhất của con người: ngôn ngữ. Hai yếu tố quan
trọng của một ngôn ngữ ngắn gọn là: các từ thông dụng (như "một", "cái", "tôi")
nên ngắn gọn hơn các từ kém thông dụng hơn (như "thông tin", "thợ thủ công") để
các câu không bị quá dài. Sự cân bằng độ dài các từ như vậy cũng tương tự như
trong nén dữ liệu và là một thành phần cơ bản của mã hóa nguồn. Ngoài ra, nếu
một phần của câu không nghe được hoặc bị nghe nhầm do tiếng ồn, chẳng hạn như
do có ô tô chạy qua, thì người nghe vẫn có thể đoán ra ý nghĩa của câu. Sự vững
chắc đó là một thành phần thiết yếu cho hệ thống liên lạc điện tử cũng như cho
ngôn ngữ. Tính chất đó trong truyền thông được đảm bảo bởi mã hóa kênh. Mã hóa
nguồn và mã hóa kênh là những mối quan tâm chính của lý thuyết thông tin.

1. Entropy
Lý thuyết thông tin được định nghĩa là khối lượng thông tin trong một thông báo
như là số bít nhỏ nhất cần thiết để mã hoá tất cả những nghĩa có thể của thông báo
đó.
Ví dụ, trường ngay_thang trong một cơ sở dữ liệu chứa không quá 3 bít
thông tin, bởi vì thông tin tại đây có thể mã hoá với 3 bít.

0

= Sunday

1

= Monday

10 = Tuesday
11 = Wednesday
100 = Thursday
101 = Friday

độ tuyệt đối.

3.

An toàn của hệ thống mã hoá

Shannon định nghĩa rất rõ ràng, tỉ mỉ các mô hình toán học, điều đó có nghĩa là hệ
thống mã hoá là an toàn. Mục đích của người phân tích là phát hiện ra khoá k, bản
rõ p, hoặc cả hai thứ đó. Hơn nữa họ có thể hài lòng với một vài thông tin có khả
năng về bản rõ p nếu đó là âm thanh số, nếu nó là văn bản tiếng Đức, nếu nó là
bảng tính dữ liệu, v. v . . .
Trong hầu hết các lần phân tích mã, người phân tích có một vài thông tin có khả
năng về bản rõ p trước khi bắt đầu phân tích. Họ có thể biết ngôn ngữ đã được mã
hoá. Ngôn ngữ này chắc chắn có sự dư thừa kết hợp với chính ngôn ngữ đó. Nếu nó
là một thông báo gửi tới Bob, nó có thể bắt đầu với "Dear Bob". Chắc chắn là "Dear
Bob " sẽ là một khả năng có thể hơn là chuỗi không mang ý nglĩa gì chẳng hạn
"tm*h&rf". Mục đích của việc thám mã là sửa những tập hợp khả năng có thể có
của bản mã với mỗi khả năng có thể của bản rõ.
Có một điều giống như hệ thống mã hoá, chúng đạt được sự bí mật tuyệt đối. Hệ
thống mã hoá này trong đó bản mã không mang lại thông tin có thể để tìm lại bản
3


rõ. Shannon phát triển lý thuyết cho rằng, hệ thống mã hoá chỉ an toàn tuyệt đối nếu
nếu số khoá có thể ít nhất là nhiều bằng số thông báo có thể. Hiểu theo một nghĩa
khác, khoá tối thiểu dài bằng thông báo của chính nó.
Ngoại trừ an toàn tuyệt đối, bản mã mang lại một vài thông tin đúng với bản rõ, đ
iều này là không thể tránh được. Một thuật toán mật mã tốt giữ cho thông tin ở mức
nhỏ nhất, một người thám mã tốt khai thác những thông tin này để phát hiện ra bản
rõ.

thông số liệu trên các kênh truyền có độ nhiễu cao (noisy channels)), dùng những
phương pháp tinh xảo khiến phần lớn các lỗi xảy ra có thể được chỉnh sửa. Nó còn
4


xử lý những đặc tính của mã (codes)), và do vậy giúp phù hợp với những ứng dụng
cụ thể.
Có hai loại mã hiệu:
1. Mã hóa dùng nguồn (Mã hóa entrôpi (Entropy encoding))
2. Mã hóa trên kênh truyền (Sửa lỗi ở phía trước (Forward error correction))

Cái đầu tiên chúng ta nói đến là mã hóa dùng nguồn. Ý định của phương pháp này
là nén dữ liệu từ chính nguồn của nó, trước khi truyền đi, giúp cho việc truyền
thông có hiệu quả hơn. Chúng ta chứng kiến thói quen này hằng ngày trên Internet,
nhất là trong cách dùng "zip" nén dữ liệu để giảm lượng dữ liệu phải truyền, giảm
nhẹ gánh nặng cho mạng lưới truyền thông, đồng thời thu nhỏ cỡ tập tin. Cái thứ hai
là mã hóa trên kênh truyền. Bằng việc cộng thêm những bit mới vào trong dữ liệu
được truyền, còn gọi là bit chẵn lẻ (parity bits), kỹ thuật này giúp cho việc truyền
thông tín hiệu chính xác hơn trong môi trường nhiễu loạn của kênh truyền thông.
Có nhiều chương trình ứng dụng, mà người dùng trung bình không để ý đến, sử
dụng mã hóa trên kênh truyền. Kỹ thuật Reed-Solomon được dùng để nhằm sửa lỗi
do những vết xước và bụi trên bề mặt đĩa âm nhạc CD thông thường. Trong ứng
dụng này, kênh truyền thông lại chính là bản thân cái đĩa CD. Điện thoại di động
"Cell phones" cũng dùng kỹ thuật mã hóa có hiệu ứng cao (powerful coding
technique) để sửa các lỗi trong việc truyền sóng rađiô ở tần số cao bị yếu mờ và bị
nhiễu. Modem xử lý số liệu, việc truyền thông qua đường điện thoại, và đương
nhiên ngay cả chính NASA, tất cả đều sử dụng kỹ thuật mã hóa trên kênh truyền
hiệu ứng để truyền những bit số liệu qua đường dây.
Lý thuyết toán học.



Số nguyên tố là một số lớn hơn 1, nhưng chỉ chia hết cho 1 và chính nó, ngoài ra
không còn số nào nó có thể chia hết nữa. Số 2 là một số nguyên tố. Do vậy 7, 17,
53, 73, 2521, 2365347734339 cũng là số nguyên tố. Số lượng số nguyên tố là vô
tận. Hệ mật mã thường sử dụng số nguyên tố lớn cỡ 512 bits và thậm chí lớn hơn
như vậy.
+ Ước số chung lớn nhất.

Hai số gọi là cặp số nguyên tố khi mà chúng khôn g có thừa số chung nào khác 1,
hay nói một cách khác, nếu ước số chung lớn nhất của a và n là bằng

1.

Chúng ta có thể viết như sau : gcd(a,n)=1

Số 15 và 28 là một cặp số nguyên tố, nhưng 15 và 27 thì không phải cặp số nguyên
tố do có ước số chu ng là 1 và 3, dễ dàng thấy 13 và 500 cũng là một
cặp số nguyên tố. Một số nguyên tố là một cặp số nguyên tố với tất cả những số
khác loại trừ những số là bội số.
Một cách dễ nhất để tính toán ra ước số chung lớn nhất của hai số là nhờ vào
thuật toán Euclid. Knuth mô ả thuật toán và một vài mô hình của thuật toán đã
được sửa đổi.
Định lý fermat nhỏ: cho p là số nguyên tố a là số nguyên dương không chia hết cho
p. Khi đó ta có:
ap-1≡ 1 mod p
Từ định nghĩa Fermat ta có các hệ quả:
Cho a € z và p là số nguyên tố thì ap= a mod p.
Nếu e , d nguyên dương và thỏa mãn điều kiện ed≡1(mod p-1) thì (a e)d=(ad)e=a mod
p
6


ước của a, thì a 2 ≡ 1(mod 3) , từ đây ta có a 560 ≡ 1(mod 3) , hay a 561 ≡ a (mod 3) . Tương
tự kiểm tra đối với hai số 11 và 17.
Như vậy việc kiểm số nguyên tố theo Fermat là có khuyết điểm.

Các bước kiểm tra tính nguyên tố như sau:
7


1. Chọn ngẫu nhiên a từ tập {1,2,..., n − 1} và kiểm tra điều kiện UCLN(a,n)=1
2. Nếu như điều kiện trên không thỏa mãn thì n là hợp số
3. Kiểm tra đẳng thức (2)
4. Nếu như đẳng thức (2) không thỏa mãn thì trả lời n là hợp số
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ố
Đầu vào: n: giá trị để kiểm tra tính nguyên tố; k: tham số tham gia vào quá trình
kiểm tra .
Đầu ra: hợp số nếu n là hợp số, nếu không nguyên tố xác suất
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
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.
Định nghĩa : 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ặc chẽ trong cơ sỡ a, a ∈ N , nếu như UCLN (a, n) = 1 hoặc
a d ≡ 1(mod n) , hoặc


a2

s −1

d

≡ −1(mod n) , thì chúng ta dừng, nếu như a 2

≡ ±1(mod n) . Nếu như
s −1

d

≡ 1(mod n) , thì chúng

ta lại khai căn cho đến khi tìm được a d hay căn đó đồng dư với -1.
Để kiểm tra tính nguyên tố của các số lẻ n, 7 < n < 25.109 , ta dùng quá trình như
sau:
Bước 1: Kiểm tra tính chặc chẽ giả nguyên tố của n trong cơ sở 2,3,5,7. Nếu n
không là chặt chẽ giả nguyên tố một trong các cơ sở đó thì n là hợp số.
8


Bước 2: Nếu n=3215031751, thì n là hợp số, ngược lại n là số nguyên tố.
Như vậy chúng ta thấy việc kiểm tra trên cơ sỡ tính chặc 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. Trong một số kết quả chứng tỏ rằng, điều kiện cần và đủ để
kiểm tra số nguyên tố là n < (67107840) 2 .
2.



22(n-1)/2=22128≡1mod (257)
2264 ≡ 1 (mod 257)
2232 ≡ -1 (mod 257)
Với b=17
17(n-1)/2=17128≡1mod (257)
1764 ≡ 1 (mod 257)
1732 ≡ 1 (mod 257)
1716 ≡ -1 (mod 257)
Với b=4
4(n-1)/2=4128≡1mod (257)
464 ≡ 1 (mod 257)
432 ≡ 1 (mod 257)
416 ≡ 1 (mod 257)
48 ≡ 1 (mod 257)
44 ≡ -1 (mod 257)
Khi một số nguyên dương không vượt qua được phép thử Miller thì chắc chắn nó là
hợp số, nhưng khi nó vượt qua được phép thử Miller thì chưa chắc nó đã là số
nguyên tố. Tuy nhiên không một hợp số nào có thể vượt qua mọi phép thử Miller
với các cơ sở khác nhau.
Mệnh đề 2: giả sử n là một hợp số dương lẻ thì n sẽ không thể vượt qua 75% các cơ
sở b,1≤b≤n
3.

Phép thử Rabin-Miler

Theo mệnh đề 2 ở phép thử Miller cho ta ước lượng xác suất một số nguyên có
nguyên tố hay không, như vậy khi một số nguyên tố lớn vượt qua phép thử Miller
với 1 cơ sở b nào đó giữa n và n-1 thì ta có thể nói là hơn 75% n là số nguyên tố.

− 1

)2, với

k=1,2,...,s và xs = a p −1 .
Từ định lý Fermat nhỏ:
a p −1 ≡ 1(mod p )

Hay
xs ≡ 1(mod p)

Hay
xs2−1 ≡ 1(mod p)

Do đó hoặc xs −1 ≡ 1(mod p ) hoặc xs −1 ≡ −1(mod p) . Nếu xs −1 ≡ −1(mod p) ta dừng
lại, còn nếu ngược lại ta tiếp tục với xs − 2.
Sau một số hữu hạn bước ta có: hoặc ta có một chỉ số k, 0 ≤ k ≤ s − 1 sao cho
xk ≡ −1(mod p) , hoặc tới k=0 ta vẫn có xk ≡ 1(mod p ) .

Ta có mệnh đề Q(p,a) như sau: Nếu p là số nguyên tố lẻ và p - 1 = 2 s ⋅ m thì với
k

mọi a: 0

a 2 m ≠ −1(mod n)
Với 0 ≤ i ≤ s − 1
Theo định lý Fermat ta có

a2

s

Khi đó

a2

s −1

m

có a 2

m

≡1(mod n)

a2

s −1

m

là căn bậc 2 của 1 modulo n, theo bổ đề ta có hoặc

s −1

m

≡ 1(mod n)

Và lặp lại lập luận trên, cuối cùng ta có:
12


a m ≡ 1(mod n)
Điều này là mâu thuẫn.
Xác suất trả lời sai:
Định lý: nếu n là hợp số dương lẻ thì trong các số a ∈ {2,..,n-1} tồn tại không quá
n −1
cơ sở a để n là số giả nguyên tố mạnh Fermat.
4

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).
Theo định lý trên nếu n là hợp số thì khả năng kiểm tra này trả lời TRUE xảy ra
với xác suất không vượt quá

1
1
, nghĩa là P(B|A) ≤ . Tuy nhiên để tính xác suất sai
4
4


P( A | B) =

P ( B | A) ⋅ (ln n − 2)
P ( B | A) ⋅ (ln n − 2) + 2

Kiểm tra Miller-Rabin lặp:
Theo công thức tính xác suất sai trên đây, với n lớn (cỡ 130 chữ số thập phân),
nếu thực hiện phép thử Miller-Rabin chỉ một lần, xác suất sai là khá lớn, tới trên
90%. Để giảm xác suất sai, ta lặp lại phép thử k lần với k số ngẫu nhiên a khác
nhau, nếu n vượt qua 50 lần thử thì P(B|A) ≤

1
, khi thay vào công thức với 50 lần
4k
13


thử nếu cả 50 lần, phép thử đều "dương tính" thì xác suất sai giảm xưống chỉ còn là
một số rất nhỏ không vượt quá 9 ⋅10 −29 .
4.

Kiểm tra bằng Solovay-Strasen

Xem tiêu chuẩn Euler là mệnh đề Q(p,a). Khi đó Q(p,a) đúng với mọi số nguyên
tố p và mọi số tự nhiên a, 1 ≤ a < p . Thay số nguyên tố p bằng số lẻ n ta định nghĩa:
Hợp số n được gọi là số giả nguyên tố Euler cơ sở a(1 ≤ a < n ) nếu:
a
( n−1) / 2
(mod n) .
 ≡a

n −1
2

≠ ±1(mod n) . Rõ ràng rằng, tồn

α
tại α i ≥ 2 . Theo định lý về phần dư trung hoa, có thể tìm được b ∈ N , b(mod pi ) i

α
là căn nguyên thủy trong Z p , còn khi j ≠ i, b ≡ 1(mod p j ) . Nếu như b n−1 ≡ 1(mod n) ,
j

αi
i

α
α
α −1
thì b n−1 ≡ 1(mod pi ) , từ đây n − 1φ ( pi ) = pi ( pi − 1) , điều này là không thể bởi vì ni

i

i

1 không chia hết cho pi .
Bây giờ giả sử rằng n = p1 ... pk . Chúng ta tìm số b ∈ N , sao cho b(mod p1 ) -là căn
nguyên thủy trong Z p , và b ≡ 1(mod p j ) khi j>1. Khi đó UCLN (b, n) = 1 và
1

 b   b   b   b 

n


n −1


a
W2 = a | 1 ≤ a ≤ n − 1,UCLN ( a, n) = 1, a 2 ≠  (mod n) ,
n



 a1a2   a1  a 2 
 =    . Cho nên đối
 n   n  n 

Nếu như a1 ∈ W1 , a2 ∈ W2 , thì a1a 2 ∈ W2 , bởi vì 

với số a ∈ W1 , thặng dư không âm nhỏ nhất của a(mod n) thuộc W2 . Dẫn đến ,
| W2 |≥| W1 | , từ đây rút ra điều khẳng định của định lý.

Giải thuật kiểm tra Solovay-Strasen
Đầu vào: n: là số tự nhiên lẻ
Đầu ra: FALSE nếu n là hợp số, nếu không TRUE
1. Chọn a ngẫu nhiên trong khoảng[1,n-1]
a
n

2. Tính ký hiệu Jacobi J=  
3. Tính x =a(n − 1) / 2(mod n)

(b) p + 1 có một thừa số lớn là s.
(c) r – 1 có một thừa số nguyên tố lớn là t.
15


Thuật toán Gordon:
(1) Phát sinh ngẫu nhiên hai số nguyên tố s và t đủ lớn có số ký số tương đương.
(2) Chọn một số nguyên dương i* và tìm số nguyên r=2it+1, với i= i*, i*+1,
i*+2,... đầu tiên vượt qua phép thử Rabin-Miller.
(3) Tính z = sr-1 mod r.
(4) Tính p*= 2zs-1.
(5) Chọn một số nguyên k*, sau đó tìm số nguyên p= p*+2krs, với k = k*,
k*+1, k*+2,... đầu tiên vượt qua phép thử Rabin- Miller.
(6) Reaturn p.
Mệnh đề: p tìm được theo thuật toán Gordon là một số nguyên tố mạnh,
Chứng minh: theo định lý Fermat nhỏ, ta có sr-1≡ 1(mod r).
Vậy: p*=2zs -1 ≡ 2sr-2*s-1 ≡ 2*1-1≡ 1 (mod r) và
p*=2zs -1≡ -1 (mod r)
Từ đó ta có:

III.

(a) p – 1 = p* +2krs -1 ≡ 0(mod r) -> r= 2it+1 là một thừa số nguyên tố lớn của
p-1
(b) p+1 = p* + 2krs+1≡0(mod r) -> s là một thừa số nguyên tố lớn của p+1.
(c) r-1 = 2it≡0(mod t)-> t là một thừa số nguyên tố lớn của r-1
Một Số Thuật Toán Phân Tích Ra Thừa Số Nguyên Tố
1. Phương pháp Fermat:

Cho n là số nguyên dương lẻ. Giả sử

Tiến trình trên đảm bảo dừng do m không thể vượt quá (n+1)/2. Thực vậy:
((n+1)/2)2 – n=((n-1)/2)2
Và tất cả các số hàng của biểu thức này đều là các số nguyên.
Ví dụ với n = 11
Bắt đầu với m = 4 > √11≈ 3.32 và xét dãy sau:
42-11=16-11=5
52-11=25-11=14
62-11=36-11=25=52
Vậy: 11= 62-52=(6+5)(6-5)=11×1.
Hạn chế:
-

Tuy nhiên phương pháp này hiệu quả nhất khi n là tích của hai số nguyên tố
gần nhau. Đây là kẽ hở để có thể bẻ khóa một số hệ mã (như RSA chẳng
hạn).

-

Mặc dù vẫn giải quyết được việc phân tích số n ra thừa số nguyên tố nhưng
phương pháp Fermat không hiệu quả .Thậm chí phương pháp này còn tệ hơn
phương pháp chia thử, vì chia thử chỉ thử với tối đa tới √n nhưng fermat thì
có trường hợp phải thử tới (n+1)/2-√n số nguyên. khi n rất lớn, tới (n+1)/2√n càng lớn hơn √n.

2. Phương pháp Monte- Carlo:

17


Mô tả thuật toán:
Cho n là một hợp số và p là ước nguyên tố nhỏ nhất của n.

(p-1) là ước số của k! nào đó. Khi ấy, (p-1) là tích của toàn số nguyên tố nhỏ, thì k
sẻ không quá lớn, và k! có thể tính được.
Theo định lý Fermat nhỏ, ta có:
2p-1≡1(mod p)
Và do (p-1)|k!, tồn tại q sao cho k!=(p-1)q. kết quả là:
2k!=2(p-1)q(2p-1)q≡1q=1(mod p)
Nghĩa là p|(2k!-1).
Đặt Z =2k!-1 mod n
Nếu n|(2k!-1) ta có:
Z=(2k!-1)-ni với i nguyên dương
Ta có p|Z vì là ước của cả 2 k!-1 lẫn n. Như thế ta có thể tìm được một ước số của n
bằng cách tính gcd(Z,n). Z và n sẽ không nguyên tố cùng nhau, nghĩa là
gcd(Z,n)=d>1, vậy d là 1 ước không tầm thường của n
Nếu n|(2k!-1) phương pháp Rho sai vì ta sẽ có Z≡0 (mod n) và gcd(Z,n)=gcd(0,n)=n
Trong trường hợp n có các thừa số nguyên tố lớn, ta sẽ chọn một sơ sở b>2 khi tính
bk!-1.
Ví dụ: n= 632887
Chọn cơ sở b=261482. Ta tạo dãy ri≡bi!(mod n), i= 1,2,3,... cho đến khi gcd(r i-1,n)
không tầm thường như sau:
r1 = 261482 (mod 632887)
r2 = r12= 155053(mod 632887); gcd(r2-1,n)=1
r3= r23= 386889(mod 632887); gcd(r3-1,n)=1
r4 = r34= 181843(mod 632887); gcd(r4-1,n)=1
r5 = r45= 293943(mod 632887); gcd(r5-1,n)=1
r6 = r56= 630444(mod 632887); gcd(r6-1,n)=1
r7 = r67= 249467(mod 632887); gcd(r7-1,n)=1
r8 = r78= 234544(mod 632887); gcd(r8-1,n)=1
r9 = r89= 422180(mod 632887); gcd(r9-1,n)=1
r10 = r910= 582903(mod 632887); gcd(r10-1,n)=769
19

22