Thuật_toán Miller_Thuật toán Miller là thuật_toán để phân_tích nhân tử một_số nửa nguyên_tố thành_tích của hai số_nguyên_tố Thuật_toán này là nền_tảng cơ_bản của thuật_toán Shor trong máy_tính lượng_tử Thuật_toán Miller được xây_dựng bởi Victor_S_Miller_Giải thuật Giả_sử ta có số Với một bài_toán cho biết số n rồi tìm 2 số p và q thường hay_là nhất là bạn sẽ chia n cho các số_từ 2 đến n từ đó bạn có_thể xác_định được hai số p và q Nhưng khi số n là một_số cực lớn thì việc này trở_nên khó_khăn rất nhiều và khi chạy trong một thời_gian quá dài Thay vào đó Miller đã lựa_chọn một_số nguyên x bất_kì thoả_mãn 1 x n và UCLN x n 1 Số_nguyên x đó ta gọi là seed hạt Tìm số_nguyên_dương w nhỏ nhất và thoả_mãn X mod n 1 Gọi w là order of the seed x bậc của hạt x Nếu chỉ ra rằng w là một_số lẻ tương_ứng với x khi đó sẽ thử lại với một_số x khác cho đến khi x là một_số chẵn Tiếp_theo tính M X Và với M là một_số nguyên Sau đó tính tích của A M 1 và B M 1 Nếu B mod n 0 tìm x thoả_mãn hai điều_kiện 1 w là số_chẵn 2 B mod n khác 0 Cuối_cùng để xác_định được ước_chung lớn nhất của A n và B và n Có p UCLN A n và q UCLN B n Ví_dụ Tìm tích của hai số_nguyên_tố p và q với n p q 15 Với các số x 1 x 2 x 4 x 7 x 8 x 11 x 13 và x 14 Dễ thấy UCLN x 15 1 với I thuộc 1 8 Chọn x x 2 Ta sẽ có 2 2 mod 15 4 mod 15 4 4 2 mod 15 8 mod 15 8 8 2 mod 15 16 mod 15 1 Do_đó ta thấy 2 4 mod 15 1 suy ra w 4 cũng là số_mũ nhỏ nhất thoả_mãn 2 mod 15 1 A 2 1 3 và B 2 1 5 Dễ thấy w 4 thoả_mãn 2 điều_kiện w là số_chẵn và B mod n khác 0 Và ta có p UCLN A 15 UCLN 3 15 3 và Do_đó 15 phân_tích ra thừa_số nguyên_tố là 3 và 5 Lưu_ý Thuật_toán Miller để phân_tích một_số nửa nguyên_tố ra thừa_số nguyên_tố không phải lúc_nào cũng luôn thành_công ngay với một lựa_chọn hạt_giống x Nếu hạt_giống x đã chọn không phù_hợp thì luôn có_thể tìm hạt_giống khác Trong ví_dụ nêu trên cơ hội tìm_kiếm được hạt_giống thoả_mãn là lớn hơn 85 Chứng_minh Giả_sử chúng_ta lựa_chọn hạt x và w là số_nguyên_dương nhỏ nhất tìm thấy với X mod n 1 hay_là X 1 mod n 0 hay có_thể hiểu là n là ước của X 1 n X 1 Từ đó chúng_ta sẽ xây dưng thuật_toán với w là số_chẵn chúng_ta sẽ viết thành n X 1 X 1 hay n A B n là ước của tích AB nhưng n không là ước của B Chúng_ta loại_bỏ trường_hợp này bằng cách yêu_cầu B mod n khác 0 với các hạt x Nếu chúng_ta giả_sử n là ước của A ta có X mod n 1 nhưng w 2 và w 2 w Đó chính là điểm mâu_thuẫn với w là số_nguyên nhỏ nhất thoả_mãn điều_kiện trên Do_đó n không phải là ước của A và B Vì n có_thể phân_tích thành hai nhân tử p và q một trong 2 số p q này phải là A số còn lại là B Phá mã RSA Các số nửa nguyên_tố trong mã_hoá RSA hiện_đại thường có 200 chữ_thập phân hay nhiều hơn_nữa Với những số nửa nguyên_tố lớn như_vậy thì thuật_toán Miller thường cần lượng thời_gian để phân_tích là lớn đến mức RSA vẫn an_toàn Tuy_nhiên thuật_toán Shor áp_dụng thuật_toán Miller trên máy_tính lượng_tử có_thể thực_hiện trong thời_gian ngắn hơn nhiều Liên_kết ngoài http mathworld wolfram com MillersAlgorithm html
Thuật_toán Miller