* Phương pháp sàng Dyxon và sàng bậc hai Trong phần này giơi thiệu thuật toán phân tích hai số nguyên được coi là mạnh nhất theo nghĩa thời gian tính tốt nhất hiện nay. | Phương pháp sàng Dyxon và sàng bậc hai Trong phần này giơi thiệu thuật toán phân tích hai số nguyên được coi là mạnh nhất theo nghĩa thời gian tính tốt nhất hiện nay. ý tưởng của một loạt khá lớn các thuật toán phân tích số như phương pháp phân tích các dạng chính phương Danien Shaks phương pháp đặc biệt của Ơle phương pháp khai triển liên phân số của Morrison và Brillhart phương pháp sàng bậc hai của Pomerance Dixon. là cố tìm được x y mod n sao cho x2 y2 mod n còn kỹ thuật tìm cụ thể như thế nào thì chính là nội dung riêng của từng thuật toán Thuật toán Dixon được thực hiện như sau - Sử dụng một tập B chứa các số nguyên tố bé và gọi là cơ sở phân tích - Chọn một vài số nguyên x sao cho tất cả các thừa số nguyên tố của x2 mod n nằm trong cơ sở B - Lấy tích của một vài giá trị x sao cho mỗi nguyên tố trong cơ sở được sử dụng một số chẵn lần. Chính điều này dẫn đến một đồng dư thức dạng mong muốn x2 y2 mod n mà ta hy vọng sẽ đưa tới việc phân tích n và suy ra gcd x-y n là một ước của n. Ví dụ Giả sử chọn n 15770708441 B 2 3 5 7 11 13 Và chọn ba giá trị x là 8340934156 12044942944 2773700011 Xét ba đồng dư thức 834 0 9 34 1 562 3x7 mod n 120449429442 2x7x13 mod n 27737000112 2x3x13 mod n Lấy tích của ba đồng dư thức trên 8340934156 x 12044942944 x 2773700011 2 2 x 3 x 7 x 13 2 mod n Rút gọn biểu thức bên trong dấu ngoặc trong modulo đó ta có 95034357852 s 5462 mod n Suy ra x 9503435785 5 y 546 http 89 Tính gcd x-y n gcd 9503435785 - 546 15770708441 1157759 Ta nhận thấy 115759 là một thừa số của n Giả sử - B P1 _ pB là một cơ sở phân tích - C lớn hơn B một chút chẳng hạn C B 10 - Có đồng dư thức x pppĩ .pa mod n Với 1 j C mỗi j xét véc tơ ữj a J mod2 a2j mod2 . aBj mod2 e Z2 B Nếu có thể tìm được một tập con các aj sao cho tổng theo modulo 2 là vectơ 0 0 . 0 thì tích của các Xj tương ứng sẽ được sử dụng mỗi nhân tử trong B một số chẵn lần. Ví dụ Xét lại ví dụ trên n 15770708441 B 2 3. 5 11 13Ư Cho ba vectơ a1 a2 a3 A1 0 1 0 1 0 0 A2 1 0 0 1 0 1 A3 1
