Đề tài 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 º 5462 (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 = {p1, . . . .pB}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: xj2 º p1a1j ´ p2a2j ´ . . .´ pBaBj(mod n) với 1Ê j Ê C. Với mỗi j xét véctor : aj = (a1j mod 2, a2j mod 2, . . ., aBj mod 2) ẻ (Z2)B Nếu có thể tìm được một tập con các aj sao cho tổng theo modulo 2 là vector (0,. . ., 0) thì tích của các xj 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ụ trên. 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ụ :(tiếp) Cho 3 vector a1, a2, a3 : a1 =(0, 1, 0, 1, 0, 0) a2 =(1, 0, 0, 1, 0, 1) a3 = (1, 1, 0, 0, 0, 1) Dễ dàng thấy rằng: a1 +a2 + a3 = (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 a1, a2, . . ., aC 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 Z2) 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 aj). 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 xj mà các giá trị xj2 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ể thực hiện được điều đó. Biện pháp sàng bậc hai do Pomerance đưa ra dùng các số nguyên dạng xj=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 xj 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 xj 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. 3.5 Phương pháp p-1: Thuật toán Pollard thứ nhất Thuật toán kiểu p-1 là thuật toán phân tích số nguyên N dựa vào phân tích của p-1 với p là một ước nguyên tố của N. Thuật toán còn được gọi là thuật toán phân tích thứ nhất của Pollard, đây là một thuật toán có tác dụng nếu ta biết được các ước nguyên tố của một thừa số p của N nói chung và đặc biệt nếu N có một thừa số nguyên tố p mà p-1 chỉ gồm những ước nguyên tố nhỏ thì thuật toán được trình bày trong phần này sẽ có hiệu quả. ý tưởng của thuật toán là tìm một cách ngẫu nhiên số aẻZ*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 bºap-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º(ap-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 đề chưa tường minh trong việc thực hiện nói trên là: Do p là số chưa biết nên dấu hiệu nhận biết giá trị a cần tìm là ap-1 mod N#1 cũng chưa 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 chưa biết bằng số Q giả định có thể là chọn trước và tính bºaQ 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=. 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 chúng ta phải trả lời câu hỏi “ liệu có tồn tại hay không số a có bậc không là ước của p-1?”. Trước hết chúng ta giới hạn phạm vi số N cần được phân tích là N=pq với p và q là các số nguyên tố khác nhau, khi này bậc cao nhất của các phần tử trong Z*N sẽ là g(N)=1cm(p-1, q-1). Do p khác q nên chắc chắn hoặc p-1 hoặc q-1 là ước thực sự của g(N) và câu hỏi đã được trả lời “có”. Đến đây mức độ “khó hay dễ” của việc tìm được số a sẽ liên quan đến mật độ này như sau: Mật độ nói trên sẽ nghịch biến với gcd(p-1,q-1). Như vậy nếu gcd(p-1,q-1) nhỏ thì việc tìm ra a sẽ thuận lợi, ngược lại trong trường hợp khó khăn hơn (gcd(p-1,q-1) lớn) thì trong phần 2.3 sau này chúng tôi sẽ chỉ ra một phương pháp phân tích hiệu quả hơn. Các bước của thuật toán Pollard. (dùng để phân tích N có ước p với p-1 chỉ gồm các ước nguyên tố trong k số nguyên tố đầu tiên). (1) Q=, i=1,j=0. (2) Lấy a ngẫu nhiên trong Z*N, tính bºaQ 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<logqiN. 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.qi. 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=q1!...qk!, tiếp đến là mỗi giá trị a chỉ được xét đúng một lần với giá trị bºaQ mod N, thậm chí trong [Stinson] chỉ luông xét với a=2. Thứ nhất ta có thể kiểm chứng được rằng nếu p-1 chỉ có các ước trong k số nguyên tố đầu tiên thì chưa chắc p-1 đã là ước của Q= q1!...qk! trong khi đó giá trị Q=mà chúng tôi lựa chọn chắc chắn đáp ứng được yêu cầu này. Chính yếu tố chưa đáp ứng mà các thuật toán khác sẽ gặp phải gcd(b-1, N)=1 ngay cả khi b-1#0 đúng hơn là ngay cả khi a là phần tử có bậc không là ước của p-1 trong khi của thuật toán của chúng tôi với trường hợp này chắc chắn sẽ thành công. 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 r: 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 r 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 () 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ằ) thì thời gian tính cũng chỉ là . ý 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 ( aº±b mod p) nhưng không đồng dư modulo N. Khi này p sẽ là ước của gcd(N,(a±b ) mod N). Thuật toán 2.3 (Thuật toán Pollard thứ hai) i=0 i=i+1 Xét gcd((x2i- xi)mod N,N)>1 - Nếu đúng ta có gcd((x2i- xi)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à: x2i-xi º (X22i-1+a)-(Xi-12+a)ºX22i-1-X2i-1º(x2i-1-xi-1)(x2i-1+xi-1)º...º (x2i-1+xi-1)(x2i-2+xi-2)...(xi+x0)(xi+x0) 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 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 O() 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 chưa đượ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 các thuật toán đã nêu trong mục này. 3.7 Phương pháp p±1: Thuật toán Williams. Để tiện tiếp thu phương pháp p±1 trước hết chúng tôi xin điểm lại một số kết quả chính yếu nhất liên quan đến dãy Lucas ( các định nghĩa liên quan và các chứng minh của các kết quả được đưa ra có thể tìm đọc trong [Riesel], [Kranakis] hay một sách giáo khoa số học bất kỳ). Định nghĩa 2.5. (Dãy Lucas) Cho a, b là hai nghiệm của phương trình x2-Px+Q=0 (*). Kí hiệu Um= và Vm=am+bm (**). Các dãy {Um}, {Vm} 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 trưng của dãy (**)... Tính chất 3.6. Nếu i là ước của j thì Ui là ước của Uj ... Tính chất 3.7. (Công thức tính các phần tử của dãy Lucas). Ta có U0=0, U1=1, V0=2, V1=P và "m>1 thì Um và Vm được tính theo công thức sau: Định lý 3.8. { Um} là dãy Lucas của phương trình (*) với P2-4Q=d2D có D 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 DQ thì mod p ở đây 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ì với kết quả của Lucas ( định lý 2.4) chúng ta cũng phát triển thành một phương pháp phân tích số nguyên một cách tương tự nhưng dựa vào kết quả phân tích của p±1 với p là ước mguyên tố của N. Chúng ta có thể hinh dung về thuật toán như sau: Thuật toán 3.9. (Thuật toán p±1 của Williams). (1). Q=, i=1, j=0. (2). Lấy D không có ước chính phương ngẫu nhiên trong Z*N , tìm R, S nguyên sao cho R2-4S=Dd2 với d#0 nào đó. Xét gcd(DQ.N)>1. Nếu đúng ta có ước của N là gcd(DQ.N). Dừng chương trình. Ngược lại tính bºUQ mod N (phần tử thứ Q trong dãy Lucas của phương trình x2-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<logqiN. 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 =-1) và p-1 (trong trường hợp =1) là ước của Q. Việc xét đẳng thức b=0 trong mỗi bước, nếu sai nhằm đảm bảo cho ta b không là bội của N và nếu p+1 hoặc p-1 là ước của Q thì theo các kết quả 2.7 và 2.9 cho ta b là bội của p và như vậy gcd(b, N) là ước thực sự của N. Thuật toán trên rõ ràng có hiệu quả trong cả hai trường hợp p+1 hoặc p-1 chỉ gồm các ước nguyên tố nhỏ, tuy nhiên căn cứ vào công thức tính các giá trị của dãy Lucas ta thấy ngay rằng hệ số nhân của thuật toán này là lớn hơn nhiều so với thuật toán của Pollard trong trường hợp cùng phân tích được N với ước p của nó có p-1 chỉ gồm những ước nhỏ boỉ vì thay cho việc tính một luỹ thừa thông thường thì thuật toán của Lucas phải tính một luỹ thừa của một ma trận. 3.8 Phương pháp r của Pollard Trong phương pháp này còn được gọi là phương pháp phân tích ra thừa số thứ hai của Pollard. Nó dựa trên một ý tưởng thống kê và đã được R.Brent cải tiến. 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: Xây dựng một dãy số nguyên {xi} hồi qui tuần hoàn (mod p). Tìm ra chu kỳ, tức là tìm i và j, sao cho xi=xj (mod p) 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): xiº F(xi-1,xi-2,...,xi-s) (mod m) với các giá trị đã cho đối với x1, x2,...,xs. Sau đó xs+1, xs+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 xk, được cho theo modulo m, nên mỗi xk chỉ có thể nhận một trong m giá trị khác nhau (0,1,...,m-1) và vì vậy chỉ có nhiều nhất là ms dãy phân biệt xi-1,xi-2,...,xi-s của s số xk liên tiếp. Như vậy sau cùng lắm là ms+1 bước đệ qui, hai dãy giống hệt nhau gồm s số liên tiếp phải xuất hiện. Chúng ta gọi hai dãy này là xi-1,xi-2,...,xi-s, và xj-1, xj-2,...,xk-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ị xi và xj, đượ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ị: xi, xi-1,...,xi-s+1 và xj, xj-1,..., xj-s+1 với tính chất là xi=xj, xi-1=xj-1,...,xi-s+1. Từ đây dẫn đến kết quả là xi+1 đồng nhất với xj+1 và cứ thế tiếp tục. Nhưng điều này có nghĩa là dẫn {xi} là tuần hoàn lặp lại có thể chỉ trừ ra một phần khi bắt đầu dãy. Phần này được gọi là không có chu kỳ. Chúng ta xét một ví dụ để cho dễ hiểu: Dẫy Finabocci (mod 11). Dãy này được định nghĩa như sau: xiº xi-1+xi-2(mod 11) với x1ºx2º1. Chúng ta nhận được liên tiếp các phần tử sau đây của dẫy: 1, 1, 2, 3, 5, 8, 2, 10, 1, 0, 1, 1, 2, 3,... (mod 11) 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à xi được định nghĩa chỉ qua xi-1 và không qua bất kỳ một xk nào khác thì dẫy này được lặp lại theo chu kỳ ngay khi một phần tử xj 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ị xj mới với các xk đứ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 {xi} (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ử: x2iºxi(mod m)? Chứng minh: Trước hết, nếu x2iºxi(mod m) thì dẫy này rõ ràng là tuần hoàn từ x2i 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, xjºxi (mod m) đối với j=i+k |, k=1,2,3,... và mọi i>a (tức là đối với tất cả các phần tử sau phần không tuần hoàn) rút cuộc sẽ có một i với x2iºxi (mod m). Giá trị đầu tiên như vậy của i là i=(l+1)[a/l]. Nếu a>b, thì cách tìm này sẽ phát hiện ra chu kỳ chỉ sau một vài chu kỳ đầy đủ đã bỏ qua, nhưng cuối cùng thế nào cũng tìm được chu kỳ của dẫy. Bây giờ làm thế nào để có thể so sánh x2i với các xi mà không cần phải lưu giữ tất cả các xi? Đơn giản ta chỉ cần tính lại các xi song song với các x2i. Giả sử xi+1=f(xi). Thuật toán tìm chu kỳ có thể mô tả bằng đoạn mã chương trình sau: x:=x1; y:=f(x1); WHILE xy 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 {xi} tuần hoàn (mod p) thì bằng cách nào chúng ta có thể tìm được ước p chưa 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 x2i-xi (mod N) và N. Thường thì d sẽ quay về 1, nhưng ngay khi x2iºxi (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 {xi} 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, x2i-xi) (mod N)=1. Pollard đã phát hiện ra trong một dẫy {xi} các số nguyên ngẫu nhiên (mod P) một phần tử thường hay lặp lại chỉ sau bước. Điều này cũng dễ hiểu nếu chúng ta xem xét lời giải của bài toán Ngày sinh: Cần phải chọn bao nhiêu người một cách ngẫu nhiên để cho xác suất có ít nhất hai người trong số đó trùng ngày sinh lớn hơn 1/2 ? Lời giải: Xác suất để q người không có cùng ngày sinh là Biểu thức này nhỏ hơn <0.5 khi q³23. 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 Vế trái được ước lượng bằng: . Biểu thức này bằng 0.5 nếu. , tức là nếu Đến đây chúng ta có thể phát biểu thuật toán phân tích ra thừa số của Pollard. Thay cho các số nguyên ngẫu nhiên {xi}, chúng ta phải tính một cách đệ qui một dãy được gọi là các số nguyên giả_ngẫu nhiên. Cách lựu chọn đơn giản nhất là chọn xi+1º axi(mod p) với một giá trị cố định của a. Tuy nhiên, lại xảy ra một vấn đề là sự lựa chọn này không sinh ra được các số nguyên đủ ngắn nhiên để cho một chu kỳ ngắn chỉ gồm bước đối với dẫy {xi}. 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: xi+1=x2i+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) nhưng nó cũng chưa đượ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 x2i-xi (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 Qi=(mod N). và áp dụng thuật toán Euclid chỉ khi i là bôi của 100. Bằng cách này, chi phí cho việc sử dụng thuật toán Euclid được giảm một phép nhân và một phép rút gọn (mod N) trên một chu trình. 3.9. Mô tả đại số của phương pháp r của Pollard Có những lý luận đại số khá đơn giản để chỉ ra tại soa một thừa số p của N được tìm thấy sau O() chu trình trong p của Pollard. Lý luận này như sau: yi=x2i-xi=x22i-1+a(x2i-1+a)=x22i-1-x2i-1 =( x2i-1+ xi-1)=( x2i-1+ xi-1)( x2i-2+ x2i-2)( x2i-2- xi-2) . . . =( x2i-1+ xi-1)( x2i-1+ xi-2)...( xi+ x0)( xi- x0) Vì vậy, thừa số yi tham gia trong tích Qi dùng để tính (Qi, N) chứa ít nhất i+1 thừa số đại số. Một thừa số điển hình xk-xi chứa bao nhiêu thừa số nguyên tố khác nhau Êp? Người ta cho rằng số các thừa số nguyên tố ÊG của một số N là vào khoảng lnlnG nếu N đủ lớn. Các số xk tăng cực kỳ nhanh, số chữ số của nó tăng gấp đôi kể từ một chỉ số k nào đó tới chỉ số tiếp theo do phép bình phương xk+1=x2k+a. Bây giờ xk sẽ tăng theo cấp số nhân của x2k0, và sẽ vượt qua ranh giới được gọi là đủ lớn rất nhanh.Vì thế chúng ta thấy rằng số lượng các thừa số nguyên tố ÊG của yi (tích của i+1 số của lớn) sẽ xấp xỉ (i+1) lnlnG. Chạy thuật toán p của Pollard n chu trình, chúng ta tích luỹ trong Qn các số nguyên tố của tất cả thừa số y1,y2,...,yn và cộng tất cả lại, hy vọng sẽ gồm: lnlnG. các thừa số nguyên tố ÊG. Chúng ta phải tiếp tục như thế nào nữa để có thể đảm bảo rằng tất cả các số nguyên tố nhỏ hơn một thừa số p nào đó của N được tích lại trong Qn? Dưới p có số nguyên tố, và do đó n buộc phải lớn vào khoảng , trong đó C là một hằng số. Vì vậy độ phức tạpj của phép tìm một thừa số p bằng phương pháp của Pollard lớn hơn C một chút. Trực giác có thể cho thấy rằng phương pháp p của Pollard là C và do vậy có thể kết luận rằng thừa số C mà ta đưa ra trong thực tế không hẳn là hừng số mà nó thay đổi rất chậm cùng với p. Mô hình đại số của phương pháp p Pollard có gì đó hơi thô, nhưng tuy nhiên chúng ta vẫn có thể sử dụng để nghiên cứu cải tiến phương pháp này và cũng sử dungj để bàn về một vấn đề rất quan trọng : Tốc độ của một thuật toán phân tích thừa số. 3.10. Một chương trình cho phương pháp r của Pollard: Sau đây là một chương trình được viết bằng Pascal thể hiện những gì mà chúng ta đã trình bày ở trên: Program Pollard; Label 1,2; Var a, x1,x,y,Q,i,p,N: Integer; Function Euclid(a,b: Integer): Integer; Var m,n,r: Integer; Begin m:=a; n:=b; While n0 Do Begin r:=m mod n; m:=n; n:=r End; Euclid:=m; End; Begin 1: Write(‘Input a0, 2 and x1 ‘); Read(a); If a=0 Then goto 2; Read(x1); x1:=x1; y:=x1; Q:=1; Write(‘ Input N For factorization: ‘); Read(N); For i:=1 to 10000 do Begin x:=(x*x-a) mod N; y:=(y*y-a) mod N; y:=(y*y-a) mod N; Q:=Q*(y-x) mod N; If i mod 20=0 Then Begin p:=Euclid(Q,N); If p>1 Then While N mod p=0 do Begin Writeln(‘p=’,p:8,’ found for i=’,i:4); N:=N Div p; If N=i Then goto 1 End; End; End; Writeln(‘ No factor found in 10,000 cycles’); Goto 1; 2: End. Chú ý rằng thuật toán này có thể không đúng. Nếu N có một vài ước, thì có thể xảy ra hiện tượng một số ước này bị rút ra giữa hai lần tính toán liên tiếp sử dụng thuật toán Euclid giống hệt như trong phương pháp (p-1). Đúng ra trong trường hợp đó chúng ta phải lưu lại tất cả các giá trị của Q100k, x100k và x200k và chạy lại tính toán từ điển này trở đi với việc sử dụng thuật toán Euclid thường xuyên hơn. Nếu thuật toán hỏng thì toàn bộ thuât toán phải chạy lại từ đầu với môt giá trị khác nhau của a. Cũng lưu ý rằng chương trình Pascal trên đây chỉ là mô hình của mã máy tính có thể thực hiện phương pháp Pollard. Nó chạy nhưng chỉ đối với các giá trị nhỏ của N, nghĩa là các giá trị sao cho N2 nhỏ hơn số nguyên lớn nhất có thể được lưu trữ trong một biến. Để có thể chuyển mô hình này thành một chương trình có thể chạy trên máy, chúng ta phải sử dụng ít nhấ là các biến có thể chạy trên máy, chúng ta phải sử ít nhất là các biến có độ chính xác gấp đôi, hoặc tốt hơn là với độ chính xác cao hơn nữa để sao cho các phép nhân không gây ra sự tràn ô. Hơn nữa, sẽ có lợi nếu không thực hiện các tính toán tìm ước số chúng lớn nhất bằng thuật toán Euclid tại những điểm cách đều mà nên dùng một khoảng nhỏ hơn khi bắt đầu, rồi sau đó mới tăng dần khoảng này lên tới 100 hoặc lớn hơn. Điều đó là để không phải nhận tất cả các thừa số nhỏ của N nhân với nhau tại một giai đoạn nào đó. Vì chi phí phải bỏ ra để có được một thừa số p là tương đương với nên chỉ sử dụng thuật toán Pollard trên các số mà đã được biết là hợp số. Ví dụ: Hãy phân tích ra thừa số 91643 với xi+1=xi-1-1, x0=3. x1=8 x2=63 y1=63-8=55 (55,N)=1; x3=3968 x4º74070 y3ºx4-y2º74004 (74004,N)=1 x5º65061 x6º35191 y3=x6-x3º31225 (31225, N) x7º83746 x8º45368 y4ºx8-x4º62941 (62441,N)=113 => N=113.811. Chương VI. Xây dựng phần mềm phân tích các số dạng 2n-1 4.1.Sơ đồ xuất phát T Begin Nhập N (hợp số) Q=2 a=Random(N) d=gcd(a-1, N)>1 aºaQ mod N d là ước của N Không phân tích được F Q<Q0 Q=Q+1 F T Q0 ngưỡng phân tích Nhận xét: nếu N có các ước p mà p-1 phân tích hoàn toàn trong Q thì gcd(a-1, N)>1 với a=aQ! mod N (ằ" ước p của N, đều có ước nguyên tố lớn của p-1 thì Q rất lớn, và ta có thể lấy Qằ) Thoả hiệp, khống chế số bước tìm Q<Q0 Chỉ sau ÊQ0 bước là thuật toán dừng Trong trường hợp mọi ước nguyên tố p của N ta đều có p-1 có ước > Q0 thì không tìm được ước của N. Khi này ta nói N không phân tích được bằng thuật toán Pollard với ngưỡng Q0. 4.2 Phân tích hệ thống Căn cứ vào sơ đồ xuất phát cần phải có các quy tắc để biểu diễn các số lớn trên máy tính, các cách thực hiện các phép toán số học +, -, *, / , và luỹ thừa trên các số lớn này. 4.2.1. Khai báo số lớn Biểu diễn q phần một số nguyên N Định nghĩa: Cho q>0 khi đó "N $ duy nhất bộ n0, n1,...,nk, với 0Êni<q, sao cho N=n0+n1q+n2q2+...+nkqk (1) (1) được gọi là biểu diễn q phân của số N. Nhận xét: Như vậy, muốn biểu diễn N ta chỉ cần biết bộ (n0, n1,...,nk). Nếu q là một số nhỏ thì việc tìm ra các ni tương đối dễ dàng. ở đây chúng ta chọn q=216(=65536). 3.2.2.Phép cộng số lớn Cho 2 số lớn X và Y: X=(x0, x1, ..., xn) Y=(y0, y1,..., yn) Z=X+Y=( (x0+y0) mod q , (x1+y1+nho0) mod q,...,(xn+yn+nhon-1) mod q ) trong đó nhoi=(xi+yi+nhoi-1)/q. Dưới đây là hàm dùng để cộng hai số lớn. void cong_SL(SL x, SL y) {int i,nho=0,d=do_dai_SL(x),c=do_dai_SL(y); if (c>d) d=c; for (i=0;i<=d;i++) {x[i]+=y[i]; x[i]+=nho; if (x[i]<y[i]) nho=1; else if (x[i]>y[i]) nho=0; } x[d+1]=nho; } 4.2.3.Phép trừ số lớn Tương tự như phép cộng ta có thể thực hiện các phép trừ trên số lớn. Dưới đây là mã chương trình cho phép trừ. void tru_SL(SL x, SL y) {int i,nho=0,d=do_dai_SL(x); for (i=0;i<=d;i++) {if (x[i]>y[i]) {x[i]-=y[i]; x[i]-=nho; nho=0; } else {if (x[i]==y[i]) x[i]=0-nho; else {x[i]-=nho; x[i]-=y[i]; nho=1; } } } } 4.2.4 Phép nhân số lớn Cho các số lớn X và Y. Tích Z của hai số này được định nghĩa như sau: ở đây chúng ta sẽ chia ra làm hai trường hợp đối với phép nhân: nhân một số lớn với một số nhỏ void nhan_WORD(SL x,SL y,WORD k) {int i; LONG t,nho=0; if (k==0) {memset(y,0,2*C);return;} if (k==1) {memcpy(y,x,2*C);return;} memset(y,0,2*C); int d=do_dai_SL(x); for (i=0;i<=d;i++) {t=x[i]; t*=k; nho+=t; y[i]=(WORD) nho; nho>>=16; } y[d+1]=(WORD) nho; } - nhân một số lớn với một số lớn void nhan_SL(SL x,SL y) {int i,j,k,d=do_dai_SL(x); LONG r,t1=0,nho=0; memset(KEP,0,4*C); for (i=0;i<=d;i++) {j=i; for (k=0;k<=i;k++) {r=(LONG) x[k]; r*=y[j--]; t1+=cao(r); nho+=thap(r); } KEP[i]=(WORD) nho; nho>>=16; nho+=t1; t1=0; } for (i=d+1;i<C;i++) {j=i; for (k=0;k<=d;k++) {r=(LONG) x[k]; r*=y[j--]; t1+=cao(r); nho+=thap(r); } KEP[i]=(WORD) nho; nho>>=16; nho+=t1; t1=0; } for (i=C;i<=d+C-1;i++) {j=i-C+1; int s=C-1; for (k=j;k<=d;k++) {r=(LONG) x[k]; r*=y[s--]; t1+=cao(r); nho+=thap(r); } KEP[i]=(WORD) nho; nho>>=16; nho+=t1; t1=0; } while (nho) {KEP[i++]=(WORD) nho; nho>>=16; } 4.2.5 Phép chia số lớn Định lý: Cho X<qY Giả sử X=x0+...+xnqn+xn+1qn+1 Y=y0+...+ynqn Nếu x div y=q thì X div Y=q hoặc q-1 Định lý là cơ sở giúp ta đoán nhanh thương của 2 số lớn X/Y với điều kiện X<qY. X=x0+,...,xnqn Trường hợp mẫu số là số nhỏ WORD chia_WORD(SL TU_SO,WORD mau_so,SL THUONG_SO) {LONG nho=0,dem; memset(THUONG_SO,0,2*C); for (int i=do_dai_SL(TU_SO);i>=0;i--) {nho<<=16; nho^=TU_SO[i]; THUONG_SO[i]=(WORD) (nho/mau_so); nho%=mau_so; } return (WORD) nho; } Trường hợp mẫu số là số lớn char chia_SL(SL TU_SO,SL MAU_SO,SL THUONG_SO,SL SO_DU) { memset(THUONG_SO,0,2*C); memcpy(SO_DU,TU_SO,2*C); if (!be_hon_SL(SO_DU,MAU_SO)) { short d=do_dai_SL(SO_DU),e=do_dai_SL(MAU_SO); if (e) { LONG dau_mod=(LONG) MAU_SO[e]; dau_mod<<=16; dau_mod^=MAU_SO[e-1]; double dd; LONG m;SL z; WORD q; for (short i=d;i>=e;i--) { short j=i-e; if (i<C-1) m=SO_DU[i+1]; else m=0; m<<=16; m+=SO_DU[i]; dd=(double) m; dd*=0x10000; dd+=SO_DU[i-1]; dd/=dau_mod; if (dd>0xffff) {q=0xffff;} else {q=(WORD) dd;} if (q) {nhan_WORD(MAU_SO,z,q); WORD nho=0; for (short k=0;k<e+3;k++) { if ((SO_DU+j)[k]>z[k]) {(SO_DU+j)[k]-=z[k]; (SO_DU+j)[k]-=nho; nho=0; } else { if ((SO_DU+j)[k]==z[k]) (SO_DU+j)[k]=(0-nho); else { (SO_DU+j)[k]-=nho; (SO_DU+j)[k]-=z[k]; nho=1; } } } if (nho) { q-=1; nho=0; for (k=0;k<e+3;k++) {(SO_DU+j)[k]+=MAU_SO[k]; (SO_DU+j)[k]+=nho; if ((SO_DU+j)[k]<MAU_SO[k]) nho=1; else if ((SO_DU+j)[k]>MAU_SO[k]) nho=0; } } } THUONG_SO[j]=q; } } else { memset(SO_DU,0,2*C); SO_DU[0]=chia_WORD(TU_SO,MAU_SO[0],THUONG_SO); } } return ((do_dai_SL(SO_DU))||(SO_DU[0])); 4.2.6 Phép luỹ thừa - Tư tưởng cơ bản của phép luỹ thừa aB mod N B=b0+b12+b222+...+br2r aB=a(b0+b12+b222+...+br2r) lt=1; A=a; for (i=0; i<=r; i++) {if (bi) lt=lt*A; A=A2; } -Cài đặt cụ thể của phép luỹ thừa một số lớn void luy_thua_SL(SL x,SL z) {int b,i,j,dem=0,dk=0,d=do_dai_SL(z); SL y,X[32]; dau_mod=MODULO[C-3]; dau_mod*=Mmax; dau_mod^=MODULO[C-4]; memcpy(X[0],x,2*C); for (i=0;i<5;i++) binh_phuong_mod(X[0]); for (i=1;i<32;i++) {memcpy(X[i],X[i-1],2*C); nhan_mod(X[i],x); } memset(y,0,2*C); y[0]=1; for (i=d;i>=0;i--) {for (j=15;j>=0;j--) {binh_phuong_mod(y); b=(z[i]>>j)&1; dem<<=1; dem+=b; if (dk) {if (dem>=32) {nhan_mod(y,X[dem&31]); dem=0; dk=0; } } else {dem=b; dk=b; } } } if (dk) {if (dem>=32) nhan_mod(y,X[dem&31]); else while (dem) {nhan_mod(y,x); dem--; } } memcpy(x,y,2*C); } } 4.2.7 Tìm UCLN của hai số lớn - Thuật toán tìm UCLN hai số nhỏ của Euclid Function Euclid(a,b: Integer): Integer; Var m,n,r: Integer; Begin m:=a; n:=b; While n0 Do Begin r:=m mod a; m:=n; n:=r ; End; Euclid:=m; End; Thuật toán tìm UCLN hai số lớn char ucln_SL(SL x,SL y,SL UCLN) { SL thuong,SO_DU,X; memcpy(X,x,2*C); memcpy(UCLN,y,2*C); chia_SL(X,UCLN,thuong,SO_DU); while (SO_DU[0]||(do_dai_SL(SO_DU))) { memcpy(X,UCLN,2*C); memcpy(UCLN,SO_DU,2*C); chia_SL(X,UCLN,thuong,SO_DU); } return ((UCLN[0]==1)&&(!(do_dai_SL(UCLN)))); } 4.3 Cài đặt chương trình 4.3.1 Mô tả qúa trình thực hiện Xây dựng một chương trình tìm và ghi lên một tệp các số nguyên tố nhỏ hơn 216. Tệp này có 6542 số nguyên tố, nó sẽ giúp chương trình bước đầu tìm ra các ước nguyên tố nhỏ của một số lớn nào đó. (1) Tìm các ước nguyên tố nhỏ của M Cho i và tính M=2i-1 bằng hàm Mersenne_SL(); in M Phân tích M bằng hàm Phân_tich_Word Đọc một số nguyên tố a từ tệp các số nguyên tố nhỏ Nếu M không chia hết cho a thì quay lên bước a) để đọc số tiếp theo. Thực hiện phép chia M cho a, bằng hàm Chia_Word Nếu M không chia hết cho a thì hàm lại bước này đối với thương của phép chia M cho a. Nếu đến một lúc nào đó ta thu được một thương bằng một số nguyên tố trong tệp hoặc chia hết cho một số trong tệp thì dừng chương trình và kết luận đã phân tích hoàn toàn và tích của các thừa số nguyên tố là ước của M chính là bằng M. Nếu đọc hết tệp mà thương cuối cùng không trùng với bất kỳ số nào trong tệp hoặc không chia hết cho bất cứ số nào trong tệp nào thì phải phân tích xem thương này có phải là số nguyên tố không bằng cách dùng hàm nguyên_to_SL. Nếu xác định thương này là nguyên tố thì dừng chương trình và kết luận là “ phân tích hoàn toàn”. Ngược lại thì chuyển sang giai đoạn (2). Dùng thuật toán Pollard 1 để phân tích ước hợp số Z của M Lấy ngẫu nhiên một số lớn a=Random_SL(Z); khởi đầu lấy Q=2; Dùng hàm UCLN_SL để tìm ước chung lớn nhất của Z và aQ-1. Nếu UCLN này lớn hơn 1 thì đây sẽ là một ước của Z và in ra đã tìm được ước. Ngược lại thì tăng Q lên 1 và làm lại bước này cho đến khi tìm được một ước hoặc khi Q vượt qua một số Q0 đủ lớn nào đó thì dừng (thường ta chọn Q0=65356). Trong trường hợp này thì ta nói “ không phân tích hoàn toàn” . 4.4 Sơ đồ khối của các Modulo thuộc chương trình Begin Input i TínhM=2n-1 Tìm ước nhỏ < 216 Ước còn lại là nguyên tố Phân tích hoàn toàn Pollard1 Ước nguyên tố Ước còn lại Không phân tích hoàn toàn T T F F a) Sơ đồ khối của chương trình chính b) Pollard1 Input Z là hợp số i=2 X=random(Z) X=Xi mod Z gdc(X-1, Z)=P P>1 Pollard=1 P và Z=Z/P là 2 ước của Z i=i+1 i<I0 Pollard=0 Không phân tích được F T F T Phụ lục 1: Kết qủa phân tích các số 2n-1, (n<200) 2^2-1=3=3, 2^3-1=7=7, 2^4-1=15=3*5, 2^5-1=31=31, 2^6-1=63=3*3*7, 2^7-1=127=127, 2^8-1=255=3*5*17, 2^9-1=511=7*73, 2^10-1=1023=3*11*31, 2^11-1=2047=23*89, 2^12-1=4095=3*3*5*7*13, 2^13-1=8191=8191, 2^14-1=16383=3*43*127, 2^15-1=32767=7*31*151, 2^16-1=65535=3*5*17*257, 2^17-1=131071=131071, 2^18-1=262143=3*3*3*7*19*73, 2^19-1=524287=524287, 2^20-1=1048575=3*5*5*11*31*41, 2^21-1=2097151=7*7*127*337, 2^22-1=4194303=3*23*89*683, 2^23-1=8388607=47*178481, 2^24-1=16777215=3*3*5*7*13*17*241, 2^25-1=33554431=31*601*1801, 2^26-1=67108863=3*2731*8191, 2^27-1=134217727=7*73*262657, 2^28-1=268435455=3*5*29*43*113*127, 2^29-1=536870911=233*1103*2089, 2^30-1=1073741823=3*3*7*11*31*151*331, 2^31-1=2147483647=2147483647, 2^32-1=4294967295=3*5*17*257*65537, 2^33-1=8589934591=7*23*89*599479, 2^34-1=17179869183=3*43691*131071, 2^35-1=34359738367=31*71*127*122921, 2^36-1=68719476735=3*3*3*5*7*13*19*37*73*109, 2^37-1=137438953471=223*616318177, 2^38-1=274877906943=3*174763*524287, 2^39-1=549755813887=7*79*8191*121369, 2^40-1=1099511627775=3*5*5*11*17*31*41*61681, 2^41-1=2199023255551=13367*164511353, 2^42-1=4398046511103=3*3*7*7*43*127*337*5419, 2^43-1=8796093022207=431*9719*2099863, 2^44-1=17592186044415=3*5*23*89*397*683*2113, 2^45-1=35184372088831=7*31*73*151*631*23311, 2^46-1=70368744177663=3*47*178481*2796203, 2^47-1=140737488355327=2351*4513*13264529, 2^48-1=281474976710655=3*3*5*7*13*17*97*241*257*673, 2^49-1=562949953421311=127*4432676798593, 2^50-1=1125899906842623=3*11*31*251*601*1801*4051, 2^51-1=2251799813685247=7*103*2143*11119*131071, 2^52-1=4503599627370495=3*5*53*157*1613*2731*8191, 2^53-1=9007199254740991=6361*69431*20394401, 2^54-1=18014398509481983=3*3*3*3*7*19*73*87211*262657, 2^55-1=36028797018963967=23*31*89*881*3191*201961, 2^56-1=72057594037927935=3*5*17*29*43*113*127*15790321, 2^57-1=144115188075855871=7*32377*524287*1212847, 2^58-1=288230376151711743=3*59*233*1103*2089*3033169, 2^59-1=576460752303423487=179951*3203431780337, 2^60-1=1152921504606846975=3*3*5*5*7*11*13*31*41*61*151*331*1321, 2^61-1=2305843009213693951=2305843009213693951, 2^62-1=4611686018427387903=3*715827883*2147483647, 2^63-1=9223372036854775807=7*7*73*127*337*92737*649657, 2^64-1=18446744073709551615=3*5*17*257*641*65537*6700417, 2^65-1=36893488147419103231=31*8191*145295143558111, 2^66-1=73786976294838206463=3*3*7*23*67*89*683*20857*599479, 2^67-1=147573952589676412927=193707721*761838257287, 2^68-1=295147905179352825855=3*5*137*953*26317*43691*131071, 2^69-1=590295810358705651711=7*47*178481*10052678938039, 2^70-1=1180591620717411303423=3*11*31*43*71*127*281*86171*122921, 2^71-1=2361183241434822606847=228479*10334355636337793, 2^72-1=4722366482869645213695=3*3*3*5*7*13*17*19*37*73*109*241*433*38737, 2^73-1=9444732965739290427391=439*2298041*9361973132609, 2^74-1=18889465931478580854783=3*223*1777*25781083*616318177, 2^75-1=37778931862957161709567=7*31*151*601*1801*100801*10567201, 2^76-1=75557863725914323419135=3*5*229*457*174763*524287*525313, 2^77-1=151115727451828646838271=23*89*127*581283643249112959, 2^78-1=302231454903657293676543=3*3*7*79*2731*8191*121369*22366891, 2^79-1=604462909807314587353087=2687*202029703*1113491139767, 2^80-1=1208925819614629174706175 =3*5*5*11*17*31*41*257*61681*4278255361, 2^81-1=2417851639229258349412351=7*73*2593*71119*262657*97685839, 2^82-1=4835703278458516698824703=3*83*13367*164511353*8831418697, 2^83-1=9671406556917033397649407=167*57912614113275649087721, 2^84-1=19342813113834066795298815 =3*3*5*7*7*13*29*43*113*127*337*1429*5419*14449, 2^85-1=38685626227668133590597631=31*131071*9520972806333758431, 2^86-1=77371252455336267181195263=3*431*9719*2099863*2932031007403, 2^87-1=154742504910672534362390527 =7*233*1103*2089*4177*9857737155463, 2^88-1=309485009821345068724781055 =3*5*17*23*89*353*397*683*2113*2931542417, 2^89-1=618970019642690137449562111=618970019642690137449562111, 2^90-1=1237940039285380274899124223 =3*3*3*7*11*19*31*73*151*331*631*23311*18837001, 2^91-1=2475880078570760549798248447=127*911*8191*2612585917490982161, 2^92-1=4951760157141521099596496895 =3*5*47*277*1013*1657*30269*178481*2796203, 2^93-1=9903520314283042199192993791=7*2147483647*658812288653553079, 2^94-1=19807040628566084398385987583 =3*283*2351*4513*13264529*165768537521, 2^95-1=39614081257132168796771975167 =31*191*524287*12761021422289693921, 2^96-1=79228162514264337593543950335 =3*3*5*7*13*17*97*193*241*257*673*65537*22253377, 2^97-1=158456325028528675187087900671 =11447*13842607235828485645766393, 2^98-1=316912650057057350374175801343 =3*43*127*4363953127297*4432676798593, 2^99-1=633825300114114700748351602687 =7*23*73*89*199*153649*599479*33057806959, 2^100-1=1267650600228229401496703205375 =3*5*5*5*11*31*41*101*251*601*1801*4051*8101*268501, 2^101-1=2535301200456458802993406410751 =7432339208719*341117531003194129, 2^102-1=5070602400912917605986812821503=3*3*7*103*307*2143*2857*6529*11119*43691*131071, 2^103-1=10141204801825835211973625643007=2550183799*3976656429941438590393, 2^104-1=20282409603651670423947251286015=3*5*17*53*157*1613*2731*8191*858001*308761441, 2^105-1=40564819207303340847894502572031=7*7*31*71*127*151*337*29191*106681*122921*152041, 2^106-1=81129638414606681695789005144063=3*107*6361*69431*20394401*28059810762433, 2^107-1=162259276829213363391578010288127=162259276829213363391578010288127, 2^108-1=324518553658426726783156020576255=3*3*3*3*5*7*13*19*37*73*109*87211*246241*262657*279073, 2^109-1=649037107316853453566312041152511=745988807*870035986098720987332873, 2^110-1=1298074214633706907132624082305023=3*11*11*23*31*89*683*881*2971*3191*201961*48912491, 2^111-1=2596148429267413814265248164610047=7*223*321679*26295457*319020217*616318177, 2^112-1=5192296858534827628530496329220095=3*5*17*29*43*113*127*257*5153*15790321*54410972897, 2^113-1=10384593717069655257060992658440191=3391*23279*65993*1868569*1066818132868207, 2^114-1=20769187434139310514121985316880383=3*3*7*571*32377*174763*524287*1212847*160465489, 2^115-1=41538374868278621028243970633760767=31*47*14951*178481*4036961*2646507710984041, 2^116-1=83076749736557242056487941267521535=3*5*59*233*1103*2089*3033169*57646075230342349, 2^117-1=166153499473114484112975882535043071=7*73*79*937*6553*8191*86113*121369*7830118297, 2^118-1=332306998946228968225951765070086143=3*2833*37171*179951*1824726041*3203431780337, 2^119-1=664613997892457936451903530140172287=127*239*20231*131071*62983048367*131105292137, 2^120-1=1329227995784915872903807060280344575=3*3*5*5*7*11*13*17*31*41*61*151*241*331*1321*61681*4562284561, 2^121-1=2658455991569831745807614120560689151=23*89*727*1786393878363164227858270210279, 2^122-1=5316911983139663491615228241121378303=3*768614336404564651*2305843009213693951, 2^123-1=10633823966279326983230456482242756607=7*13367*3887047*164511353*177722253954175633, 2^124-1=21267647932558653966460912964485513215=3*5*5581*8681*49477*384773*715827883*2147483647, 2^125-1=42535295865117307932921825928971026431=31*601*1801*269089806001*4710883168879506001, 2^126-1=85070591730234615865843651857942052863=3*3*3*7*7*19*43*73*127*337*5419*92737*649657*77158673929, 2^127-1=170141183460469231731687303715884105727=170141183460469231731687303715884105727, 2^128-1=340282366920938463463374607431768211455=3*5*17*257*641*65537*274177*6700417*67280421310721, 2^129-1=680564733841876926926749214863536422911=7*431*9719*2099863*11053036065049294753459639, 2^130-1=1361129467683753853853498429727072845823=3*11*31*131*2731*8191*409891*7623851*145295143558111, 2^131-1=2722258935367507707706996859454145691647=263*10350794431055162386718619237468234569, 2^132-1=5444517870735015415413993718908291383295=3*3*5*7*13*23*67*89*397*683*2113*20857*312709*599479*4327489, 2^133-1=10889035741470030830827987437816582766591=127*524287*163537220852725398851434325720959, 2^134-1=21778071482940061661655974875633165533183=3*7327657*193707721*761838257287*6713103182899, 2^135-1=43556142965880123323311949751266331066367=7*31*73*151*271*631*23311*262657*348031*49971617830801, 2^136-1=87112285931760246646623899502532662132735=3*5*17*17*137*953*26317*43691*131071*354689*2879347902817, 2^137-1=174224571863520493293247799005065324265471=174224571863520493293247799005065324265471 (hop so) 2^138-1=348449143727040986586495598010130648530943=3*3*7*47*139*178481*2796203*168749965921*10052678938039, 2^139-1=696898287454081973172991196020261297061887=5625767248687*123876132205208335762278423601, 2^140-1=1393796574908163946345982392040522594123775=3*5*5*11*29*31*41*43*71*113*127*281*86171*122921*7416361*47392381, 2^141-1=2787593149816327892691964784081045188247551=7*2351*4513*13264529*4375578271*646675035253258729, 2^142-1=5575186299632655785383929568162090376495103=3*228479*56409643*13952598148481*10334355636337793, 2^143-1=11150372599265311570767859136324180752990207=23*89*8191*724153*158822951431*5782172113400990737, 2^144-1=22300745198530623141535718272648361505980415=3*3*3*5*7*13*17*19*37*73*97*109*241*257*433*577*673*38737*487824887233, 2^145-1=44601490397061246283071436545296723011960831=31*233*1103*2089*2679895157783862814690027494144991, 2^146-1=89202980794122492566142873090593446023921663=3*439*1753*2298041*9361973132609*1795918038741070627, 2^147-1=178405961588244985132285746181186892047843327=7*7*7*127*337*4432676798593*2741672362528725535068727, 2^148-1=356811923176489970264571492362373784095686655=3*5*149*223*593*1777*25781083*184481113*231769777*616318177, 2^149-1=713623846352979940529142984724747568191373311=713623846352979940529142984724747568191373311 (hop so) 2^150-1=1427247692705959881058285969449495136382746623=3*3*7*11*31*151*251*331*601*1801*4051*100801*10567201*1133836730401, 2^151-1=2854495385411919762116571938898990272765493247=18121*55871*165799*2332951*7289088383388253664437433, 2^152-1=5708990770823839524233143877797980545530986495=3*5*17*229*457*1217*148961*174763*524287*525313*24517014940753, 2^153-1=11417981541647679048466287755595961091061972991=7*73*103*919*2143*11119*131071*75582488424179347083438319, 2^154-1=22835963083295358096932575511191922182123945983=3*23*43*89*127*617*683*78233*35532364099*581283643249112959, 2^155-1=45671926166590716193865151022383844364247891967=31*31*311*11471*73471*2147483647*4649919401*18158209813151, 2^156-1=91343852333181432387730302044767688728495783935=3*3*5*7*13*13*53*79*157*313*1249*1613*2731*3121*8191*21841*121369*22366891, 2^157-1=182687704666362864775460604089535377456991567871=852133201*60726444167*1654058017289*2134387368610417, 2^158-1=365375409332725729550921208179070754913983135743=3*2687*202029703*1113491139767*201487636602438195784363, 2^159-1=730750818665451459101842416358141509827966271487=7*6361*6679*69431*13960201*20394401*540701761*229890275929, 2^160-1=1461501637330902918203684832716283019655932542975=3*5*5*11*17*31*41*257*61681*65537*414721*4278255361*44479210368001, 2^161-1=2923003274661805836407369665432566039311865085951=47*127*1289*178481*3188767*45076044553*14808607715315782481, 2^162-1=5846006549323611672814739330865132078623730171903=3*3*3*3*3*7*19*73*163*2593*71119*87211*135433*262657*97685839*272010961, 2^163-1=11692013098647223345629478661730264157247460343807=150287*704161*110211473*27669118297*36230454570129675721, 2^164-1=23384026197294446691258957323460528314494920687615=3*5*83*10169*13367*181549*12112549*43249589*164511353*8831418697, 2^165-1=46768052394588893382517914646921056628989841375231=7*23*31*89*151*881*3191*201961*599479*2048568835297380486760231, 2^166-1=93536104789177786765035829293842113257979682750463=3*167*499*1163*2657*155377*13455809771*57912614113275649087721, 2^167-1=187072209578355573530071658587684226515959365500927=2349023*79638304766856507377778616296087448490695649, 2^168-1=374144419156711147060143317175368453031918731001855=3*3*5*7*7*13*17*29*43*113*127*241*337*1429*3361*5419*14449*15790321*88959882481, 2^169-1=748288838313422294120286634350736906063837462003711=4057*8191*22517871350031141032145384333278160948994153 (hop so) 2^170-1=1496577676626844588240573268701473812127674924007423=3*11*31*43691*131071*9520972806333758431*26831423036065352611, 2^171-1=2993155353253689176481146537402947624255349848014847=7*73*32377*524287*1212847*93507247*3042645634792541312037847, 2^172-1=5986310706507378352962293074805895248510699696029695=3*5*173*431*9719*101653*500177*2099863*1759217765581*2932031007403, 2^173-1=11972621413014756705924586149611790497021399392059391=730753*1505447*10883113847869730192653064467986444125801 (hop so) 2^174-1=23945242826029513411849172299223580994042798784118783=3*3*7*59*233*1103*2089*4177*3033169*9857737155463*96076791871613611, 2^175-1=47890485652059026823698344598447161988085597568237567=31*71*127*601*1801*39551*122921*60816001*535347624791488552837151, 2^176-1=95780971304118053647396689196894323976171195136475135=3*5*17*23*89*257*353*397*683*2113*229153*2931542417*5255099554003739617, 2^177-1=191561942608236107294793378393788647952342390272950271=7*179951*184081*27989941729*3203431780337*9213624084535989031, 2^178-1=383123885216472214589586756787577295904684780545900543=3*179*62020897*18584774046020617*618970019642690137449562111, 2^179-1=766247770432944429179173513575154591809369561091801087=359*1433*1489459109360039866456940197095433721664951999121, 2^180-1=1532495540865888858358347027150309183618739122183602175=3*3*3*5*5*7*11*13*19*31*37*41*61*73*109*151*181*331*631*1321*23311*54001*18837001*29247661, 2^181-1=3064991081731777716716694054300618367237478244367204351=43441*1164193*7648337*7923871097285295625344647665764672671, 2^182-1=6129982163463555433433388108601236734474956488734408703=3*43*127*911*2731*8191*224771*1210483*25829691707*2612585917490982161, 2^183-1=12259964326927110866866776217202473468949912977468817407=7*367*55633*2305843009213693951*37201708625305146303973352041, 2^184-1=24519928653854221733733552434404946937899825954937634815=3*5*17*47*277*1013*1657*30269*178481*2796203*291280009243618888211558641, 2^185-1=49039857307708443467467104868809893875799651909875269631=31*223*616318177*11510062038035036086898638569115182202584031 (hop so) 2^186-1=98079714615416886934934209737619787751599303819750539263=3*3*7*715827883*2147483647*658812288653553079*1537228672093301419, 2^187-1=196159429230833773869868419475239575503198607639501078527=23*89*131071*707983*1032670816743843860998850056278950666491537, 2^188-1=392318858461667547739736838950479151006397215279002157055=3*5*283*2351*3761*4513*13264529*7484047069*165768537521*140737471578113, 2^189-1=784637716923335095479473677900958302012794430558004314111=7*7*73*127*337*92737*262657*649657*1560007*207617485544258392970753527, 2^190-1=1569275433846670190958947355801916604025588861116008628223=3*11*31*191*2281*174763*524287*3011347479614249131*12761021422289693921, 2^191-1=3138550867693340381917894711603833208051177722232017256447=383*7068569257*39940132241*332584516519201*87274497124602996457, 2^192-1=6277101735386680763835789423207666416102355444464034512895=3*3*5*7*13*17*97*193*241*257*641*673*65537*6700417*22253377*18446744069414584321, 2^193-1=12554203470773361527671578846415332832204710888928069025791=13821503*61654440233248340616559*14732265321145317331353282383, 2^194-1=25108406941546723055343157692830665664409421777856138051583=3*971*1553*11447*31817*1100876018364883721*13842607235828485645766393, 2^195-1=50216813883093446110686315385661331328818843555712276103167 =7*31*79*151*8191*121369*145295143558111*134304196845099262572814573351, 2^196-1=100433627766186892221372630771322662657637687111424552206335 =3*5*29*43*113*127*197*19707683773*4363953127297*4432676798593*4981857697937, 2^197-1=200867255532373784442745261542645325315275374222849104412671=7487*26828803997912886929710867041891989490486893845712448833, 2^198-1=401734511064747568885490523085290650630550748445698208825343 =3*3*3*7*19*23*67*73*89*199*683*5347*20857*153649*599479*33057806959*242099935645987, 2^199-1=803469022129495137770981046170581301261101496891396417650687 =164504919713*4884164093883941177660049098586324302977543600799, 2^200-1=1606938044258990275541962092341162602522202993782792835301375 =3*5*5*5*11*17*31*41*101*251*401*601*1801*4051*8101*61681*268501*340801*2787601*3173389601. Kết luận Bài toán phân tích số nguyên ra thừa số nguyên tố ra đời từ rất lâu đã được nhiều người biết đến và bỏ công sức ra nghiên cứu. Trong thời gian làm đề tài tốt nghiệp em đã có dịp tìm hiểu và nghiên cứu xâu hơn về các thuật toán phân tích số nguyên ra thừa số nguyên tố. Bắt đầu là những thuật toán đơn giản như: thuật toán sàng Eratosthenes, sàng đồng dư và cuối cùng là những thuật toán rất phức tạp như: thuật toán r của Pollard, thuật toán p-1 của Pollard. Đồng thời, trong thời gian này em đã học thêm được một số kỹ thuật lập trình và một số thuật toán trong ngôn ngữ lập trình C++. Em đã biết phân tích hệ thống để giải một bài toán phức tạp và có thể viết chương trình để giải quyết bài toán đó. Kết quả chính của đề tài là xây dựng được một chương trình có thể phân tích được tất cả các số nguyên có dạng 2n-1, với n<200, ra các thừa số nguyên tố. Vì thời gian cũng như khả năng của em còn hạn chế nên chưa giải quyết được bài toán với số mũ n Ê 200. Có thể trong thời gian tới nếu như em vẫn được tiếp tục nghiên cứu theo hướng này thì có thể tăng độ lớn của số cần phân tích bằng những thuật toán mới và hữu hiệu hơn. Phụ lục 2. Chương trình nguồn #include #define C_max 100 #define M16 65535 #define Mmax 65536 #define thap(x) ((x)&M16) #define cao(x) ((x)>>16) typedef unsigned short WORD; typedef unsigned long LONG; typedef WORD SL[C_max]; WORD C,KEP[2*C_max]; LONG dau_mod; SL SO_MU,D,MODULO; int do_dai_SL(SL x) {int i=C-1; while ((x[i]==0)&&(i>0)) i--; return i; } int be_hon_SL(SL x,SL y) {int i=C-1; while (x[i]==y[i] && (i>0)) i--; return (x[i]<y[i]); } int bang_nhau_SL(SL x,SL y) {return (!be_hon_SL(x,y)&&!be_hon_SL(y,x)); } void cong_SL(SL x, SL y) {int i,nho=0,d=do_dai_SL(x),c=do_dai_SL(y); if (c>d) d=c; for (i=0;i<=d;i++) {x[i]+=y[i]; x[i]+=nho; if (x[i]<y[i]) nho=1; else if (x[i]>y[i]) nho=0; } x[d+1]=nho; } void tru_SL(SL x, SL y) {int i,nho=0,d=do_dai_SL(x); for (i=0;i<=d;i++) {if (x[i]>y[i]) {x[i]-=y[i]; x[i]-=nho; nho=0; } else {if (x[i]==y[i]) x[i]=0-nho; else {x[i]-=nho; x[i]-=y[i]; nho=1; } } } } void nhan_WORD(SL x,SL y,WORD k) {int i; LONG t,nho=0; if (k==0) {memset(y,0,2*C);return;} if (k==1) {memcpy(y,x,2*C);return;} memset(y,0,2*C); int d=do_dai_SL(x); for (i=0;i<=d;i++) {t=x[i]; t*=k; nho+=t; y[i]=(WORD) nho; nho>>=16; } y[d+1]=(WORD) nho; } void nhan_SL(SL x,SL y) {int i,j,k,d=do_dai_SL(x); LONG r,t1=0,nho=0; memset(KEP,0,4*C); for (i=0;i<=d;i++) {j=i; for (k=0;k<=i;k++) {r=(LONG) x[k]; r*=y[j--]; t1+=cao(r); nho+=thap(r); } KEP[i]=(WORD) nho; nho>>=16; nho+=t1; t1=0; } for (i=d+1;i<C;i++) {j=i; for (k=0;k<=d;k++) {r=(LONG) x[k]; r*=y[j--]; t1+=cao(r); nho+=thap(r); } KEP[i]=(WORD) nho; nho>>=16; nho+=t1; t1=0; } for (i=C;i<=d+C-1;i++) {j=i-C+1; int s=C-1; for (k=j;k<=d;k++) {r=(LONG) x[k]; r*=y[s--]; t1+=cao(r); nho+=thap(r); } KEP[i]=(WORD) nho; nho>>=16; nho+=t1; t1=0; } while (nho) {KEP[i++]=(WORD) nho; nho>>=16; } } void binh_phuong_SL(SL x) {int i,j,k,d,s; LONG r,t1=0,nho=0; memset(KEP,0,4*C); nho=(LONG) x[0]; nho*=x[0]; KEP[0]=(WORD) nho; nho>>=16; d=do_dai_SL(x); for (i=1;i<=d;i++) {s=i>>1; if ((i&1)==0) {r=(LONG) x[s]; r*=x[s]; t1+=r>>16; nho+=thap(r); s--; } j=i; for (k=0;k<=s;k++) {r=(LONG) x[k]; r*=x[j--]; t1+=(r>>16)<<1; nho+=(thap(r)<<1); } KEP[i]=(WORD) nho; nho>>=16; nho+=t1; t1=0; } for (i=d+1;i<=d*2;i++) {s=i>>1; if ((i&1)==0) {r=(LONG) x[s]; r*=x[s]; nho+=thap(r); t1+=cao(r); s--; } j=d; for (k=i-d;k<=s;k++) {r=(LONG) x[k]; r*=x[j--]; t1+=(r>>16)<<1; nho+=thap(r)<<1; } KEP[i]=(WORD) nho; nho>>=16; nho+=t1; t1=0; } while (nho) {KEP[i++]=(WORD) nho; nho>>=16; } } void modulo_SL(SL r) {int d=2*C-1; while ((KEP[d]==0)&&(d>0)) d--; if (d<C-3) {memcpy(r,KEP,2*C); return; } double dd; LONG m;SL z; WORD q; for (int i=d;i>=C-3;i--) {int j=i-C+3; m=KEP[i+1]; m<<=16; m+=KEP[i]; dd=(double) m; dd*=Mmax; dd+=KEP[i-1]; dd/=dau_mod; if ((LONG)dd==Mmax) q=M16;else q=(WORD) dd; if (q) {nhan_WORD(MODULO,z,q); WORD nho=0; for (int k=0;k<C-1;k++) {if ((KEP+j)[k]>z[k]) {(KEP+j)[k]-=z[k]; (KEP+j)[k]-=nho; nho=0; } else {if ((KEP+j)[k]==z[k]) (KEP+j)[k]=0-nho; else {(KEP+j)[k]-=nho; (KEP+j)[k]-=z[k]; nho=1; } } } if (nho) {q-=1; nho=0; for (k=0;k<C-1;k++) {(KEP+j)[k]+=MODULO[k]; (KEP+j)[k]+=nho; if ((KEP+j)[k]<MODULO[k]) nho=1; else if ((KEP+j)[k]>MODULO[k]) nho=0; } } } } memcpy(r,KEP,2*C); } void nhan_mod(SL x,SL y) {nhan_SL(x,y); modulo_SL(x); } void binh_phuong_mod(SL x) {binh_phuong_SL(x); modulo_SL(x); } void luy_thua_SL(SL x,SL z) {int b,i,j,dem=0,dk=0,d=do_dai_SL(z); SL y,X[32]; dau_mod=MODULO[C-3]; dau_mod*=Mmax; dau_mod^=MODULO[C-4]; memcpy(X[0],x,2*C); for (i=0;i<5;i++) binh_phuong_mod(X[0]); for (i=1;i<32;i++) {memcpy(X[i],X[i-1],2*C); nhan_mod(X[i],x); } memset(y,0,2*C); y[0]=1; for (i=d;i>=0;i--) {for (j=15;j>=0;j--) {binh_phuong_mod(y); b=(z[i]>>j)&1; dem<<=1; dem+=b; if (dk) {if (dem>=32) {nhan_mod(y,X[dem&31]); dem=0; dk=0; } } else {dem=b; dk=b; } } } if (dk) {if (dem>=32) nhan_mod(y,X[dem&31]); else while (dem) {nhan_mod(y,x); dem--; } } memcpy(x,y,2*C); } WORD chia_WORD(SL TU_SO,WORD mau_so,SL THUONG_SO) {LONG nho=0,dem; memset(THUONG_SO,0,2*C); for (int i=do_dai_SL(TU_SO);i>=0;i--) {nho<<=16; nho^=TU_SO[i]; THUONG_SO[i]=(WORD) (nho/mau_so); nho%=mau_so; } return (WORD) nho; } char chia_SL(SL TU_SO,SL MAU_SO,SL THUONG_SO,SL SO_DU) { memset(THUONG_SO,0,2*C); memcpy(SO_DU,TU_SO,2*C); if (!be_hon_SL(SO_DU,MAU_SO)) { short d=do_dai_SL(SO_DU),e=do_dai_SL(MAU_SO); if (e) { LONG dau_mod=(LONG) MAU_SO[e]; dau_mod<<=16; dau_mod^=MAU_SO[e-1]; double dd; LONG m;SL z; WORD q; for (short i=d;i>=e;i--) { short j=i-e; if (i<C-1) m=SO_DU[i+1]; else m=0; m<<=16; m+=SO_DU[i]; dd=(double) m; dd*=0x10000; dd+=SO_DU[i-1]; dd/=dau_mod; if (dd>0xffff) {q=0xffff;} else {q=(WORD) dd;} if (q) {nhan_WORD(MAU_SO,z,q); WORD nho=0; for (short k=0;k<e+3;k++) { if ((SO_DU+j)[k]>z[k]) {(SO_DU+j)[k]-=z[k]; (SO_DU+j)[k]-=nho; nho=0; } else { if ((SO_DU+j)[k]==z[k]) (SO_DU+j)[k]=(0-nho); else { (SO_DU+j)[k]-=nho; (SO_DU+j)[k]-=z[k]; nho=1; } } } if (nho) { q-=1; nho=0; for (k=0;k<e+3;k++) {(SO_DU+j)[k]+=MAU_SO[k]; (SO_DU+j)[k]+=nho; if ((SO_DU+j)[k]<MAU_SO[k]) nho=1; else if ((SO_DU+j)[k]>MAU_SO[k]) nho=0; } } } THUONG_SO[j]=q; } } else { memset(SO_DU,0,2*C); SO_DU[0]=chia_WORD(TU_SO,MAU_SO[0],THUONG_SO); } } return ((do_dai_SL(SO_DU))||(SO_DU[0])); } #include #include #include #include #include #include void hien(SL x) {for (int i=0;i<do_dai_SL(x)+1;i++) {printf("%04X ",x[i]);} } SL X_10; void doi_16_10(SL x) { SL z;LONG nho; memcpy(z,x,2*C); memset(X_10,0,2*C_max); int i=0,k=do_dai_SL(z); while (k||(z[0]>0)) { nho=0; for (int j=k;j>=0;j--) { nho<<=16;nho^=z[j]; z[j]=nho/10000; nho%=10000; } X_10[i]=nho; i++; k=do_dai_SL(z); } } void hien_10(SL t) { doi_16_10(t); short k=C_max-1; while ((k>0)&&(X_10[k]==0)) k--; short u=wherex(); if ((80-u)<(4*(k+1))) printf("\n "); printf(" %u",X_10[k]); for (short i=k-1;i>=0;i--) printf("%04u",X_10[i]); printf(" "); } void random_SL(SL x) { randomize(); memset(x,0,2*C); for (int i=0;i<C-3;i++) {x[i]=random(256);x[i]<<=8;x[i]+=random(256); } } char ucln_SL(SL x,SL y,SL UCLN) { SL thuong,SO_DU,X; memcpy(X,x,2*C); memcpy(UCLN,y,2*C); chia_SL(X,UCLN,thuong,SO_DU); while (SO_DU[0]||(do_dai_SL(SO_DU))) { memcpy(X,UCLN,2*C); memcpy(UCLN,SO_DU,2*C); chia_SL(X,UCLN,thuong,SO_DU); } return ((UCLN[0]==1)&&(!(do_dai_SL(UCLN)))); } void tru_1(SL a,SL x) { memcpy(x,a,2*C); short i=0; while ((i<C)&&(x[i]==0)) { x[i]=0xffff; i++; } x[i]--; } char bang_nhau(SL x,WORD k) { return (!do_dai_SL(x)&&(x[0]==k)); } char pollard_1(SL x,SL uoc_so) { SL X,Y,Z; C=do_dai_SL(x)+3; memcpy(MODULO,x,2*C); memcpy(Y,x,2*C); char b=1; { short hd=wherex(),td=wherey(); long i=2; memset(SO_MU,0,2*C); SO_MU[0]=(WORD) i; random_SL(X); b=ucln_SL(Y,X,uoc_so); if (b) { tru_1(X,Z); b=ucln_SL(Y,Z,uoc_so); while ((b)&&(i<0x10000)&&(!bang_nhau(Z,1))) { luy_thua_SL(X,SO_MU); tru_1(X,Z); b=ucln_SL(Y,Z,uoc_so); gotoxy(hd,td); textcolor(10);clreol(); printf("Dung phuong phap Pollard_1 de phan tich den so mu B=%lu! ",i); textcolor(15);clreol(); i++; SO_MU[0]=(WORD) i; long l=i>>16; SO_MU[1]=(WORD) l; } /* i=0; hd=wherex(); FILE *f; f=fopen("co_so_24.ngt","rb"); while ((b)&&(i<1071328)&&(!bang_nhau(Z,1))) { fread(&SO_MU,4,1,f); long l=SO_MU[1]; l<<=16; l+=SO_MU[0]; luy_thua_SL(X,SO_MU); tru_1(X,Z); b=ucln_SL(Y,Z,uoc_so); gotoxy(hd,td); printf("vong 2 den so= %7lu",l); i++; } fclose(f);*/ } } return b; } SL X; void tao_so_Marsene_SL(short k) { C=k>>4;C+=2;if (k&15) C+=1; memset(X,0,2*C); short h=k>>4; memset(X,0xffff,2*(h+1)); short a=k&15; if (a) {X[h]=0xffff>>(16-a);} else {X[h]=0;} } char nguyen_to_SL(SL x,WORD k) { WORD b; char ok; short hd,td; if (do_dai_SL(x)) { textbackground(1);clreol(); printf(" Kiem tra so: "); textbackground(0);textcolor(14);clreol(); hien_10(x); textbackground(4);textcolor(14);clreol(); b=0; SL u,v,y,mu; C=do_dai_SL(x)+3; memcpy(MODULO,x,2*C); memcpy(mu,x,2*C); ok=1; while ((ok)&&(b<k)) { random_SL(u); memcpy(v,u,2*C); luy_thua_SL(v,mu); if (bang_nhau_SL(u,v)) b++; else ok=0; } } else b=k; if (b==k) { printf(" la so nguyen to "); ok=1; } else { printf(" la hop so "); ok=0; } textbackground(0);textcolor(15);clreol(); printf("\n"); return ok; } void phan_tich_WORD(SL x) { SL thuong; WORD a,ok; FILE *f; long i=0; f=fopen("co_so_w.ngt","rb"); while ((i1))) { i++; fread(&a,2,1,f); ok=!chia_WORD(x,a,thuong); while (ok) { char st[5]; itoa(a,st,10); short hd=wherex(); if ((80-hd)<strlen(st)) printf("\n "); printf("%u",a); memcpy(x,thuong,2*C); if (do_dai_SL(x)||(x[0]>1)) printf("*"); ok=!chia_WORD(x,a,thuong); } } fclose(f); if (do_dai_SL(x)==1) { hien_10(x); memset(x,0,2*C); x[0]=1; } } WORD NT_512[97]={ 2,3,5,7,11,13,17,19,23,29, 31,37,41,43,47,53,59,61,67,71, 73,79,83,89,97,101,103,107,109,113, 127,131,137,139,149,151,157,163,167,173, 179,181,191,193,197,199, //46 211,223,227,229,233,239,241,251,257,263, 269,271,277,281,283,293, //62 307,311,313,317,331,337,347,349,353,359, 367,373,379,383,389,397, //78 401,409,419,421,431,433,439,443,449,457, 461,463,467,479,487,491,499,503,509 }; main (void) { C=C_max; textbackground(0);textcolor(15); clrscr(); SL Y,Z,KIEM_TRA,UOC; short i; printf("\n Nhap so mu: "); scanf("%d",&i); { printf(" M_%u=",i); C=C_max; tao_so_Marsene_SL(i); textbackground(4);textcolor(14);clreol(); hien_10(X); textbackground(0);textcolor(15);clreol(); printf("\n"); textbackground(7);textcolor(1);clreol(); printf(" Co cac uoc nho la: "); textbackground(0);textcolor(15);clreol(); phan_tich_WORD(X); printf("\n"); memcpy(Z,X,2*C); char b=nguyen_to_SL(Z,100); if (do_dai_SL(Z)) { while (!b) { memcpy(KIEM_TRA,Z,2*C); b=pollard_1(KIEM_TRA,UOC); if (!b) { printf("\n"); textbackground(7);textcolor(1);clreol(); printf(" Uoc tim duoc la: "); textbackground(0);textcolor(15);clreol(); hien_10(UOC); printf("\n"); chia_SL(KIEM_TRA,UOC,Z,Y); b=nguyen_to_SL(Z,100); if (b) { textbackground(7);textcolor(1);clreol(); printf(" Uoc cuoi cung la: "); textbackground(0);textcolor(15);clreol(); hien_10(Z); printf("\n"); printf("\n "); textbackground(10);textcolor(15);clreol(); printf(" Phan tich hoan toan "); textbackground(0);textcolor(15);clreol(); } } else { printf("\n"); textbackground(7);textcolor(1);clreol(); printf(" Uoc hop so cuoi cung la:"); textbackground(0);textcolor(15);clreol(); hien_10(Z); printf("\n"); printf("\n "); textbackground(10);textcolor(15);clreol(); printf(" Khong phan tich hoan toan "); textbackground(0);textcolor(15);clreol(); } } } else printf(" Phan tich hoan toan\n"); } getch(); return 1; } Tài liệu dẫn và tham khảo [ Allency- R.B.J.T.Allency and E.J.Redfern, Redfern] Introduction to number Theory with Computing, Hordder & Shoughton, 1989. [ CCNT] C.Promerance (edit), Cryptologhy and Computationnal Number Theory, Proc. Symp. Appl. Math, 42, 1990. [Dixon] John D. Dixon, Asymptotically Fast Factorization of Integer, Math. Comp. 36 (1981) pp.255-260. [Kranakis] E. Kranakis, Primality and Cryptography, John Wiley and Son, 1986. [Huber] Klaus Huber, Some Consideration concerning the Selection of RSA Moduli, [Lehman] R.Sherman Lehman, Factoring Large Integer, Math. Comp. 28 (1974) pp. 637-646. [Lehman- D.H. Lehmer and R. E . Powers, Powers] On Factoring Large Numbers, Bull. Am. Math. Soc. 37 (1931). [Maurer] Ueli M. Maurer, Fast Generation of Prime Number and Secure Public-Key Cryptographic Parameters, J. Cryptologhy (1995) 8: 123-155. [Pollard] J. M. Pollard, Theorems on Factorization and Primality Testing, Proc. Cambr. Philos. Soc. 76 (1974) pp. 521-528. [Pollard] J .M .Pollard, A Monte Carlo Method for Factorization, Nordisk Tidskrift for Infomationsbehandling (BIT) 15 (1975) [Pomerance] Carl Pomerance, Analisis and Comparison of some Integer Fac toring Algotithms, Printed in H. W. Lenstra, Jr, and R, Tijdeman, Computational Methods in Number Theory, part I, Mathematisch Centrum Tract 154, Amsterdam 1982. pp. 89-139. [Riesel] Hans Riesel, Prime Nuber and Computer Methods for Factorization, Progress in Mathematics, 57, 1985. [Salomaa] A. Saloman, Public- Key Cryptography, EATCS, 1990. [Schoof] R. J. Schoof, Quadratic Fields and Factorization, Printed in H. W. Lenstra, Jr, and R. Tijdeman, Computational Methods in Number Theory, parth II, Mathematisch Centrum, Amsterdam 1982. pp. 235-286. [Shanks] Dainel Shanks. Class Number, A Theory of Factorizations, and Genera, Amer. Math. Soc. Proc. Symposia in Pure Math. 20 (1971). [Stinson] Douglas Robert Stinson, Cryptography: Theory and Practice, 1995 by CRC Press. Inc. [Williams] H. C. Williams, A p+1 Methods of Factoring, Math. Comp. 39 (1982) pp. 225- 234. [Lều Tân] Lều Đức Tân, Một số thuật toán kiểm tra nhanh tính nguyên tố đối với một số lớp số, Luận án phó tiến sĩ, Hà nội 1993. [Lều Tân] Nghiên cứu các modulo được dùng trong mật mã, Hà nội, năm1997 Mục lục Lời nói đầu 1 Chương I : Đặt vấn đề và ý nghĩa bài toán phân tích số nguyên 3 Chương II : Số Mersenne và việc phân tích 5 2.1. Số Mersenne 5 2.2. Phép thử nguyên tố cho các số Mersenne 6 Chương III : Một số thuật toán và phương pháp phân tích số nguyên 10 3.1. Thuật toán sàng Eratosthenes10 3.2. Thuật toán sàng đồng dư 10 3.3. Thuật toán sàng bậc hai 11 3.4. Thuật toán Dixon và sàng bậc hai 14 3.5. Phương pháp p-1: Thuật toán Pollard thứ nhất 16 3.6. Phương pháp p : Thuật toán Pollard thứ hai 19 3.7. Phương pháp p ± 1 : Thuật toán Williams 20 3.8. Phương pháp p của Pollard 22 3.9. Mô tả đại số phương pháp p Pollard 26 3.10. Chương trình mô tả phương pháp p Pollard 27 Chương VI : Xây dựng phần mềm phân tích các số dạng 2n - 1 30 4.1. Sơ đồ xuất phát 30 4.2. Phân tích hệ thống ………………………………3 4.3. Cài đặt chương trình 41 4.4. Sơ đồ khối của các module thuộc chương trình 43 Phụ lục 1 : Kết quả phân tích các số dạng 2n – 1 ( nÊ 200 ) ……….45 Kết luận …………………………….53 Phụ lục 2 : Chương trình nguồn 54 Tài liệu dẫn và tham khảo ………………………….. 71