Else

If n ( n0 Then

Else

If n ≤ n0 Then

Tuy nhiên ta thấy thuật toán β mới chỉ thay đổi được nhân tử hằng số chưa thay đổiđược bậc nhưng cũng hiệu quả khi n lớn. Do đó, nếu ta tiếp tục chia bài toán con nhỏ nữa tới n0≤ 4 d/c ta sẽ thu được một thuật toán hiệu quả hơn.

c := y[n-1]. .. y[n/2];d := y[n/2-1] . . .y[0]; U :=Karatsuba(a,c,n/2);

If n = 1 then Return x[0]*y[0] Else

Theo định nghĩa thì t(n) là một hàm không giảm.Khi n đủ lớn thuật toán của chúng ta rút gọn phép nhân hai số có kích thước tối đa n đó về ba phép nhân nhỏ hơn p = wy, q = xz và r = (w+x)(y+z) với kích thước tối đa tương ứng là |n/2|, |n/2| và 1 + |n/2|, thêm vào đó là những thao tác đơn giản chiếmthời gian là O(n). Do đó ở đây tồn tại hằng số dương c saocho: t(n) = t(|n/2|) +t(|n/2|) + t(1+|n/2|) + cn với mọi n đủ lớn. Điều này chính xác là phép đệ quy mà chúng ta đã nghiên cứu cho kết quả giờ đây đã trở nên quen thuộc là t(n)∈O( nlg 3). Do vậy luôn luôn có thể nhân các số n chữ số với thờigian O(nlg3). Phân tích tình huống tồi nhất của thuật toán này chỉ rarằng trên thực tế t(n) Ρ(nlg3),nhưng điều này không được quan tâm lắm vì còn có những thuật toán nhân nhanh hơn.

Phép nhân thứ ba bao gồm những số 3 chữ số, do vậy nó không thực sự là một nửa so với phép nhân nguyên thuỷ của các sốcó 4 chữ số. Tuy nhiên kích thước của w+x và

Để đơn giản, một số vấn đề quan trọng đến nay đã bị bỏ qua. Làm thế nào để chúng ta giải quyết được những số có độ dài lẻ?Mặc dù cả hai nửa của số nhân và số bị nhân đều có kích thước n/2, có thể xảy ratrường hợp tổng của chúng bị tràn và có kích thước vượt quá 1. Do đó sẽ không hoàn toàn chính xác khi nói rằng r = (w+x)(y+z) bao hàm phép nhân hai nửa. Điềunày ảnh hưởng tới việc phân tích thời gian chạy như thế nào? Làm thế nào để nhânhai số có kích thước khác nhau? Còn những phép tính số học nào khác với phépnhân mà ta có thể xử lý hiệu quả hơn so với dùng thuật toán cổ điển?

Một nhân tố quan trọng trong hiệu suất thực tế của cách tiếp cận phép nhân này và của bất kỳthuật toán Chia để trị nào là biết khi nào cần dừng việc phân chia các bài toánvà thay vào đó sử dụng thuật toán cổ điển. Mặc dù cách tiếp cận Chia để trị trởnên có ích khi bài toán cần giải đủ lớn, trên thực tế nó có thể chậm hơn so vớithuật toán cổ điển đối với những bài toán quá nhỏ. Do đó thuật toánChia để trị phải tránh việc thực hiện đệ quy khi kích thước của các bài toán con không phù hợp nữa. Chúng ta sẽ trở lại vấn đề này ở phần sau.

Vì lg3 = 1.585 nhỏ hơn 2, thuật toán này có thể nhân hai số nguyên lớn nhanh hơn rất nhiều so với thuật toán nhân cổ điểnvà n càng lớn thì sự cải thiện này càng đáng giá. Mộ cài đặt tốt có thể khôngsử dụng cơ số 10, mà sử dụng cơ số lớn nhất để với cơ số đó phần cứng cho phép nhân trực tiếp hai “chữ số” với nhau.

Vì h(n) rất nhỏ xo với Ρ(n2)và g(n) rất nhỏ xo với Ρ(n),số hạng g(n) là bỏ qua được so với h(n)khi n đủ lớn, có nghĩa là chúng ta tăng được tốc độ lên khoảng 25% so với thuậttoán cổ điển như đã mong đợi. Mặc dù sự cải thiện này là không thể xem thường được nhưng chúng ta vẫn không làm được thay đổi bậc của thời gian cần thiết:thuật toán mới vẫn cần thời gian tính bậc hai.

Để giúp chúng ta hiểu thấu đượcnhững gì mình đạt được, hãy giả thiết rằng có một cài đặt của thuật toán nhân cổđiển đòi hỏi thời gian h(n) = cn2để nhân hai số có n chữ số, với hằng số c phụ thuộc vàocài đặt đó. (ở đây đã có sự đơn giản hoá vì trên thực tế thì thời gian đòi hỏicòn có dạng phức tạp hơn, chẳng hạn như cn2+ bn + a). Tương tự, chog(n) là thời gian mà thuật toán Chia để trị cần để nhân haisố n chữ số,không tính thời gian cần thiết để thực hiện ba phép nhân hai nửa. Nói cách khác,g(n) là thời gian cần thiết cho các phép cộng, dịch chuyển và các phép tính phụthêm khác. Dễ dàng cài đặt các phép tính này sao cho g(n)∈Ρ(n).Hãy tạm thời bỏ qua điều gì sẽ xảy ra nếu n lẻ và nếu các số hạng không có cùngđộ dài.

Chắc chắn là số các phép cộng – coi phéptrừ như là phép cộng – có nhiều hơn so với thuật toán Chia để trị nguyên thuỷ ởphần trước. Vậy thì có đáng để thực hiện bốn phép cộng nhiều hơn để tiết kiệmmột phép nhân hay không? Câu trả lời là không nếu chúng ta đang nhân số nhỏ như những số trong ví dụ này. Tuy nhiên sẽ là đáng giá nếu các số cần được nhân vớinhau đủ lớn và chúng càng lớn thì lại càng đáng làm như vậy. Khi các số hạng đủlớn, thời gian cần cho các phép cộng và dịch chuyển trở thành bỏ qua được so vớithời gian cần cho chỉ một phép nhân. Như vậy là có lý do để kỳ vọng rằng rút gọn bốn phép nhân về còn ba sẽ giúp chúng ta cắt giảm được 25% thời gian tính toán đòi hỏi cho việc nhân các số lớn. Như chúng ta sẽ thấy, sự tiết kiệm của mình sẽtốt hơn một cách đáng kể.

Chúng ta minh hoạ quá trình này bằng việc nhân 981 với 1234. Trước tiên chúng ta điền thêm vào toán hạng ngắn hơn một số không vô nghĩa để làm cho haitoán hạng có cùng độ dài, vậy là 981 trở thành 0981. Sau đó tách từng toán hạngthành hai nửa: 0981 cho ra w = 09 và x = 81, còn 1234 thành y = 12 và z= 34.Lưu ý rằng 981 = 102w + x và 1234 = 102y + z. Do đó, tíchcần tìm có thể tính được là 981 x 1234 =(102w + x)( 102y + z) = 104wy + 102(wz + xy) +xz = 1080000 + 127800 + 2754 =1210554

Theo định lý thợ ta có độ phức tạp của thuật toán là T n = size 12{ { size 24{T} }rSub { size 8{n} } ={}} {} (On 2 ) .Như vậy thuật toán thu được cũng không gặt hái được bất kỳ cải thiện nào so với thuật toán nhân cổ điển mặc dù chúng ta đã khôn ngoan hơn. Để vượt được thuậttoán cổ điển và như vậy mới hoàn toàn thấy rõ được công dụng của phép Chia để trị, chúng ta phải tìm cách rút gọn phép nhân nguyên thuỷ không phải về bốn mà làbaphép nhân hai nửa.

If ( y < x[Middle] then return Bsearch(x,Start,Middle-1) Else

Else

If (y = x[Middle]) then return middle

If n đủ nhỏ then Insert(T) Else

Giả sử t(n) là thời gian cần thiết để giải thuật này sắp xếp một mảng n phần tử. Việc tách T thành U và V là tuyến tính. Ta cũng dễ thấy merge(U,V,T) cũng tuyến tính. Do vậy:

Else

If n đủ nhỏ then Insert(T)

Else

If U[i]<V[j] then

For k:=1 to n+m do

Như vậy quicksort có thể sắp xếp 1 mảng n phần tử khác nhau trong trường hợp trung bình là O( nlogn ). Câu hỏi đặt ra là liệu có thể sửa đổi quicksort để nó sắp xếp với thời gian O( nlogn ) trong trương hợp xấu nhất hay không. Câu trả lời là có thể!!!. Tuy nhiên nếu việc tìm phần tử ở giữa của T[i..j] là tuyến tính và lấy nó làm vật trung tâm (pivot) (Finding the median) thì quicksort cũng cần O( n 2) để sắp xếpnphần tử trong trường hợp xấu nhất (khi tất cả các phần tử của mảng cần sắp là bằng nhau). Giải thuật sau đây có thể khắc phục được vấn đề này:

hay c ≥ 2d + 4a/n 2

Ta chỉ ra c sao cho t( n ) ≤ cnlogn

Ta chứng minh t( n ) = cnlogn với mọin≥ 2. với c là hằng số.

Gọi t( n ) là thời gian cần thiết để sắp n phần tử trong trường hợp trung bình. a,n 0 là các hằng số giống như công thức 2.7.1

Với công thức như trên quả là khó phân tích độ phức tạp. Ta dự đoán nó tương tự mergesort và hi vọng nó là như vậy tức là vào cỡ O(nlogn). Thật vậy ta có định lý sau:

else begin

if n đủ nhỏ then Insert(T[i..j])

repeat k:=k+1; until (T[k] > p); repeat l:=l-1; until (T[l]≤p); Swap(T[i],T[l]);

while (k<l) do

repeat l:=l-1; until (T[l] < p);

repeat k:=k+1; until (T[k] > p) or (k≥j);

Việc thiết kế giải thuật ngăn cách mảng bằng vật trung tâm với thời gian tuyến tính không phải là sự thách đố (có thể làm được). Tuy nhiên điều đó là cần thiết để so sánh với các giải thuật sắp xếp khác như là heapsort. Vấn đề đặt ra là mảng con T[i..j] cần được ngăn bởi vật trung tâm p=T[i]. Một cách làm có thể chấp nhận được là:

Giải thuật này được phát minh bởi Hoare, nó thường được hiểu như là tên gọi của nó – sắp xếp nhanh, hơn nữa nó cũng dựa theo nguyên tắc chia để trị. Không giống như mergesort nó quan tâm đến việc giải các bài toán con hơn là sự kết hợp giữa các lời giải của chúng. Bước đầu tiên của giải thuật này là chọn 1 vật trung tâm (pivot) từ các phần tử của mảng cần sắp. Tiếp đến vật trung tâm sẽ ngăn mảng này ra 2 phần: các phần tử lớn hơn vật trung tâm thì được chuyển về bên phải nó, ngược lại thì chuyển về bên trái. Sau đó mỗi phần của mảng được sắp xếp độc lập bằng cách gọi đệ qui giải thuật này. Cuối cùng mảng sẽ được sắp xếp xong. Để cân bằng kích thước của 2 mảng này ta có thể sử dụng phần tử ở giữa (median) như là vật trung tâm . Đáng tiếc là việc tìm phần ở giữa cũng mất 1 thời gian đáng kể. Để giải quyêt điều đó đơn giNn là chúng ta sử dụng 1 phần tử tuỳ ý trong mảng cần sắp như là vậttrung tâm và hi vọng nó làtốt nhất có thể.

Cùng với phát minh của Strassen, có một số nhà nghiên cứu cố gắng tìm kiếm thuật toán để xác định được hằng số ω, khi đó độ phức tạp tính toán phép nhân hai ma trận kích thước n*n là . Để thực hiện được điều này, việc đầu tiên phải tiến hành là nhân hai ma trận kích thước 2*2 với 6 phép nhân cơ bản. Nhưng vào năm 1971 Hopcroft và Kerr đã chứng minh điều này là không thể vì phép nhân hai ma trận không có tính chất giao hoán. Việc tiếp theo phải thực hiện là tìm cách nào để nhân hai ma trận 3*3 với nhiều nhất chỉ 21 phép nhân cơ bản. Nếu thực hiện được việc này có thể sử dụng thuật toán này để suy ra thuật toán đệ quy nhân hai ma trận n*n với thời gian , nhanh hơn thuật toán của Strassen vì . Không may mắn là điều này không thể thực hiện. Trong suốt một thập kỷ trước khi Pan phát hiện ra cách để nhân hai ma trân kích thước 70*70 với 143640 phép nhân cơ bản – so sánh với 343000 phép nhân nếu sử dụng thuật toán cổ điển và quả thực là bé hơn một chút so với lg7. Phát hiện này được gọi là cuộc chiến tranh của số thập phân (decimal war). Nhiều thuật toán, mà trong đó hiệu suất tiệm cận cao, được tìm ra sau đó. Ví dụ như cuối năm 1979, phép nhân ma trận có thời gian tính toán là . Hãy tưởng tượng rằng, ngay sau đó tháng 1 năm 1980 thời gian tính của phép nhân ma trận là . Biểu thức tiệm cận thời gian tính toán tồi nhất của thuật toán nhân ma trận kích thước n*n được Coppersmith và Winograd phát minh ra năm 1986 là . Tại vì các hằng số liên quan bị Nn nên không một thuật toán nào được tìm ra sau thuật toán của Strassen được nghiên cứu và sử dụng.

Gọi t(n) là thời gian cần thiết để nhân hai ma trận kích thước n*n bằng cách sử dụng đệ quy hai phương trình 2.3.1 và 2.3.2. Giả sử rằng n là luỹ thừa bậc 2. Do thời gian để tình phép cộng, trừ ma trận là, do đót ( n ) = 7 t ( n /2) +dn 2, điều này là một ví dụ minh hoạ cho chúng ta trong việc phân tích tổng quát thuật toán chia để trị. áp dụng dụng định lý thợ ta có . Đối với các trường hợp ma trận vuông nhưng kích thước không phải là luỹ thừa bậc 2 thì giải quyết vấn đề bằng cách thêm các dòng và các cột sao cho kích thước ma trận mới gấp đôi kích thước ma trận cũ và gán giá trị cho các phần tử mới thêm là 0. Điều này không làm ảnh hưởng đến thời gian tính toán. Do lg7<2,81 nên có thể thực hiện phép nhân hai ma trận kích thước n*n trong thời gian với điều kiện các phép tính vô hướng là phép tính cơ bản.

Bây giờ nếu ta thay thế các phần tử trong A và B bằng các ma trận có kích thước n*n, thì để thực hiện phép nhân hai ma trận A và B ta phải thực hiện 7 phép nhân hai ma trận với kích thước n*n và cũng từng đấy phép cộng, trừ của hai ma trận n*n. Nếu ta làm việc với các ma trận lớn thì phép cộng sẽ nhanh hơn rất nhiều so với phép nhân, việc tiết kiệm 1 phép nhân sẽ lợi hơn nhiều so với việc thực hiện các phép cộng cơ bản.

Do đó ta thấy rằng, có thể nhân hai ma trận kích thước 2*2 bằng cách chỉ sử dụng 7 phép nhân vô hướng. Nhìn thoáng qua thấy rằng thuật toán này không có gì thú vị lắm, nó sử dụng một số lượng lớn các phép cộng và phép trừ, trong khi thuật toán cổ điển chỉ cần 4 phép cộng.

Ta có ma trận C là tích của hai ma trận A và B là:

Với mảng một chiều (kích thước n phần tử), ma trận C được tính trong thời gian O(n), giả sử rằng phép cộng vô hướng và phép nhân là các phép tính cơ bản (có thời gian tính là hằng số). Với mảng hai chiểu (kích thước n*n) thì thời gian để tính phép nhân ma trận AB là O( n 3)

Bài toán : Cho hai ma trận A, B với kích thước n*n, ta có ma trận C chứa kết quả của phép nhân hai ma trận A và B. Thuật toán nhân ma trận cổ điển như công thức dưới đây:

Giới thiệu về khoa học mật mã

Trong phần trước chúng ta đã thấy việc rút gọn số mũ trong số các phép nhân cần thiết để tínhankhông tiết kiệm được một cách đáng kể thời gian tính. Tuy nhiên, có những ứng dụng trong đó các phép nhân được coi là có chi phí ngang nhau. Đó là trường hợp khi chúng ta quan tâm đến số học đồng dư, tức là đến các phép toánanchia đồng dư cho một số nguyênz . Chúng ta đã biết rằngxmodzsẽ cho phần dư của phép chia nguyênxchoz . Ví dụ, 25 mod 7 = 4 vì 25 = 3 x 7 + 4. Nếuxvàylà các số nguyên nằm giữa 0 vàz- 1, và nếuzlà một số nguyên có kích thướcm , thì phép tính nhân đồng dưxymodzsẽ bao gồm một phép nhân thường của hai số nguyên có kích thước tối đam , mà kết quả là một số nguyên có kích thước tối đa 2 m , và tiếp theo là
một phép chia tích của hai số đó choz , cũng là một số nguyên có kích thước m , kết quả mà chúng ta quan tâm sẽ là phần dư của phép chia này. Như vậy thời gian cần cho mỗi phép nhân đồng dư phần nào không bị ảnh hưởng bởi giá trị của hai sốxvày .

dụng những phân tích trong phần trước với một số thay đổi cần thiết cho phép chúng ta kết luận rằng thuật toán trên chỉ cần một số lượng phép nhân đồng dư vào cỡ (log n) để tínhanmodz . Phân tích một cách chính xác hơn ta thấy số lượng phép nhân đồng dư bằng số Bít trong phép triển khai nhị phân củan , cộng với số Bít 1 trong số những Bít này; tức là vào khoảng 3/2 lgn cho các giá trị đặc trưng củan . Thuật toán tương ứngexposeqđòi hỏin– 1 phép nhân cho tất cả các giá trị củan . Để rõ hơn về điều này, hãy giả dụa ,nvàzlà những số có 200 chữ số và với các số có độ lớn như vậy có thể thực hiện phép nhân đồng dư trong một phần ngàn giây. Thuật toán expomod sẽ tính anmodz trong thời gian ít hơn một giây. Trong khi thuật toánexposeqcần thời giản vào khoảng 10179 lần tuổi của vũ trụ để tínhan .

Trong thực tế, liệu chúng ta có cần tính những lũy thừa đồng dư lớn như vậy hay không? Khoa học mật mã hiện đại, môn khoa học và nghệ thuật của những giao tiếp bí

mật trên những kênh không an toàn, phụ thuộc chủ yếu vào những phép tính này.

Chúng ta hãy xem xét trường hợp sau: Hai người là anh A và chị B trao đổi các thông

điệp với nhau. Giả sử anh A muốn gửi thông điệp cá nhânmcho chị B, nhưng kênh liên lạc lại không an toàn, hay nói một cách khác là dễ dàng bị nghe trộm. Để ngăn không cho những người khác đọc được thông điệp, anh A chuyển nó thành dạng mật mãc , sau đó gửi cho chị B. Việc chuyển đổi này là kết quả của một thuật toán chuyển mã. Đầu ra của nó không những chỉ phụ thuộc vào thông điệpmmà còn phụ thuộc vào

tham biếnk . Chúng ta gọi tham biến này làkhóa . Theo phương pháp kinh điển thì khóa chính là thông tin bí mật được thoả thuận giữa anh A và chị B trước khi họ trao đổi thông điệp với nhau. Nhờ có khoáknên khi nhận được thông điệp (đã mật mã hoá)c , chị B có thể tạo lại thông điệpm . Những hệ thống bí mật kiểu như vậy đều dựa trên nguyên tắc là dù kẻ nghe trộm lấy được thông điệpc , nhưng không biết khóa k thì cũng không thể đọc được nội dung thông điệpm .

Phương pháp mật mã hoá này được sử dụng với những thành công nhất định trong lịch sử phát triển của nó. Việc đòi hỏi các bên tham gia phải thỏa thuận những thông tin bí mật trước khi tham gia truyền thông có thể chấp nhận được trong giới ngoại giao và quân sự, nhưng khó có thể chấp nhận đối với những người dân bình thường. Trong thời đại siêu tốc điện tử, người ta có nhu cầu truyền thông riêng tư với nhau mà không cần có sự sắp đặt từ trước. Liệu anh A và chị B có thể trao đổi thông tin với nhau một cách bí mật với sự có mặt của những người khác mà không cần thỏa thuận từ trước những quy ước bí mật với nhau? Thế hệ mật mã hóa với khóa công khai đã được khai sinh với ý tưởng của Diffie, Hellman và Merkle về sự khả thi vấn đề trên trong những năm giữa thập kỷ 70 thế kỷ 20. Tiếp theo đây chúng tôi sẽ trình bày một giải pháp độc đáo được Rivest, Shamir và Adleman đưa ra ít năm sau. Giải pháp nàyn ngày nay được biết dưới cái tên hệ thống mật mã RSA, viết tắt từ tên của những người đã phát minh ra nó.

Xét hai số nguyên tố có 1 trăm chữ sốpvàqđược chọn một cách ngẫu nhiên bởi chị B. Gọizlà tích củapvàq . Chị B có thể tínhzmột cách hiệu quả từpvàq . Cho dù chúng ta sở hữu những máy tính hiện đại bậc nhất, cũng không có cách nào tính đượcpvàqtừzsử dụng những thuật toán đã biết, ngay cả khi chúng ta sử dụng hết cả thời gian của vũ trụ. Gọi ϕ là tích ( p- 1)( q- 1). Gọinlà một số nguyên nằm giữa 1 vàz– 1 được chọn một cách ngẫu nhiên bởi chị B sao cho n và ϕ nguyên tố cùng nhau. (Chị B không cần kiểm tra một cách cụ thể xemncó thỏa mãn điều kiện trên hay không vì chị sẽ nhanh chóng biết được điều đó). Trong số học chúng ta đã biết là chỉ có duy nhất một số nguyên s nằm giữa 1 và z– 1 thỏa mãn điều kiện nsmod = 1. Ngoài ra có thể dễ dàng tính rastừnvà ϕ (xem lời giải bài tập 7.31) đồng thời sự tồn

tại củascòn cho phép kiểm tra xemnvà ϕ có nguyên tố cùng nhau hay không. Nếuskhông tồn tại, chị B cần phải chọn một giá trị ngẫu nhiên khác chon ; xác xuất thành công của mỗi lần chọn đều như nhau. Mấu chốt trong giải pháp được trình bày ở đây là định lý:axmodz=atrong đó 0 ≤a<zvàxmod ϕ = 1.

Để có thể cho phép anh A hoặc ai đó truyền thông riêng tư với mình, chị B phổ biến cho tất cả sự lựa chọn của chị về giá trị củaxvàn , nhưng giữ bí mậts . Gọimlà một thông điệp mà anh A định gửi cho chị B. Sử dụng bộ mã chuNn chẳng hạn như ASCII, anh A chuyển thông điệp của mình thành một chuỗi Bít, được hiểu như là một sốa . Để đơn giản chúng ta giả thiết rằng 0 ≤a<z– 1; trong trường hợp a ≥z- 1 anh A có thể chia thông điệpmcủa mình thành từng đoạn có kích thước phù hợp. Tiếp đó anh A sử dụng thuật toánexpomodđể tínhc=anmodz , rồi gửi thông điệp đã được mã hóac cho chị B thông qua một kênh không an toàn. Nhờ có khóa s , Chị B giải mã và nhận được sốa , và qua đó là thông điệp mcủa anh A, việc này được thực hiện bởi một phép gọi hàmexpomod ( c ,s ,z ). Điều này thực hiện được vì:csmodz= ( anmodz ) s modz= ( an ) s mod z =ansmodz=a

Bây giờ chúng ta sẽ xét đến hành động của kẻ nghe trộm. Giả sử anh ta nghe được mọi trao đổi giữa anh A và chị B, như vậy anh ta sẽ biếtz ,nvàc . Mục đích của anh ta là xác định giá trị sốamà anh A gửi cho chị B, sốalà số duy nhất nằm giữa 0 vàz– 1 thỏa mãn điều kiệnc=anmodz . Để tính ra a chưa có một thuật toán hiệu quả nào được biết đến: phép tính lũy thừa đồng dư có thể thực hiện một cách hiệu quả với thuật toánexpomodnhưng điều ngược lại hình như không thể thực hiện được. Phương pháp tốt nhất được biết đến hiện nay là: phân tíchzra thành hai thừa số p và q , ( p- 1)( q- 1), tính s và tính a=csmod. Đó chính là cách chị B đã làm. Mỗi bước nêu trên đều khả thi, trừ bước đầu tiên: phân tích một số có 200 chữ số ra thừa số là một việc vượt quá khả năng cho phép của công nghệ hiện nay. Bởi vậy lợi thế của chị B trong việc giải mã chính là ở chỗ chị ta là người duy nhất biết các thừa số củaz , là những số cần thiết để tính ra ϕ vàs . Chị ta biết được không phải do có tài phân tíchzra thừa số mà do chị ta tính z từ các thừa số được chị ta chọn.

Hiện tại độ chắc chắn của sơ đồ mật mã hóa này vẫn chưa được xác định trên phương diện toán học: Không có chứng minh toán học nào khẳng định việc phân tích ra thừa số là không thể được và cũng không có chứng minh nào khẳng định rằng để phá mã cần phải phân tích ra thừa số. Xét trên phương diện khác thì chúng ta có thể có

những thuật toán có khả năng phân tích thừa số một cách hiệu quả, nhưng chúng lại đòi hỏi những máy tính lượng tử, mà để tạo ra những máy tính đó, thì lại nằm ngoài mtầm của công nghệ hiện tại. Hệ thống mật mã hóa mà chúng tôi mô tả ở trên vẫn được coi là một trong những phát minh sáng giá nhất trong lịch sử khoa học mật mã.

Phương pháp “chia để trị” – VOER

Giới thiệu về khoa học mật mã

mtoplist