Bài toán phân tích số nguyên ra thừa số nguyên tố

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 2m-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 Mq=2q-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 lưu ý tới việc cài đặt thuật toán Pollard thứ nhất một thuật toán rất hiêụ quả trong việc phân tích những hợp số lớn. Một vấn đề không thể không nói trước là những vấn đề được hiểu thấu đáo sẽ được chúng tôi trình bày chi tiết ở mức độ thuật toán khả thi trong việc lập trình, còn một số kết quả cần đến những chuẩn bị toán học cao siêu thì chỉ được dẫn các đánh giá tương ứng về thời gian tính đủ rút ra các thông số cần thiết để xây dựng các tiêu trí. Chúng tôi nghĩ rằng chỉ có thể trình bày bản báo cáo này theo cách như vậy mới đảm bảo tính cân đối trong cấu trúc bởi vì để làm cho tường minh dù chỉ một trong những vấn đề đã né tránh trên chúng ta cũng phải cần đến hàng tập tài liệu dầy, đấy là chưa kể đến việc chúng ta có đủ kiến thức cần thiết đến mức để có thể trình bày nó cho mọi người rõ hay không. Chương i. Đặt vấn đề và ý nghĩa của bàI toán 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à đã cuốn hút nhiều bộ óc vĩ đại nhất trên thế giới để 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 vào năm 1978, đó là hệ mật mã RSA ( RSA là từ viết tắt của ba người: Rivets – Shamir – Adleman ). Hệ mật này có nội dung đề cập đến việc phân tích số nguyên tố ngẫu nhiên lớn (chẳng hạn có 80 chữ số) ra thừa số. Một vấn đề quan trọng là cần phải kiểm tra bao nhiêu số nguyên ngẫu nhiên (với kích thước xác định) cho tới khi tìm được một số nguyên tố. Một kết quả nỗi tiếng trong lý thuyết số (được gọi là định lý số nguyên tố) phát biểu rằng: số các số nguyên tố không lớn hơn N xấp xỉ bằng N/ln N. Bởi vậy, nếu p được chọn ngẫu nhiên thì xác suất p là một số nguyên tố sẽ vào khoảng 1/ln p. Với một mođun 512 bít, ta có 1/ln p ằ 1/77. Điều này có nghĩa là tính trung bình, cứ 177 số nguyên ngẫu nhiên p với kích thước tương ứng sẽ có một số là số nguyên tố. Dĩ nhiên, nếu chỉ hạn chế xét các số nguyên lẻ thì xác suất sẽ tăng gấp đôi tới khoảng 2/177). Bỡi vậy trên thực tế, hoàn toàn có khả năng tạo được các nguyên tố đủ lớn và do đó về mặt thực thể ta có thể thiết lập được một hệ mật RSA. 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 2m-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 log2n, 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 r 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 2m-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 2m-1 là luỹ thừa của một số Prime Power thì nó phải là một số nguyên tố và do vậy m cũng là một số nguyên tố. Các số có dạng Mq=2q-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. ở vào thời đại của Mersenne, người ta đã biết rằng một vài số Mersenne là số chính phương và một vài số khác là hợp số. Ví dụ, M2=3, M3=7, M5=31, M7=127 là nguyên tố, trong khi M11=23*89. Vào năm 1640 , Mersenne đã cho rằng Mq là số nguyên tố đối với q=13,17,19,31,67,127,257; ông đã nhầm đối với 67 và 257 và đã không đưa 61,89 và 107(những số nhỏ hơn 257) vào danh sách trên. Những số này cũng sinh ra các số nguyên tố Mersenne. Phát hiện của ông thực sự đáng kinh ngạc về mặt độ lớn của các số. Một bài toán khá hiển nhiên là: Xét xem một số Mersenne có là số nguyên tố không, và nếu không thì xác định các thừa số của nó ( hay còn gọi là bài toán 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(qº3(mod 4)) thì Mq 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ì Mq là hợp số. Chứng minh: Cho n=2q+1 là một thừa số của M. Vì 22#1 (mod n) nên 2q#1 (mod n), và 22q-1=(2q+1)Mqº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ì pº7(mod 8) nên (2/p)=1, do vậy tồn tại m sao cho 2ºm2 (mod p). Điều này chứng tỏ rằng 2qº2(p-1)/2ºmp-1º1(mod p) Vì vậy Mq chia hết cho p. Hơn nữa, nếu q>3 thì Mq=2q-1>29+1=p, vì vậy Mq là hợp số. Vì vậy nếu q=11, 23, 83, 131, 179, 191, 239, 251, thì Mq có các ước tương ứng là 23, 47, 167, 263, 350, 383, 479, 503. Cũng rất dễ để xác định hình dạng của các thừa số của các số Mersenne: "Nếu Mq chia hết cho n thì nº±1 (mod 8) và nº1 (mod q)" Chứng minh: Chỉ cần chỉ ra rằng mọi thừa số nguyên tố p của Mq có dạng trên là đủ. Thật vậy, nếu p là ước của Mq=2q-1 thì 2qº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: (mod p). Do đó pº±1 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ẻ, n³3 thì Mn=2n-1º7 (mod 12). Đồng thời, nếu Nº7 (mod 12) thì ký hiệu Jacobi: 2.2. Phép thử nguyên tố cho các số Mersenne Cho p=2,Q=-2 và xét các dãy Lucas kép (Um)m³0,(Vm)m³0, có biệt gthức D=12. N=Mn là một số nguyên tố khi và chỉ khi V(N-1)/2 chia hết cho N. Chứng minh: Cho N là một số nguyên tố. Ta có: V2(N+1)/2=VN+1+2Q(N-1)/2=VN-1-4(-2)(N-1)/2 º VN+1-4(-2/N) ºVN+1+4(mod N) Vì (-2/N)=(-1/N)(2/N)=-1. Vì vậy chỉ cần chỉ ra rằng Nº7 (mod N). Theo (IV.4): 2VN-1=VNV1+DUNU1=2VN+12UN; do vậy theo (IV.14) và (IV.13): VN+1=VN+6VNº2+6(12/N) º2-6º-4(mod N). Ngược lại, giả sử rằng V(N+1)/2 chia hết cho N. Thế thì theo (IV.2), VN+1 chia hết cho N. Đồng thời, theo(IV.6): V2(N+1).2)=1 (gcd_ước chung lớn nhất). Vì vậy gcd(N,2)=1, nên thu phép thử một (Phần V), N là một số nguyên tố. Để cho tính toán, người ta thay dẫy Lucas (Vm)m>=0 bằng dẫy (Sk)k>=1 được định nghĩa như sau: S0=4; Sk+1=S2k-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: Mn=2n-1 là nguyên tố khi và chỉ khi Mn là ước của Sn-2. Chứng minh: S0=4=V2/2. Giả sử rằng Sk-1=V2k/; thì Sk=S2k-1-2=. Theo phép thử này thì Mn là nguyên tố khi và chỉ khi Mn là ước của V(Mn+1).2=, hay tương đương Mn là ước của Sn-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 M127 là nguyên tố và M67 là hợp số. Sau đó không lâu, Pervushin đã chỉ ra rằng M61 cũng là nguyên tố. Cuối cùng, vào năm 1927 Lehmer chứng minh được M257 cũng là hợp số. Chú ý rằng M127 có 39 chữ số và là số nguyên tố lớn nhất được biết tới trước kỷ nguyên của máy tính. Các số nguyên tố Mersenne với q<= 127 được tìm ra trước khi có máy tính điện tử. Năm 1951, Turing đã lần đầu tiên thử dùng một máy tính để tìm các số nguyên tố Mersenne nhưng bị thất bại. Năm 1952, Robinson đã tiến hành phép thử của Lucas trên một máy SWAC. Ông đã tìm ra các số nguyên tố Mersenne : M521, M607_những số đầu tiên tìm được bằng máy tính. Các số nguyên tố M1279,M2203,M2281 cũng được tìm ra trong cùng năm ấy. Số nguyên tố Mersenne lớn nhất đã tìm được là M21609, nó có 65050 chữ số do Slowinski phát hiện năm 1985. Số nguyên tố Mersenne được tìm ra cuối cùng là M110503 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: pº2k±1 hoặc p=4k±3 Mp là một số nguyên tố 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: Liệu có vô hạn các số nguyên tố Mersenne không? 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 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213 19937 21701 23209 44497 86243 110503 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* P.A.Cataldi P.A.Cataldi L.Euler I.M.Pervushin R.E.Powers E.Fauquembergue E.Lucas R.M.Robinson R.M.Robinson R.M.Robinson R.M.Robinson R.M.Robinson H.Riesel A.Hurwitz A.Hurwitz D.B.Gillies D.B.Gillies D.B.Gillies B.Tuckerman L.C.Noll & L.Nickel L.C. Noll H.Nelson & D. Slowinski D.Slowinski W.N.Colquitt & L. Welsch, Jr. D.Slowonski D.Slowonski “See Dickson’s History of the Theory of Numbers, Vol. I.p.6. Chương iII. Một số thuật toán và phương pháp phân tích số 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() nhưng 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=[] 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à mằCp với C là một hằng số tính được nào đó ( việc giải chi tiết bài toán trên có thể xem trong [Riesel]). Như vậy chúng ta có thể thành công trong thuật toán với xác suất >0.5 sau không quá m bước. Hiển nhiên bằng cách duyệt dần thì thời gian tính của thuật toán của chúng ta cũng chẳng khác gì thời gian tính của phép sàng. Trong [Pollard], tác giả J. M. Pollard đã sử dụng một phương pháp còn được gọi là “phương pháp p” nhằm chỉ cần thông qua bước có thể duyệt được m cặp khác nhau như đã nêu trong thuật toán. Việc thể hiện phương pháp này có thể mô tả như sau: Chọn dãy giả ngẫu nhiên {xi mod N:i=1,2,...} được xác định như sau xi-1º(xi2+a) mod N với a#0 và #-2 còn giá trị đầu x0 tuỳ ý. 3.3 Thuật toán sàng bậc hai Tử tưởng chủ đạo của một loạt khá lớn các thuật toán phân tích số như phương pháp đặc biệt của Euler, phương pháp phân tích các dạng chính phương của Danien Shanks, phương pháp khai triển liên phân số của Morrison và Brillhart, phương pháp sàng bậc hai của Pomerance... là cố tìm đồng dư thức x2=y2 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= còn x=0, ±1, ±2,... - Xây dựng đồng dư thức x2ºy2 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 x2ºy2 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à ri=xi2=qa11.qa12...qakk( qj là số nguyên tố thứ j của B), ta đặt tương ứng với véc tơ viẻGF(2)2 như sau vi=(a1mod 2, a2 mod 2,..., ak mod 2). Chý ý rằng có thể có nhiều giá trị ri khác nhau được ứng cùng với một véc tơ v nhưng 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ơ vi (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à: , với q là véc tơ không và ai không đồng thời bằng không. Khi đó theo định nghĩa sẽ là x2 mod N, mặt khác do điều kiện đặt ra ở trên là Q(xi) phân tích được hoàn toàn trong tập cơ sở cùng với điều kiện tức là vế phải của tích 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 y2 nào đó. Nếu xạ±y 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(x±y, 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à 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+rpa)º[(m+x+rpa )2-N mod Nº{[(m+x)2-N]+rpa[2(m+x)+rpa]}mod NºQ(x)+rpa[2(m+x)+rpa] mod N nên: Nếu pa là ước của Q(x) thì nó cũng là ước của Q(x+rpa) 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. Ngoài ra một số kết quả (xem [Riesel]) khác cũng không kém phần quan trọng đó là: Điều kiện cần và đủ để $x sao cho p là ước của Q(x) là kí hiệu Legendge (N/p)=1. Như vậy không phải toàn bộ các số nguyên tố trong đều cần phải được biểu diễn (đúng hơn là chỉ có khoảng một nửa số nguyên tố trong cơ sở là có mặt trong biểu diễn của các Q(x)) do đó để thu được hệ phụ thuộc tuyến tính nêu trong phân tích trên thì thường chỉ cần số phương trình khoảng già nửa số các nguyên tố trong cơ sở là đủ. Nếu pº3 mod 4 thì giá trị xºm±N(p+1)/4 mod p là các giá trị <p thoả mãn p là ước của Q(x). Nếu pº1 mod 4 thì việc tìm các giá trị x tương tự có thể bằng một thuật toán gần đa thức. Nếu x<pa thoả mãn pa là ước của Q(x) và pa+1 không là ước của Q(x) thì giá trị y<pa+1 có pa+1 là ước của Q(y) có thể tìm được là y=x+rpa với r là nghiệm của phương trình đồng dư bậc nhất sau 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 pa là ước của Q(x). - Các thặng dư bậc hai nhỏ Q(x)=R2=qa11.qa22...qakk, ở đây x0 là giá trị nhỏ nhất để qa11.qa22...qakk là ước của Q(x) mà ta có thể phát hiện được ở bước trên. Tất cả các phân tích được nêu ở trên mặc dù chưa đủ 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à: 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 x2ºy2 (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 x2 (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 x2 º y2 (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: 83409341562 º 3 ´ 7 (mod n) 120449429442 º 1 ´ 7 ´ 13 (mod n) 27737000112 =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ó: 95034357852 º