1748036
Thuật toán Miller
https://vi.wikipedia.org/wiki?curid=1748036
Title: 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ì thỏa mãn 1&lt;x&lt;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à thỏa mãn:
"X"w 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"w/2
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 thỏa 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 = 1, "x"2 = 2, "x"3 = 4, "x"4 = 7, "x"5 = 8, "x"6 = 11, "x"7 = 13, và "x"8 = 14
Dễ thấy UCLN("x"i,15) =1 với I thuộc (1,8)
Chọn x = "x"2 = 2
Ta sẽ có:
2*2 mod 15 = 4 mod 15 =4.
4*2 mod 15 = 8 mod 15 =8.