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

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ính M=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=1208925819614