Phân tích một số ra các thừa số nguyên tố ?

[blackboys]

hien nay khoa n cua RSA voi do dai 1024 bit phai can 15 trieu PC cao cap chay trong ... 1 nam moi pha duoc. Vay voi khoa n cua RSA ta co so n+1 va n-1 thi phan tich nhu the nao? Thuat toan nao la kha thi nhat? rat mong cac bac tra loi giup em .(Tat nhien n+1 va n-1 la so chan)

[ConanKudo]

Bài toán phân tích một số n ra thừa số nguyên tố có thể chạy được với
n<=10^12.
Có một số bạn làm quá thừa khi phải mất công kiểm tra 1 số có phải là số nguyên tố không,vừa tốn bộ nhớ vừa tốn thời gian chạy mà chả giải quyết cái gì .Khi một số n mà phân tích ở dạng p^k.A với p nguyên tố và k là lớn nhất,thì chắc chắn rằng A sẽ không chia hết cho p nữa,điều đó có nghĩa là nếu A không chia hết cho p thì mọi bội số của p A cũng sẽ không chia hết => chả việc gì phải kiểm tra số nguyên tố cho mất thời gian

Ta có nhận xét chỉ có số 2 là số nguyên tố chẵn,đầu tiên ta phân tích n = 2^t.q

while not odd(n) do 
   begin
       inc(top);
       a[top]:=2;
       n:=n div 2; 
   end;

Sau đó mình sẽ dùng một biến i để tính tiếp

i:=3;
while (i<=trunc(sqrt(n))+1) do
  begin
       while (n mod i=0) do
             begin
                 inc(top);a[top]:=i;
                 n:=n div i; 
             end;
       i:=i+2;    
   end;
 if n>1 then
   begin
       inc(top); 
       a[top]:=n;
   end;

Sau vòng lặp nếu n>1 => chắc chắn n là số nguyên tố => add thẳng vào mảng a.
Mảng a chính là mảng kết quả.
Độ phức tạp trong TH xấu nhất là O(sqrt(n)).
Bạn nào vẫn còn phân vân việc có phải kiểm tra nguyên tố hay không thì cứ cóp code vào chạy thử rồi sẽ nhận ra tại sao lại vậy

[=========> Bổ sung bài viết <=========]

uses crt;
var n,i,j,dem,mu:longint;
begin
clrscr;
write('nhap n:');readln(n);
write(n,'=');
for i:=2 to n-1 do
begin
if (n mod i=0) then
begin
for j:=2 to i do
begin
if i mod j=0 then break;
end;
if j=i then
begin
dem:=0;mu:=1;
repeat
mu:=mu*i;
dem:=dem+1;
until n mod mu<>0;
write(i,'^',dem-1,'*');
end;
end;
end;
readln;
end.
BÀi giải đây!

Không những dài mà còn không chạy được với n cỡ 10^8 .Cái này mình ko nhầm độ phức tạp còn > O(N)

[vtnphong]

Bài toán phân tích một số n ra thừa số nguyên tố có thể chạy được với
n<=10^12.

n<=10^12 hình như là quá nhỏ so với thuật toán RSA thì phải?

[ConanKudo]

Thuật toán RSA bạn nói chắc là cái mã hóa,đương nhiên có thể thuật toán mình post ở đây ko so sánh đc với cái đó vì nó chỉ trong phạm vi thi học sinh giỏi,chưa ứng dụng nhiều được vào thực tế
Cái mình post ở đây là cái dễ cài đặt trong thời gian ngắn nhất,độ phức tạp thấp,phục vụ cho bạn nào muốn thi,vậy thôi !

[Mr.Bo_Aloha]

anh conankudo! cách của xBach tuy dài nhưng đơn giản dễ hiểu hơn cách của anh!! đừng trách em nhiều chuyện nhưng theo em nếu là em thì em cũng làm như xBách

[ConanKudo]

Ừ,ở mức độ THCS thì cài trâu cũng có thể đc điểm tối đa ( không yêu cầu cao) ,nhưng ở mức độ HSG THPT thì nó sẽ bắt em làm thuật toán tối ưu đấy.
Thuật toán O(N) chắc cũng có thể đc 100/100 với n thuộc phạm vi integer

[blackboys]

ai co the giup em phan tich so nay : PQ-1 va PQ+1 voi P, Q la hai so nguyen to bat ky

[=========> Bổ sung bài viết <=========]

Rat mong ca cbai co the giup em, THANKS

[=========> Bổ sung bài viết <=========]

nhung so PQ = n nay neu la so nho thi co the goi la phan tich duoc. doi voi so lon thi chua chac da phan tich duoc( PQ=n co the co thua so nguyen to lon). Nhan day em cung xin noi luon, thuc ra PQ = n chinh la khoa RSA voi do dai >= 1024 bit. Hien em co mot so y tuong dua moi tren khoa cua RSA de tao mot he thong bao mat khac. Rat mong cac bac giup suc.

[mr_invincible]

anh conankudo! cách của xBach tuy dài nhưng đơn giản dễ hiểu hơn cách của anh!! đừng trách em nhiều chuyện nhưng theo em nếu là em thì em cũng làm như xBách

Là một người đã giành nhiều thời gian học pascal tôi khuyên bạn là nên học theo cả cách tối ưu và cách không tối ưu. Khi đi thi tùy theo yêu cầu của bài toán (giới hạn lớn hay nhỏ) mà chọn cách phù hợp

[blackboys]

cac bac cho em hoi: co the phan tich so co do dai khoang 2^350 tai thoi diem hien tai khong?

[=========> Bổ sung bài viết <=========]

phan tich nhu vay la khong on voi cac so lon.

[blackboys]

cho em hoi co cach nao tinh nhanh tong : s= xich ma tu k=1 đen n cua k[n/k] voi [a] chi phan nguyen cua a.