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

-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
-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
+6V
N

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
2
k-1
-2=

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
67
là hợp số. Sau đó không
lâu, Pervushin đã chỉ ra rằng M

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.
q Năm Ngời phát hiện
2
3
5
7

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
*
P.A.Cataldi
P.A.Cataldi
L.Euler
I.M.Pervushin

(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
nh sau:
Cho p là ớc nguyên tố nhỏ nhất của N, thế thì cần có tối thiểu bao nhiêu
cặp a, b đợc xét đến xác suất { có ít nhất một cặp a, b chia hết cho p} > 0.5.
Bài toán trên còn đợc gọi là bài toán trùng ngày sinh và số m tối thiểu
cần tìm trong bài toán sẽ là mCp với C là một hằng số tính đợc nào đó ( việc giải

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
=x
i
2
=q
1
1

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
)(
a
xQ
theo định nghĩa sẽ là x
2
mod N, mặt khác do điều kiện đặt ra ở
trên là Q(x

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:
Nếu p

là ớc của Q(x) thì nó cũng là ớc của Q(x+rp

) với mọi số nguyên r.
Từ kết quả trên chúng ta thấy rằng nếu tồn tại giá trị x theo yêu cầu Q(x)
phân tích hoàn toàn trong cơ sở và không quá B thì ta có thể tìm đợc nó chỉ cần
trong lân cận B của 0.

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).
- Các thặng d bậc hai nhỏ Q(x)=R
2
=q

1
1
.q


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
muốn x
2
y
2
(mod n) mà ta hy vọng sẽ đa đến việc phân tích n.
Ta sẽ minh hoạ bằng một ví dụ đã đợc dự tính kỹ lỡng.
Ví dụ :
Giả sử n=15770708441. Giả sử b = {2,3,5,7,11,13}. Xét ba đồng thức sau:

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,
2j
mod 2, . . .,
Bj
mod 2) (Z
2
)
B
Nếu có thể tìm đợc một tập con các 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
một trong các đồng d thức kết quả sẽ dẫn đến việc phân tích n.
Vấn đề còn lại là phải làm thế nào để nhận đợc các số nguyên x
j
mà các giá
trị x
j
2
mod n có thể phân tích hoàn toàn trên cơ sở b. Một vài phơng pháp có thể

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
1
...
1
.
Tất nhiên các số mũ trong khai triển của Q là quá d thừa do đó các lựa chọn tiếp
theo của chúng ta sẽ là cố giảm các số mũ này đến mức thấp nhất có thể, cách làm
cụ thể cho việc này sẽ đợc mô tả cụ thể trong thuật toán.
Vấn đề kế tiếp là việc tìm kiếm có khả thi hay không, nói một cách khác

, 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
1
!...q
k
!, tiếp đến
là mỗi giá trị a chỉ đợc xét đúng một lần với giá trị ba
Q
mod N, thậm chí trong
[Stinson] chỉ luông xét với a=2.

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
i
)mod N,N).Dừng chơng trình
- Ngợc lại quay về (2).
Bây giờ chúng ta phân tích thời gian tính của thuật toán.
Một điều dễ dàng nhận ra là:
x
2i

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ố.
Điều kiện 2.4.Về ớc bé nhất của module hợp số N.
-p phải là một số lớn
- Các ớc phải có kích thớc xấp xỉ nhau.
- Các ớc không đợc xấp xỉ nhau về giá trị.
Yêu cầu thứ nhất là đơng nhiên tuy vậy định lợng cho tiêu chuẩn lớn ở đây cha
đợc đặt ra.Yêu cầu thứ hai chính là bài toán phân tích về lớp khó nhất của
chúng, còn yêu cầu cuối cùng đợc coi là mội ví dụ chi việc tránh các trờng hợp cá
biệt. Điều kiện 2.4 đã loại bỏ tất cả các module không an toàn trớc tấn công bở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:
...
01
00
11
11





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






P

là kí hiệu Legendre...
Nếu nh cơ sở của phơng pháp p-1 là dựa vào kết quả của định lý Fermat thì

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






P

=-1) và p-1 (trong trờng hợ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
, x
s+2
,... có thể đợc tính lần lợt
theo công thức đã cho. Tuy nhiên, vì tất cả các x
k
, đợc cho theo modulo m, nên
mỗi x
k
chỉ có thể nhận một trong m giá trị khác nhau (0,1,...,m-1) và vì vậy chỉ có

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
i-1
=x
j-1
,...,x
i-s+1
. Từ đây dẫn
đến kết quả là x
i+1
đồng nhất với x

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)?
Chứng minh: Trớc hết, nếu x
2i
x
i
(mod m) thì dẫy này rõ ràng là tuần hoàn từ x
2i
trở đi, thậm chí có thể còn trớc nữa. Ngợc lại, đối với một dẫy tuần hoàn bất kỳ với
độ dài chu kỳ l, x
j

; 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
i
(mod P) thì d sẽ chia hết cho p.
Bây giờ, chúng ta sẽ bàn đến một thuật toán tìm thừa số hiệu quả dựa vào
các ý tởng trên dãy sẽ có dạng nh thế nào. Thứ nhất, dẫy {x
i
} nên là một dẫy thật
dễ tính toán ( bởi vì phải tính nó hai lần). Thứ hai, độ dài chu kỳ nên ngắn thôi.
Thứ ba, việc sử dụng thuật toán Euclid cần đợc tổ chức một cách hữu hiệu sao cho
thời gian tính toán không quá nhiều trong phép tìm ớc chung lớn nhất (N, x

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
Vế trái đợc ớc lợng bằng:
e
pqq
q
p
q
2/)1(
1
)
2

i
}. Một cách lựa chọn đơn giản nữa là sử dụng một biểu thức bậc 2:
x
i+1
=x
2
i
+a (mod p)
Về mặt trực giác thì có thể phép chọn này đáp ứng đợc các tính chất cần
thiết (ít ra là khi a không bằng 0 cũng không bằng 2) nhng nó cũng cha đợc
chứng minh đầy đủ.
Chúng ta sẽ thực hiện việc tìm p bằng thuật toán Euclid trên x
2i
-x
i
(mod N)
và N trong mỗi chu trình nh thế nào? Một lần nữa, ta lại sử dụng các mẹo nh đã
làm trong phơng pháp (p-1) : Tích luỹ tích
Q
i
=
)(
1
2 j
i
j
j
xx

=