1748036
Thuật toán Miller
https://vi.wikipedia.org/wiki?curid=1748036
Title: Thuật toán Miller
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&gt;= 2 và w/2&lt;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.