Giáo trình Đại số hiện đại - Chương 4: Phân tích số nguyên thành nhân tử

4.1 Nhân tử hóa với độ phức tạp là hàm mũ

4.1.1 Mở đầu

Trong mục này chúng ta xem xét các thuật toán phân tích số tự nhiên n ra thừa số, mà nó thực hiện O(n^c ) lệnh số học, c là hằng số, 0<><1; hoặc="" thực="" hiện="" o(n^(c_1="" )="" log^(c_2="">⁡n) lệnh số học với một số giá trị c_1,c_2. Chúng ta sẽ giới hạn bằng cách tìm kiếm sự phân tích số ra 2 thừa số: n=ab,1<>⁡n) lệnh số học, bởi vì n bao gồm tích của không lớn hơn log_2⁡n số nguyên tố.

Nhưng trước khi tiến hành phân tích thành nhân tử số nguyên, chúng ta phải chắc chắn rằng số đã cho là hợp số. Để tin tưởng điều này, tốt nhất chúng ta dùng một trong các phương pháp kiểm tra tính nguyên tố của số bằng một số phương pháp đã trình bày trong chương về số nguyên tố, nhưng thông thường ta chọn phương pháp xác suất, ví dụ thuật toán Miller-Rabin.

4.1.2 Phương pháp Fermat

Phương pháp nhân tử hóa chúng ta đã tìm hiểu trong phần phương pháp thử chia, và cách này tốn O(n^(1/2) ) lệnh số học. Bây giờ chúng đi tìm hiểu thuật toán Fermat. Thuật toán này tính toán nhân tử lớn nhất a của n, mà nó không lớn hơn n^(1/2). Trong thuật toán này không sử dụng lệnh chia mà là lệnh cộng, trừ và nhân. Chú ý rằng nếu n=pq, với p,q là số nguyên tố, ví dụ nó có độ lớn như nhau thì thuật toán Fermat sẽ nhanh phân tích. Cái này được tính toán khi chọn modulo trong hệ mã RSA.