Đồ án Phân tích số nguyên ra thừa số nguyên tố

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