- ơng cách thực hiện điều này là: trớc hết phải tạo ra các số ngẩu nhiên lớn, sau đó kiểm tra tính nguyên thuỷ của chúng bằng cách dùng thuật toán xác suất Monte- Carlo thời gian đa thức (chẳng hạn nh thuật toán Miller- Rabin hoặc là thuật toán Solovay- Strasen). - Cả hai thuật toán trên đều đợc trình bày trong phần này. - Chúng là các thuật toán nhanh (tức là một số nguyên n đợc kiểm tra trong thời đa thức theo log 2 n, là số các bít trong biểu diện nhị phân của n). - Bởi vậy, bằng cách thay đổi thuật toán nhiều lần, có thể giảm xác suất sai số dới một mức ngỡng cho phép (sau này sẽ thảo luận kỹ hơn một chút về vấn đề này).. - Bởi vậy, nếu p đợc chọn ngẫu nhiên thì xác suất p là một số nguyên tố sẽ vào khoảng 1/ln p. - Một thuật toán xác suất là một thuật toán bất kỳ có sử dụng các số ngẫu nhiên (ngợc lại, thuật toán không sử dụng các số ngẫu nhiên sẽ đợc gọi là một thuật toán tất định). - Các định nghĩa sau có liên quan tới các thuật toán xác suất cho các bài toán quyết định.. - Thuật toán Monte Carlo định hớng “có” là một thuật toán xác suất cho một bài toán quyết định, trong đó câu trả lời. - Thuật toán Monte Carlo định hớng “không“ cũng đợc định nghĩa theo cách tơng tự. - Chúng ta nói rằng, một thuật toán Monte Carlo định hớng “có” có xác suất sai bằng ε nếu với bất kỳ mổt trờng hợp nào mà câu trả lời là “có” thì thuật toán có câu trả lời sai “không” với xác suất không lớn hơn ε (xác suất này đợc tính trên mọi phép chon ngẫu nhiên, có thể thực hiên bởi thuật toán với một câu vào đã cho).. - Cần chú ý rằng một thuật toán quyết định chỉ có câu trả lời. - “có” hoặc “không” đặc biệt trong bài toán hợp lệ số là ta không yêu cầu thuật toán tính tích thừa số khi n là hợp lệ số.. - Trớc tiên ta sẽ mô tả thuật toán Soloway- Strasson. - Đây là một thuật toán Monte- Carlo định hớng “có” cho bài toán hợp số có. - Đây là một thuật toán Monte-Carlo định hớng “có” cho bài toán hợp số và xác xuất sai 1/2. - Bởi vậy, nếu thuật toán trả lời “có” thì n là hợp số. - ngợc lại nếu n là hợp số thì thuật toán trả lời “có” với xác xuất tối thiểu 1/2.. - Đặc trng của bài toán: cho p là một số nguyên tố lẻ và một số nguyên x sao cho 0 ≤ x ≤ p-1. - Mặc dù thuật toán Miller-Rabin (ta sẽ xét sau) nhanh hơn thuật toán Soloway-Strasson (S-S) nhng ta sẽ xét thuật toán S-S trớc vì nó dễ hiểu hơn về khái niệm, đồng thời lại liên quan tới một số vấn đề của lý thuyết số (mà ta sẽ còn dùng trong các chơng trình sau). - Ta sẽ xây dựng một số nền tảng sâu sắc hơn trong lý thuyết số trớc khi mô tả thuật toán.. - Giả sử p là một số nguyên tố lẻ và x là một số nguyên, 1. - Trớc hết, ta sẽ chứng minh một kết quả- tiêu chuẩn Euler –tạo nên thuật toán tất định theo thời gian đa thức cho bài toán về các thặng d bậc hai.. - Giả sử p là một số nguyên tố, khi đó x là một thặng d bậc hai theo modulo p khi và chỉ khi:. - Định lý 4.8 sẽ dẫn tới một thuật toán thời gian đa thức cho các thặng d bậc hai nhờ sử dụng kỹ thuật “bình phơng và nhân” cho phép lấy luỹ thừa theo modulo p. - Độ phức tạp của thuật toán khoảng O((log p) 3. - Giả sử p là số nguyên tố lẻ. - Với một số nguyên tố bất kỳ a. - Ta đã biết là a (p-1)/2 ≡ 1 (mod p) khi và chỉ khi a là một thặng d bậc hai theo modulo p. - Cuối cùng, nếu a là một thặng d không bậc hai theo modulo p thì a (p-1. - Bởi vậy, ta có kết quả cho phép xây dựng một thuật toán hữu hiệu để đánh giá các ký hiệu Legendre nh sau. - Giả sử p là một số nguyên tố. - Giả sử n là một số nguyên dơng lẻ và phân tích theo các luỹ thừa nguyên tố của n là p 1 e1. - Giả sử a ≥ 0 là một số nguyên. - 1 là một số lẻ. - Nếu n là một số nguyên tố thì. - Mặt khác nếu n là một hợp số thì. - Điều đó chứng tỏ rằng, việc kiểm tra tính nguyên tố theo thuật toán Soloway-Strasson đợc nêu ở hình 4.7 là thuật toán Monte-Carlo định hớng “có”với xác xuất sai tối đa là 1/2.. - Đến đây vẫn cha xác định rõ thuật toán ttrên có theo thời gian đa thức hay không.. - Thuật toán kiểm tra tính nguyên tố Solova- Strassen với số nguyên lẻ n.. - Chọn một số nguyên ngẫu nhiên a, 1 ≤ a ≤ n-1 2. - Trả lời “ n là số nguyên tố ” Nếu không. - Trả lời “ n là một hợp số. - Nếu n là một số nguyên tố lẻ và m 1 ≡ m 2 (mod n) thì:. - Nếu n là một số nguyên lẻ thì. - chỉ là rút gọn theo modulo và phân tích ra các luỹ thừa của thuật toán đợc biểu diễn dới dạng nhị phân thì việc phân tích ra các luỹ thừa của hai số chính là việc xác định số các số 0 tiếp sau. - Bởi vậy, độ phức tạp của thuật toán đợc xác. - Giả sử ta đã tạo đợc một số ngẫu nhiên n và đã kiểm tra tính nguyên tố của nó theo thuật toán Soloway- Strasen. - Nếu chạy thuật toán m lần thì câu trả lời “ n là một số nguyên tố” sẽ có mức độ tin cậy nh thế nào? Quả là liều lĩnh nếu coi răng, xác suất này là 1-2 -m . - b- Chỉ sự kiện “ thuật toán trả lời n là số nguyên tố m lần liên tiếp. - Phần này sẽ kết thúc bằng một thuật toán Monte- Carlo khác cho bài toán hợp số, đó là thuật toán Miller- Rabin (M-R) (đợc coi là một phép kiểm tra giả nguyên tố mạnh). - Thuật toán. - Đây lá một thuật toán với thời gian đa thức: độ phức tạp của nó cỡ O((log n) 3 ) tơng tự nh thuật toán S- S Thực ra trong thức tế thuật toán M-R thực hiện tốt hơn thuật toán S-S.. - Bây giờ chúng ta sẽ chỉ ra rằng thuật toán này không thể lời. - “n là một hợp số. - nếu n là số nguyên tố, tức nó là một thuật toán định hớng. - thuật toán Miller – Rabin về các hợp số là thuật toán monte- carlo định hớng “có. - Hình 4.9 Thuật toán kiểm tra tính nguyên tố Miller-rabin với số nguyên lẻ n. - Viết n-1=2 k m, trong đó m là một số lẻ. - Trả lời “ n là số nguyên tố “ và quit 5. - Trả lời “n là số nguyên tố “ và quit Else b=b 2 mod n. - Ta sẽ chứng minh bằng cách giả sử thuật toán trả lời “ n là hợp số” với số nguyên tố n nào đó và nhân đợc mâu thuẫt.. - Vì thuật toán trả lời “ nlà hợ số “ nên chắc chắn là a m ≡ 1(mod n). - Bây giờ xét dãy các giá trị b đợc kiểm tra trong bớc 2 của thuật toán .Vì b đợc bình phơng trong mỗi phép lặp của vòng For nên ta sẽ kiểm tra các giá trị a m , a 2m. - thuật toán trả lời “n là hợp số” nên suy ra:. - Vì n là một số nguyên tố nên hoặc n (x-1)(tức là x ≡ 1 modun) hoặc n (x+1) (tức là x ≡ -1 modun). - điều này là mâu thuẫn, bởi vậy trong trờng hợp này thuật toán phải có câu trả lời “n là số nguyên tố”.. - Còn một vấn đề cha cha đợc xem xét là xác xuất sai của thuật toán M-R. - Bây giờ chúng ta sẽ chứng minh một kết quả rất thú vị là một thuật toán bất kỳ để tính số mũ giải mã a đều có thể. - đợc dùng nh một chơng trình con (hay một điều kiện )trong thuật toán xác suất phân tích n .Bởi vậy việc tính a sẽ không dễ hơn việc phân tích n.Tuy nhiên, có một điều không ngoài quy luật là ta vẫn có thể phá hệ mật mà không cần tính a.. - Thuật toán mà ta sẽ mô tả là một thuật toán xác suất kiểu las vegas.Sau đây là định nghĩa của kiểu thuật toán này.. - Giả sử 0 ≤ ε ≤ 1 là một số thực.Thuật toán las vegas là một thuật toán xác suất cao cho với một trờng hợp bất kỳ của bài toán I, thuật toán có thể không cho kết quả với một xác suất ε nào đó (chẳng hạn thuật toán có thể kết thúc với thông báo “ không trả lời”).Tuy nhiên, nếu thuật toán cho lời giải thì. - Nhân xét:Thuật toán las vegas có thể không cho câu trả lời nhng một câu trả lời bất kỳ mà thuật toán cho là đều là câu tra lời đúng.Ngợc lại, thuật toán monte-carlo luôn luôn cho câu trả lời nhng câu trà lời này có thể là sai.. - Nếu ta có một thuật toán las vegas để giải một bài toán thì đơn giản ta chỉ chạy lặp đi lặp lại thuật toán này cho tới khi nó tìm ra một câu trả lời.Xác suất để thuật toán không trả. - Giả sử A là một thuật toán giả định tính số mũ giải mã a từ b. - Ta sẽ mô tả một thuật toán las vegas dùng A nh một chơng trình giả định (oracle) con.Thuật toán sẻ phân tích n với xác suất tối thiểu là 1/2.Bởi vậy nếu thuật toán chạy m lần thì n sẽ đợc phân tích với xác suất tối thiểu là 1-1/2 m. - Thuật toán đợc xây dựng trên cơ sở một số nguyên tố nhất định liên quan tới các căn bậc 2 của một theo modulo n, trong đó n=pq là tích của hai số nguyên tố lẻ phân biệt ta biết rằng phơng trình đồng d X 2 ≡ 1( mod p) có hai nghiệm theo modulo p là X. - p hoặc q(và tơng tự UCLN(X- 1,n)=p hoặc q).Tất nhiên có thể tính UCLN bằng thuật toán Euclide mà không cần phải biết phân tích nhân tử của n.Bởi vậy, hiểu biết về căn bậc hai không tầm thờng của 1 mod n sẽ làm cho việc phân tích n chỉ cần thực hiện trong thời gian đa thức.. - Trên hình 4.10 trình bày thuật toán (dùng thuật toán giả định A làm chơng trình con) để phân tích n bằng cách tìm một căn bậc hai không tầm thờng của 1 modulo n (A thực hiện tính số mũ giải mã a theo số mũ mã b ).Trớc tiên ta sẽ đa ra một ví dụ để minh hoạ cho việc áp dụng thuật toán này.. - Đây là một thừa số của n. - Bây giờ sẽ tiến hành phân tích thuật toán.Trớc tiên, nhân thấy rằng nếu ta may mắn chọn đợc w là bội của p hoặc q thì có thể ngay lập tức phân tích đợc n.Điều này đ- ợc biểu thị ở bớc 2. - Hình 4.10 Thuật toán phân tích thừa số (cho trớc số mũ giải mã a).. - Nếu ta có W 2r ≡ 1(mod n) .Bởi vậy, vòng lặp while sẽ kết thúc sau nhiều nhất là s bớc lặp .kết thúc vòng lặp, ta tìm đợc một giá trị v 0 sao cho v 0 2 ≡ 1 (mod n) nhng v 0 ≡ 1 (mod n) .Nếu v 0 ≡ -1 (mod ,n ) thì thuật toán không thành công. - Nhiệm vụ chính còn lại bây giờ là phải chứng minh rằng, thuật toán thành công với xác suất là ẵ .Có hai cách mà theo. - đó thuật toán có thể không thành công khi phân tích n. - đồng d thức này thì phép lựa chọn w này là “tồi” và thuật toán sẽ không thành công .Bởi vậy, ta sẽ chuyển sang tính số các nghiệm của mỗi đông d thức này.. - thế xác suất thành công của thuật toán tối thiểu là 1/2.. - Ta sẽ chứng minh rằng với y=e K (x) cho trớc một thuật toán bất kỳ tính parity(y) hoặc half(y) đều có thể đợc dùng nh một chơng trình con để xây dựng một thuật toán tính bản x. - Ta sẽ chỉ ra cách tính x=d K (y) theo một thuật toán giả. - Thuật toán đợc trình bày trên hình 4.11 .Trong các bớc 2.4 ta tính. - Dới đây là một ví dụ nhỏ. - Giả giử rằng (sử dụng thuật toán giả định đối với half(y. - ta nhận đợc các giá trị y i sau theo bớc 3 thuật toán:. - Hình 4.11.Giả mã bản mã RSA với một thuật toán giả định tính. - Chính xác hơn, giả sử w là một trong 4 căn bậc hai của một modulo n. - Đây là một phơng trình bậc hai theo giá trị x cha biết.. - Giả sử C là một thặng d bậc hai và p ≡ 3 (mod 4. - Một điều lý thú là với p ≡ 1 (mod 4), ngời ta cha biết đợc một thuật toán tất định theo thời gian đa thức nào để tính căn bậc hai của các thặng d bậc hai theo modulo p . - Tuy nhiên, vẫn có thuật toán Las Vegas với thời gian đa thức để tính nó. - Ta xẽ chứng minh rằng một thuật toán giải mã giả định A có thể đợc dùng nh một chơng trình con trong một thuật toán Las Vegas để phân tích modulo n với xác suất tối thiểu bằng 1/2.. - Thuật toán này đợc mô tả ở hình 4.14.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt