Hình 4.14. Phân tích modulus của rabin với một chơng trình con
giải mã cho trớc.
Bởi vậy giá trị x sẽ thu đợc ở bớc 3. Tiếp theo xét bớc 4. Nhận thấy
rằng x
1
2
= r
2
(mod n). Điều đó dẫn tới x
1
r (mod n) hoặc x
1
wr
(mod n), trong đó w là một trong các căn bậc hai không tầm thờng của
1 modulo n. Trong trờng hợp thứ hai ta có :
n(x
1
-r

)(x
1
+r)
song n không phải là ớc của một thừa số nào ở vế phải. Bởi vậy, việc
tính UCLN(x
1
+r,n)(hoặc UCLN(x
1
-r, n)) phải dẫn tới hoặc p hoặc q,
và nh vậy phép phân tích n đợc hoàn thành.
Ta sẽ tính xác suất thành công của thuật toán này trên tất cả (n-
1) phép chọn ngẫu nhiên r. Với hai thặng d khác không r

~ r
3
thì r
1
~ r
3
. Điều đó cho ta thấy rằng quan hệ ~ là một
quan hệ tơng đơng. Các lớp tơng đơng của Z
n
\{0} đều có bốn phần tử,
lớp tơng đơng chứa r là tập
[r] = {r, wr (mod n)}
trong đó w là căn bậc hai không tầm thờng của 1 modulo n.
1. Chọn một số ngẫu nhiên r , 1 r n-1
2. Tính y = r
2 -
B
2
/4 mod n
3. Gọi chơng trình con A(y) để tìm bản giải
mã x
4. Tính x
1
= x+B/2
5. If x
1
r (mod n) then quit (không thành
công)
Else UCLN(x
1

12
thì đây là một
phơng pháp phân tích thừa số hợp lý một cách hoàn hảo, tuy nhiên với
n lớn hơn nói chung ta phải dùng các kỹ thuật tinh tế hơn.
[ ]
n
4.8.1. Phơng pháp p-1
Thuật toán p-1 của Pollar (đa ra vào năm 1947) là một thí dụ về
một thuật toán đơn giản đơn khi đợc áp dụng với các số nguyên lớn.
Thuật toán này (trình bày trên hình 4.15) có hai đầu vào: số nguyên lẻ
n cần đợc phân tích và một cận B. Có thể mô tả thuật toán nh sau:
Hình 4.15. Thuật toán phân tích thừa số p-1.
Giả sử p là ớc mhuyên tố của n và q B , với mỗi mũ nguyên tố
p(p-1). Khi đó
(p-1)B!
ở cuối vòng lặp for (bớc 2)
a 2
B!
(mod n)
nên a 2
B!
(mod p)
vì pn. nên theo định ý Fermat ta có :

135979 ì 115979
Trong trờng hợp này, phép phân tích sẽ thành công do 135978 chỉ gồm
các thừa số nguyên tố nhỏ:

nguyên i xác định nào đó thì thuật toán thực sự là thuật toán thời gian
đa thức, tuy nhiên với phép chọn B nh vậy, xác suất thành công sẽ rất
nhỏ. Mặt khác, nếu tăng kích thớc của B lên thật lớn (chẳng hạn
tới ?????????????? ) thì thuật toán sẽ thành công nhng nó sẽ không
thực hiện nhanh hơn phép chia thử.
Nh vậy, điểm bất lợi của thuật toán này là nó yêu cầu n phải có
ớc nguyên tố p sao cho (p-1) chỉ các thừa số nguyên tố bé. Ta có thể
dễ dàng xây dựng đợc hệ mật RSA với modulus n= pq hạn chế đợc
việc phân tích theo phơng pháp này. Trớc tiên tìm một số nguyên tố
lớn p
1
sao cho p= 2p
1
+1 cũng là một số nguyên tố và một số nguyên tố
lớn q
1
sao cho q= 2q
1
+1 cũng là một số nguyên tố (nhờ dùng một trong
các thuật toán kiểm tra tính nguyên tố Monte-Carlo nêu trong phần
4.5). Khi đó modulo của RSA n= pq sẽ chống đợc cách phân tích theo
phơng pháp p-1.
Thuật toán đờng cong elliptic mạnh hơn (đợc Lenstra xây dựng
vào những năm 1980) trên thực tế là sự tổng quát hoá của phơng pháp
p-1. Ta sẽ không thảo luận về lý thuyết ở đây mà chỉ nhấn mạnh rằng,
thành công của phơng pháp đờng cong elliptic tuỳ thuộc vào tình
huống tơng tự : một số nguyên gần với p chỉ có các thừa số nguyên
tố bé. Trong khi phơng pháp p-1 phụ thuộc vào quan hệ trong Z
p
thì

12044942944
2
1 ì 7 ì 13 (mod n)
2773700011
2
=2 ì 3 ì 13 (mod n)
Nếu lấy tích của ba đồng d thức trên:
(8340934156 ì 2044942944ì2773700011)
2
(2ì 3ì 7ì 13)
2
(mod n)
Rút gọn các biểu thức bên trong các dấu ngặc theo modulo n, ta có:
9503435785
2
546
2
(mod n)
Sau đó tính:
UCLN(9503435785-546, 15770708441)=115759
Ta thấy 115759 là một thừa số của n.
Giả sử B = {p
1
, . . . .p
B
}là một cơ sở nhân tử. Giả sử c lớn hơn B
một chút (chẳng hạn C=B+10) và giả sử ta đã có C đồng d thức:
x
j
2

j
tơng ứng sẽ sử dụng mỗi nhân tử
trong B một số chẵn lần.
Ta sẽ minh hoạ bằng cách trở lại ví dụ 4.15. Trong trờng hợp
này nếu C < B, vẫn tìm đợc sự phụ thuộc tuyến tính.
Ví dụ 4.15 (tiếp)
Cho 3 vector a
1
, a
2
, a
3
:
a
1
=(0, 1, 0, 1, 0, 0)
a
2
=(1, 0, 0, 1, 0, 1)
a
3
= (1, 1, 0, 0, 0, 1)
Dễ dàng thấy rằng:
a
1
+a
2
+ a
3
= (0, 0, 0, 0, 0, 0) mod 2

j
=j +
,j=1,2...... Tên sàng bậc hai lấy từ thủ tục sàng (không mô tả ở đây)
dùng để xác định các x
j
phân tích đợc trên b.
ở đây dĩ nhiên là một sự thoả hiệp: nếu B = | B | là một số lớn
thì thích hợp hơn cả là nên phân tích số nguyên x
j
trên b. Tuy nhiên
khi B càng lớn thì ta càng phải gom nhiều đồng d thức hơn trớc khi có
thể tìm đợc một quan hệ phụ thuộc. Lựa chọn tối u cho B xấp xỉ bằng
??????????????????
[ ]
n