✨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ố: :n= p*q. Với p, q là các số nguyên tố.

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<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à 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, x₂ = 2, x₃ = 4, x₄ = 7, x₅ = 8, x₆ = 11, x₇ = 13, và x₈ = 14

Dễ thấy UCLN(x_i,15) =1 với I thuộc (1,8) Chọn x = x₂ = 2 Ta sẽ có: 22 mod 15 = 4 mod 15 =4. 42 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 thỏa mãn:

2^w mod 15 = 1

A = 2^w/2 - 1 = 3 và B = 2^w/2 + 1 = 5.

Dễ thấy w =4 thỏa 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à q = UCLN(B,15)= UCLN(5,15) =5. 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 thỏa 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^w mod n = 1 hay là (X^w - 1) mod n = 0.

hay có thể hiểu là n là ước của (X^w - 1)

n|(X^w - 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^w/2 - 1).(X^w/2 + 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^w/2 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 thỏa 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ã hóa 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.