Tài liệu Kỹ thuật lập trình - Chương 4: Phân tích số nguyên thành nhân tử

Phân tích nhân tử là một thuật ngữ toán học dùng để chỉ một cách viết một số nguyên, hay tổng quát là một vật thể toán học, thành một phép nhân của các số nguyên khác, hay tổng quát là các vật thể toán học khác. Các số nguyên, hay vật thể toán học, nằm trong phép nhân gọi là nhân tử. Cùng tham khảo tài liệu dưới đây để tìm hiểu kiến thức về phân tích số nguyên thành nhân tử.
Nội dung trích xuất từ tài liệu:
Tài liệu Kỹ thuật lập trình - Chương 4: Phân tích số nguyên thành nhân tử 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 [ ] Giá trị ban đầu ( x0 , y0 ) = ( n ,0) . Sự tăng số k diễn ra theo quy tắc sau. Nếu nhưrk = 0 , thì mục đích của chúng ta đạt được n = xk − y k = ( xk − y k )( xk + y k ) , và thuật toán 2 2dừng. Nếu như rk > 0 , thì ( xk +1 , y k +1 ) := ( xk , y k + 1) , Nếu như rk < 0 , thì ( xk +1 , y k +1 ) := ( xk + 1, y k ) ; sau đó rk +1 := xk +1 − yk +1 − n 2 2 Chúng ta có thể chứng minh rằng với số bước thực hiện có hạn thì thuật toán đ ưađến giá trị rk = 0 . 4.1.3 Phương pháp (p-1) Pollaid Thuật toán p-1 của Pollaid đưa ra năm 1974 là một thuật toán đơn giản áp dụng đốivới các số nguyên lớn. Thuật toán này dựa vào hai đối số: Số nguyên lẻ n cần phân tíchvà cận B. Thuật toán được miêu tả như sau: Đầu vào: n và B. Đầu ra: Các thừa số của n (nếu tìm thấy). Bước 1. Cho a=2 Bước 2. For j=2 to B do a = a j (mod n) Bước 3. Tính d=UCLN(a-1,n) Bước 4. Nếu 1 < d < n thì d là một thừa số của n Ngược lại Không tìm thấy thừa số của n. Chúng ta xem tính hợp lý của thuật toán. Giả sử p là một ước số nguyên tố của n. Giới hạn B >0 thỏa mãn điều kiện sau. Vớimọi số nguyên tố q | ( p − 1) thì ta có điều kiện: v q ( p −1) q ≤B. Từ đây dẫn đến (p-1)|B! Nếu như chúng ta chọn số tự nhiên n sao cho UCLN(a,n)=1thì theo định lý nhỏ Fermat: a B! ≡ 1(mod p ) , Mà (p-1)|B!, nên a ≡ 1(mod p ) , nghĩa là p | (a − 1) , mà ta lại có p|n, cho nênp=UCLN(a-1, n). Trong thuật toán có (B-1) lũy thừa theo modulo, mỗi lũy thừa cần nhiều nhất là2log2B phép nhân modulo, ở đây chúng ta có thể áp dụng thuật toán bình phương và nhânđể thực hiện hiểu quả phép lũy thừa. Việc tính ước chung lớn nhất có thể thực hiện trong thời gian O((log n) 3) bằng thuậttoán Euclide. Vì thế độ phức tạp của thuật toán là O(B log B(log n)2+(log n)3). Nếu nhưB là O((log n)i) với i là một số nguyên nào đó thì độ phức tạp của thuật toán là độ phứctạp thời gian đa thức. 4.1.4 Phương pháp ρ Pollaid Phương pháp này được đề cập khá nhiều trong các sách và báo, nên ở đây chúng tachỉ nói khá tóm tắt miêu tả thuật toán. Sơ đồ thuật toán Đầu vào: là số nguyên n, mà chúng ta cần phân tích nó ra thừa số. Bước 1. Chọn ánh xạ f : Zn → Zn . Thông thường f (x) là đa thức có bậc không lớn hơn hay bằng 2, ví dụ f ( x) = x 2 + 1 . Bước 2. Chọn ngẫu nhiên x0 ∈ Z n và tính phần tử theo đệ quy của dãy x0 , x1 , x 2 ,... theoquy tắc xi ≡ f ( xi −1 )(mod n) . Bước 3. Đối với một số j, k kiểm tra điều kiện 1 < UCLN ( x j − xk , n) < n Cho đến khi nào không tìm được ước của số n hoặc thời gian chưa kết thúc. Kết thúc thuật toán Chú ý: Sự lựa chọn j, k trong bước 3 của thuật toán thông thường thực hiện mộttrong các cách sau 1. Đối với từng j chọn tất cả các số k, k h +1 3. Nếu như j trong giới hạn 2 ≤ j < 2 , h ∈ N , thì cho k = 2 h − 1 h Đây là phương pháp khá đơn giản. Nếu như chu kỳ của dãy xi (mod n) có thể bậc là n, thì chu kỳ của dãy xi (mod p ) đối với ước nguyên tố p của số n không vượt quá p. Điều này có nghĩa là x j , xk có thể khác nhau theo modulo n, nhưng trùng nhau theo modulo p, có nghĩa là p | UCLN ( x j − xk , n) . Phương pháp này cần O(n1 / 4 ) lệnh số học. Nó rất thông dụng và thường được sửdụng để tách ước nguyên tố không lớn của số n. 4.1.5 Phương pháp Serman-Leman Thuật toán này cần O(n1 / 3 ) lệnh số học Thuật toán Đầu vào: Cho n là số lẻ, n>8. Đầu ra: Là các thừa số của n. Bước 1. Đối với a = 2,3,..., [ n1 / 3 ] kiểm tra điều kiện a | n . Nếu như trên bước nàychúng ta không phân tích được n ra thừa số, thì chuyển đến bước 2. Bước 2. Nếu như trong bước 1 ước không tìm thấy và n là hợp số, thì n=pq, ở đâyp,q là số nguyên tố và n1 / 3 < p ≤ q < n 2 / 3 [ ...