Lời nói đầu
Bài toán phân tích số nguyên ra thừa số nguyên tố đã đợc ra đời từ rất lâu và
đã có rất nhiều nhà toán học trên thế giới nghiên cứu và giải quyết vấn đề về nó.
Ngoài ý nghĩa lý thuyết của bản thân bài toán thì ngời ta còn phát hiện ra rất nhiều
ý nghĩa thực tiễn đặc biệt là trong mật mã.
Thứ nhất nó là cơ sở cho sự ra đời của một hệ mật khoá công khai nổi tiếng
ra đời trong năm 1978, đó là hệ mật RSA của Revert - Shamir - Adlemal. Hệ mật
này mà độ mật của nó dựa vào tính khó của việc phân tích số N=pq (p, q nguyên
tố ) ra thừa số.
Tiếp đến trong những việc thiết kế nên các bộ tạo dãy giả ngẫu nhiên một
trong những nguyên liệu của nó là các đa thức nguyên thuỷ mà để tạo đợc các đa
thức nguyên thuỷ bậc m thì điều đầu tiên phải giải quyết là phân tích hoàn toàn với
2
m
-1 ra thừa số nguyên tố.
Để giải quyết vấn đề đợc đặt ra trong đồ án này, chúng tôi đa ra một số cơ
sở lý thuyết.
Chơng 1 sẽ trình bầy về các số Mersenne. Các số có dạng M
q
=2
q
-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.
Chơng 2 xem xét loại bài toán quen thuộc hơn đó là bài toán phân tích số nguyên
ra thừa số. Sự đóng góp có tính khoa học của chúng tôi thề hiện bởi việc trình bày
các thuật toán về phân tích số nguyên tố theo cách hiểu của mình.
Chơng 3 là phần cơ bản của đề án, trong đó trình bày các t tởng của thuật toán
phân tích ra thừa số nguyên tố của những số nguyên lớn. Tiếp theo trong chơng
này trình bày các cài đặt cụ thể cho những thuật toán liên quan đến việc phân tích
ra thừa số nguyên tố, ví dụ nh các phép : +, -, *, / và luỹ thừa các số lớn. Chúng tôi
còn đặc biệt lu ý tới việc cài đặt thuật toán Pollard thứ nhất một thuật toán rất hiêụ

trong những nguyên liệu của nó là các đa thức nguyên thuỷ mà để tạo đợc các đa
thức nguyên thuỷ bậc m thì điều đầu tiên phải giải quyết là phân tích hoàn toàn với
2
m
-1 ra thừa số nguyên tố. Để kiểm tra tính nguyên thuỷ của chúng bằng cách
dùng thuật toán xác suất Monte- Carlo thời gian đa thức, đây là thuật toán nhanh
(tức là một số nguyên n đợc kiểm tra trong thời đa thức theo log
2
n, là số các bít
trong biểu diện nhị phân của n). Tuy nhiên, vẫn có khả năng là thuật toán cho rằng
n là số nguyên tố trong khi thực tế n là hợp số. Bởi vậy, bằng cách thay đổi thuật
toán nhiều lần, có thể giảm xác suất sai số dới một mức ngỡng cho phép.
Bản đồ án không đi sâu vào các phân tích của những ý nghĩa nêu trên mà đã
đặt nhiệm vụ chính là giải quyết bài toán phân tích số nguyên ra thừa số nguyên
tố nh là một việc làm trung gian của một ứng dụng thực tiễn cụ thể. Đã có một
khối lợng khổng lồ các tài liệu về các thuật toán phân tích thừa số và việc nghiên
cứu kỹ lỡng sẽ đòi hỏi phải có một cuốn sách dày trang hơn quyển sách này. ở
đây chỉ cố gắng đa ra một cái nhìn khái quát bao gồm việc thảo luận sơ lợc về các
thuật toán phân tích thừa số tốt nhất hiện thời và cách sử dụng chúng trong thực tế.
Các thuật toán nổi tiếng khác (những thuật toán toán có trớc) bao gồm thuật toán
p+1 của Williams, phơng pháp và thuật toán p-1 của Pollard, thuật toán liên
phân số và dĩ nhiên cả những phép chia thử.
Chơng iI. Số Mersenne và việc phân tích
2.1 Số Mersenne
Nếu một số có dạng 2
m
-1 là một số nguyên tố thì m=q là một số nguyên tố.
Không khó khăn lắm, có thể chứng minh đợc rằng nếu 2
m
-1 là luỹ thừa của một số

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à:
Bài toán: Nếu q là một số nguyên tố đồng d modulo 4(q3(mod 4)) thì M
q
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ì
M
q
là hợp số.
Chứng minh: Cho n=2q+1 là một thừa số của M. Vì 2
2
#1 (mod n) nên 2
q
#1 (mod
n), và 2
2q
-1=(2
q
+1)M
q
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ì p7(mod 8) nên (2/p)=1, do
vậy tồn tại m sao cho 2m
2
(mod p). Điều này chứng tỏ rằng 2
q
2
(p-1)/2
m

-1 thì 2
q
1 (mod q); Vì vậy theo bài toán
nhỏ của Fermat thì q là ớc của p-1, tức là p-1=2kq (vì p#2). Vì vậy:
122)
2
(
2/)1(


qkp
p
(mod p).
Do đó p1 mod (8).
Phơng pháp tốt nhất hiện nay dùng để xác định Mq là một số nguyên tố hay
là một hợp số đợc phát triển dựa vào việc tính toán một dãy đệ qui do Lucas
(1878) và Lehmer (1930) đa ra. Tuy nhiên, bằng cách này vẫn không tìm ra đợc
các thừa số cụ thể.
Nếu n lẻ, n3 thì M
n
=2
n
-17 (mod 12). Đồng thời, nếu N7 (mod 12) thì ký
hiệu Jacobi:
1)1)(
3
()
3
(
2/)1(

(N-1)/2
=V
N-1
-4(-2)
(N-1)/2
V
N+1
-4(-2/N) V
N+1
+4(mod N)
Vì (-2/N)=(-1/N)(2/N)=-1. Vì vậy chỉ cần chỉ ra rằng N7 (mod N). Theo
(IV.4): 2V
N-1
=V
N
V
1
+DU
N
U
1
=2V
N
+12U
N
; do vậy theo (IV.14) và (IV.13):
V
N+1
=V
N

-2;
Vì thế dẫy này sẽ khởi đầu bằng 4,14,194,... và phép thử nguyên tố đợc phát
biểu lại nh sau:
M
n
=2
n
-1 là nguyên tố khi và chỉ khi M
n
là ớc của S
n-2
.
Chứng minh: S
0
=4=V
2
/2. Giả sử rằng S
k-1
=V
2k
/
1
2
2

k
;
thì S
k
=S

là nguyên tố
khi và chỉ khi M
n
là ớc của V
(Mn+1).2
=
2
2
2
2
2
1



=
n
SV
n
n
, hay tơng đơng M
n
là ớc của
S
n-2
. Tính lặp của các phép tính này đã làm cho phép thử trở nên phù hợp. Bằng
cách này, tất cả các ví dụ về các số nguyên tố Mersenne lớn đã đợc tìm ra. Năm
1876 , Lucas đã tự mình tìm ra M
127
là nguyên tố và M

110503
do Colquitt và Welsch phát hiện năm
1988. Năm 1989, Bateman, Selfridge và Wagstaff đã đa ra một phỏng đoán liên
quan đến các số nguyên tố Mersenne:
Cho p là một số tự nhiên lẻ (không nhất thiết phải là nguyên tố). Nếu hai
trong các điều kiện sau đây thoả mãn thì điều kiện thứ 3 cũng thoả mãn:
a) p2
k
1 hoặc p=4
k
3
b) Mp là một số nguyên tố
c)
3
12
+
p
là một số nguyên tố
Phỏng đoán này đã đợc kiểm chứng là đúng đối với mọi p<100.000. Những
số nguyên tố p<100.000 thoả mãn cả ba điều kiện là p=3, 5, 7, 13, 17, 19, 31, 61,
127. Có thể tin rằng những số này là các số nguyên tố duy nhất thoả mãn cả ba
điều kiện nói trên.
Cũng nh đối với các số Fermat, hiện còn có rất nhiều vấn đề mở về các số
Mersenne:
(1) Liệu có vô hạn các số nguyên tố Mersenne không?
(2) Liệu có vô hạn các số Mersenne là hợp số không?
Câu trả lời cho cả hai câu hỏi trên chắc là có
(3) Có phải mọi số Mersenne đều là không chính phơng không?
Kỷ lục: Có 31 số nguyên tố Mersenne đã đợc biết. Dới đây là danh sách đầy đủ
của chúng cùng với tên ngời và năm tìm ra.

132049
216091
1461
1588
1588
1750
1883
1911
1913
1876
1952
1952
1952
1952
1952
1957
1961
1961
1963
1963
1963
1971
1978
1979
1979
1982
1988
1983
1985
Anonymous

3.1 Thuật toán sàng Eratosthenes
Thuật toán phân tích số nguyên N đợc mô tả nh sau:
Thuật toán 3.1( sàng Eratosthenes )
(1) p=1.
(2) p=p+1.
(3) Tính r=N mod p.
Nếu r>0 quay về (2).
Ngợc lại p là ớc của N. Dừng chơng trình...
Đây là thuật toán có tính phổ thông và mặc dù nh chúng ta đã biết là thuật
toán rất tồi vì thời gian tính của nó là O(
N
) nhng nếu N có ớc nhỏ thì việc áp
dụng thuật toán này lại rất hiệu quả. Hơn thế nữa, thuật toán này cũng có thể lấy
điểm xuất phát của bớc (1) là p=[
N
] và tiến hành bớc (2) là p=p-1 thì rõ ràng nó
cũng hiệu quả nếu ớc của N rất gần với.
3.2 Thuật toán sàng đồng d
Thuật toán 3.2:
Lấy ngẫu nhiên hai số a và b ngẫu nhiên

Z
*
N
.
Kiểm tra gcd((a-b) mod N, N) hoặc gcd((a+b) mod N, N)>1 là xác suất nh sau:
Nếu đúng thì gcd((a-b) mod N, N) hoặc gcd((a+b) mod N, N)>1 là ớc của N.
Dừng chơng trình.
Ngợc lại quay về (1).
Bây giờ chúng ta hãy tạm dừng để phân tích thuật toán dới góc độ xác suất

sàng bậc hai của Pomerance... là cố tìm đồng d thức x
2
=y
2
mod N sao cho x#y
mod N, còn kỹ thuật tìm cụ thể nh thế nào thì chính là nội dung riêng của từng
thuật toán.
Đối với thuật toán sàng bậc hai của Pomerance đợc thực hiện nh sau:
- Chọn k số nguyên tố đầu tiên và gọi là cơ sở phân tích.
- Chọn B là một số nào đó gọi là ngỡng tìm các thặng d bậc hai nhỏ.
- Tìm k+1 các thặng d bậc hai nhỏ hơn B và phân tích đợc hoàn toàn trong tập cơ
sở trong lớp các số dạng Q(x)((m+x)
2
-N mod N với k là số phần tử của cơ sở, m=
N
còn x=0, 1, 2,...
- Xây dựng đồng d thức x
2
y
2
mod N từ k+1 thặng d bậc hai tìm đợc trên.
Cơ sở của thuật toán chủ yếu dựa vào thứ nhất là khả năng tìm đợc k+1
thặng d bậc hai và tiếp đến là việc xây dựng đồng d thức x
2
y
2
mod N nh thế nào.
Trớc hết chúng ta cùng xem xét đến vấn đề thứ hai.
Giả sử thặng d bậc hai thứ i tìm đợc ở trên là r
i

i
khác nhau đợc ứng
cùng với một véc tơ v nhng một cách hình thức ta có thể coi k+1 véc tơ khác nhau
thu từ việc ứng k+1 giá trị r có đợc ở trên.
Hiển nhiên trong không gian k chiều GF(2)
k
thì tập k+1 véc tơ v
i
(i=1,2,...k+1) chắn chắn phụ thuộc tuyến tính, giả sử ta có tổ hợp tuyến tính đặc tr-
ng cho sự phụ thuộc đó là:

+
=
=
1
1
k
i
ii
va

, với là véc tơ không và a
i
không đồng thời bằng không.
Khi đó

=
1
1
1

chứa toàn các số mũ chẵn đối với các thừa số
trong cơ sở do vậy nó cũng là một thặng d bậc hai y
2
nào đó. Nếu xy mod N thì
chúng ta sẽ thành công trong việc phân tích N với các thừa số tơng ứng là
gcd(xy, N). Ngời ta cũng chỉ ra rằng khả năng thành công xảy ra với xác suất là
2
1
do vậy thời gian tính của thuật toán chủ yếu phụ thuộc tuyến tính (thông thờng
bằng phép khử Gauss).
Với việc tìm các thặng d bậc hai nhỏ thoạt nhọửn chúng ta nhận thấy rằng
do Q(x+rp

)[(m+x+rp


)
2
-N mod N{[(m+x)
2
-N]+rp

[2(m+x)+rp

]}mod NQ(x)
+rp

[2(m+x)+rp

] mod N nên:

y<p

+1
có p

+1
là ớc của Q(y) có thể tìm đợc là y=x+rp

với r là nghiệm của phơng
trình đồng d bậc nhất sau
0)(2
)(
2
++
+
rmx
P
Nmx

mod p ( chú ý rằng phơng
trình trên luôn luôn có duy nhất nghiệm).
Với hai kết quả trên rõ ràng chúng ta luôn tìm đợc toàn bộ giá trị x trong
một phạm vi B cho trớc nào đó mà với chúng Q(x) có ớc lẻ trong tập cơ sở phân
tích. Trờng hợp p=2 việc thu đợc kết quả na ná nh trên có phức tạp hơn, chúng tôi
không đủ tài liệu để mô tả tờng minh việc dò tìm đó ở đây.
Tóm lại quá trình tìm các thặng d bậc hai nhỏ có thể mô tả nh sau:
- Chọn một ngỡng B nào đó và sàng để tìm các giá trị x nhỏ nhất < B mà với
chúng p

là ớc của Q(x).

Tất cả các phân tích đợc nêu ở trên mặc dù cha đủ chặt chẽ cho sự đảm bảo
thành công của việc tìm các thặng d bậc hai nhỏ trong lớp Q(x) mà chỉ dừng ở
mức độ thể hiện một mô tả bớc tìm kiếm này sẽ đợc thông qua một quá trình
sàng theo cơ sở của những kết quả nêu trên nhằm loại bỏ các giá trị không thể là
ứng cử viên cho các thặng d bậc hai nhỏ. Một số tài liệu (xem [Dixon],
[Lenstra],...) đã phân tích về thời gian tính của thuật toán và số liệu khả quan nhất
về vấn đề này của Lenstra là:
)(
2
1
)lnln))(ln0(1(
e
NN
O
+
với O(1) là một hàm tiến tới 0 khi N tiến tới .
3.4 Thuật toán Dixon và sàng bậc hai
Thuật toán Dixon đợc xây dựng trên ý tởng đó là: nếu tìm đợc x y (mod
n) sao cho x
2
y
2
(mod n) thì UCLN(x-y,n) là ớc không tầm thờng của n.
Phơng pháp này sử dụng cơ sở nhân tử là một tập b chứa các số nguyên tố bé.
Trớc tiên ta nhận đợc một vài số nguyên x sao cho tất cả các thừa số nguyên tốcủa
x
2
(mod n) nằm trong cơ sở b (cách thực hiện điều này sẽ đợc thảo luận sau). ý t-
ởng thực hiên ở đây là lấy tích của một vài giá trĩ sao cho mỗi số nguyên tố trong
cơ sở đợc sử dụng một số chẵn lần. Điều này dẫn đến một đồng d thức dạng mong

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
p
1

1j
ì p
2

2j
ì . . .ì p
B

Bj
(mod n)
với 1 j C. Với mỗi j xét véctor :
a
j
= (
1j
mod 2,

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
Đây là lý do cho thấy đồng d thức (thiết lập theo tích) sẽ phân tích thành công đợc
n.
Nhận thấy rằng, bài toán tìm một tập con C vector a
1
, a
2
, . . ., a
C
sao cho
tổng theo modulo 2 là một vector toàn chứa số 0 chính là bài toán tìm sự phụ
thuộc tuyến tính (trên Z
2
) của các vector này. Với C > B, sự phụ thuộc tuyến tính
này nhất định phải tồn tại và ta có thể dễ dàng tìm đợc bằng phơng pháp loại trừ
Gaux. Lý do giải thích tại sao lấy C > B+1 là do không có gì bảo đảm để một
đồng d thức cho trớc bất kỳ sẽ tạo đợc phân tích n. Khoảng 50% thuật toán cho ra
x y (mod n). Tuy nhiên nếu C > B+1 thì có thể nhận đợc một vài đồng d thức
nh vậy. (Nảy sinh từ các phụ thuộc tuyến tính khác của các a
j
). Hy vọng là ít nhất

n
có bậc không là
ớc của p-1. Số a nếu tìm đợc hiển nhiên phải thoả mãn ba
p-1
mod N#1, điều này
có ý nghĩa N không là ớc của b-1. Mặt khác do p nguyên tố nên theo định lý
Fermat ta có b mod p(a
p-1
mod N) mod p=1 nh vậy b-1 0 mod p và do đó có
ngay p | gcd(b-1,N). Hai điều kéo theo p=gcd(b-1,N).
Một số vấn đề cha tờng minh trong việc thực hiện nói trên là:
[ ]
n
Do p là số cha biết nên dấu hiệu nhận biết giá trị a cần tìm là a
p-1
mod N#1 cũng
cha xác định. Tất nhiên ở đây điều kiện nhận biết có thể đợc làm nhẹ bớt đó là
ta có thể thay số p-1 cha biết bằng số Q giả định có thể là chọn trớc và tính ba
Q
mod N, nếu N>gcd(b-1, N)>0 thì việc chọn của chúng ta đã thành công và có
p=gcd(b-1, N). Hiển nhiên việc giả định Q chỉ có nghĩa khi và chỉ khi p-1 là ớc
của Q, trong trờng hợp p-1 chỉ có các ớc nguyên tố nhỏ tức là p-1=
qq
N
k
q
N
q
k
loglog

loglog
1
...
1
, i=1,j=0.
(2) Lấy a ngẫu nhiên trong Z
*
N
, tính ba
Q
mod N.
(3) Xét đẳng thức b=1.
Nếu đúng chuyển sang (4).
Ngợc lại chuyển sang (6).
(4) Xét j<log
qi
N.
Nếu đúng thì j=i+1, Q=Q|qi, quay về (3).
Ngợc lại: chuyển sang (5).
(5) Xét i<k.
Nếu đúng thì : i=i+1, j=0, nếu b#1 thì Q=Q.q
i
. Quay về (4).
Ngợc lại quay về (1).
(6) Xét gcd (b-1, N)>1.
Nếu đúng có ớc của n là gcd (b-1,N). Dừng chơng trình.
Ngợc lại quay về (4)...
Chú ý: Thuật toán của Pollard mà chúng tôi trình bày ở trên giống bất cứ thuật
toán trình bày trong các tài liệu khác nh của [Riesel], [Stinson]... tuy nhiên một số
chi tiết nh giá trị xuất phát Q ở các thuật toán khác đều lấy là Q=q

Tiếp đến trong thuật toán của chúng tôi, mỗi khi xét một giá trị a chúng tôi
vét toàn bộ khả năng về bậc của nó. Giá trị b#1 tìm đợc trong (2) đảm bảo bậc của
a không là ớc của p-1, mỗi giá trị b#1 tìm đợc trong các phần sau đó thành công ở
(6) cũng đảm bảo một kết luận tơng tự. Giá trị Q cuối cùng trong trờng hợp không
thành công của thuật toán chính là bậc của a và khi này Q|p-1.
3.6 Phơng pháp : Thuật toán Pollard thứ hai
Bớc tiến đáng kể nhất trong các thuật toán hiệu quả trong việc tìm các ớc
nhỏ là thuật toán dựa vào phơng pháp còn đợc gọi là thuật toán Pollard thứ hai.
Thời gian tính của thuật toán này chỉ còn là O (
p
) với p là ớc nguyên tố nhỏ
nhất của N. Nh vậy trong trờng hợp tồi nhất (p
N
) thì thời gian tính cũng chỉ là
3
N
.
ý tởng phơng pháp p của Pollard rất đơn giản nh sau: Tìm hai phần tử a và
b đồng d modulo p ( ab mod p) nhng không đồng d modulo N. Khi này p sẽ là -
ớc của gcd(N,(ab ) mod N).
Thuật toán 2.3 (Thuật toán Pollard thứ hai)
(1) i=0
(2) i=i+1
(3) Xét gcd((x
2i
- x
i
)mod N,N)>1
- Nếu đúng ta có gcd((x
2i

)...
(x
2i-1
+x
i-1
)(x
2i-2
+x
i-2
)...(x
i
+x
0
)(x
i
+x
0
)
Nh vậy tại bớc thứ i chúng ta đã xét đến i+1 cặp khác nhau và cũng dễ dàng
nhận ra rằng các cặp đợc xét trong mọi bớc là không giống nhau do đó hiển nhiên
với
p
bớc chúng ta đã có p cặp khác nhau đợc xét đến và nh đã phân tích ở trên,
thuật toán sẽ thành công với xác xuất >0.5.Nói một cách khác thuật toán của
Pollard đợc thực hiện trong (
p
) bớc.
Nhận xét
Với các thuật toán đơn giản đợc giới thiệu trong phần này chúng ta cùng thống
nhất đa ra yêu cầu sau đối với các module hợp số.

+b
m
(**).
Các dãy {U
m
}, {V
m
} m=0,1,2,... gọi là dãy Lucas của phơng trình (*). Ngợc lại
phơng trình (*) gọi là phơng trình đặc trng của dãy (**)...
Tính chất 3.6. Nếu i là ớc của j thì U
i
là ớc của U
j
...
Tính chất 3.7. (Công thức tính các phần tử của dãy Lucas).
Ta có U
0
=0, U
1
=1, V
0
=2, V
1
=P và m>1 thì U
m
và V
m
đợc tính theo công
thức sau:
...

VU
VU
m
mm
mm
Định lý 3.8. { U
m
} là dãy Lucas của phơng trình (*) với P
2
-4Q=d
2
có không có
ớc chính phơng (hay còn gọi là bình phơng tự do).
Nếu p không là ớc của Q thì
0











P
p
mod p ở đây


cho R
2
-4S=d
2
với d#0 nào đó. Xét gcd(Q.N)>1.
Nếu đúng ta có ớc của N là gcd(Q.N). Dừng chơng trình.
Ngợc lại tính bU
Q
mod N (phần tử thứ Q trong dãy Lucas của phơng trình x
2
-
Rx+S=0).
(3). Xét đẳng thức b=0.
Nếu đúng chuyển sang (4).
Ngợc lại chuyển sang (6).
(4). Xét j<log
qi
N.
Nếu đúng j=j+1, j=0, nếu b#1 thì Q=Q.qi. Quay về (3).
Ngợc lại: chuyển sang (5).
(5). Xét i<k.
Nếu đúng thì: i=i+1, j=0, nếu b#1 thì Q=Q.qi. Quay về (4).
Ngợc lại quay về (1).
(6). Xét gcd(b, N)>1.
- Nếu đúng có ớc của n là gcd(b,N). Dừng chơng trình.
Ngợc lại quay về (4)...
Phân tích thuật toán
Trớc hết ta thấy rằng các bớc và việc làm trong mỗi bớc của thuật toan gần
nh giống hệt với thuật toán của Pollard nhằm để vét hết các khả năng p+1 (trong
trờng hợp

Các ý tởng liên quan đến việc tìm ra ớc số p của số N đợc mô tả nh sau:
(1) Xây dựng một dãy số nguyên {x
i
} hồi qui tuần hoàn (mod p).
(2) Tìm ra chu kỳ, tức là tìm i và j, sao cho x
i
=x
j
(mod p)
(3) Nhận dạng thừa số p của N.
Bớc 1 yêu cầu tìm ra một dãy tuần hoàn (mod m), trong đó m là một số
nguyên tuỳ ý, là rất dễ thoả mãn. Xét một dãy bất kỳ đợc định nghĩa đẹ qui theo
kiểu sau ( s đợc giá thiết là một hằng số, tức là độc lập với i, và F là một đa thức):
x
i
F(x
i-1
,x
i-2
,...,x
i-s
) (mod m)
với các giá trị đã cho đối với x
1
, x
2
,...,x
s
. Sau đó x
s+1

j-1
, x
j-2
,...,x
k-s
, nên rõ ràng là, nếu các
dãy của các giá trị này trùng khớp nhau đối với hai giá trị khác nhau của k, thì các
giá trị x
i
và x
j
, đợc tính từ các giá trị đằng trớc theo cùng một cách sẽ giống nhau.
Vì vậy, chúng ta có hai dẫy mới gồm s giá trị:
x
i
, x
i-1
,...,x
i-s+1
và x
j
, x
j-1
,..., x
j-s+1
với tính chất là x
i
=x
j
, x

Sau 10 phần tử dẫy này lặp lại. Đây là dẫy tuần hoàn ngay từ bắt đầu.
Bây giờ sang bớc 2 của thuật toán : tìm chu kỳ. Để xác định nó trong trờng
hợp tổng quát, ta cần phải tìm ra vị trí mà tại đó một dẫy các phần tử liên tiếp bắt
đầu lặp lại nếu chu kỳ dài. Đây là một việc cực khó và rất tốn công sức. Tuy nhiên,
trong trờng hợp đơn giản nhất khi mà x
i
đợc định nghĩa chỉ qua x
i-1
và không qua
bất kỳ một x
k
nào khác thì dẫy này đợc lặp lại theo chu kỳ ngay khi một phần tử x
j
bất kỳ bằng một phần tử trớc nó. Vì vậy, trờng hợp này chỉ yêu cầu một phép so
từng giá trị x
j
mới với các x
k
đứng trớc để tìm ra chu kỳ. Tuy vậy, nếu chu kỳ rất
dài (một vài triệu phần tử ) thì rất khó có thể ghi lại tất cả các phần tử và so sánh
chúng từng cặp. Thay vào đó, ta có thể sử dụng kỹ thuật sau:
Giả sử dẫy tuần hoàn {x
i
} (mod m) với phần không tuần hoàn có độ dài a và
một chu kỳ có độ dài l. Thế thì, chu kỳ này cuối cùng sẽ đợc phát hiện ra bằng
phép thử: x
2i
x
i
(mod m)?

2i
. Giả sử
x
i+1
=f(x
i
). Thuật toán tìm chu kỳ có thể mô tả bằng đoạn mã chơng trình sau:
x:=x
1
; y:=f(x
1
);
WHILE x<>y DO
BEGIN
x:=f(x); y:=f(y); y:=f(x);
END;
Khi thực hiện đợc đến đây có nghĩa là x=y và chu kỳ đã đợc chạy qua.
Cuối cùng, ta xét các yêu cầu thứ ba và cuối cùng của phơng pháp p của
Pollard. Nếu chúng ta có một dãy {x
i
} tuần hoàn (mod p) thì bằng cách nào chúng
ta có thể tìm đợc ớc p cha biết của N? cũng giống nh cách chúng ta đã làm trong
phơng pháp p-1, đơn giản bằng cách dùng thuật toán Euclit để tìm ớc chung lớn
nhất d của x
2i
-x
i
(mod N) và N. Thờng thì d sẽ quay về 1, nhng ngay khi x
2i
x

1)(
365
2
1)(
365
1
1(


Biểu thức này nhỏ hơn <0.5 khi q23.
Tổng quát hoá: q phải bằng bao nhiêu để cho ít nhất hai số nguyên đợc chọn ngẫu
nhiên trong q số sẽ là đồng d (mod p) với xác suất >1/2.
Điều này sẽ xảy ra nếu
2
1
)
1
1)...(
3
1)(
2
1)(
1
1(
<


p
q
ppp