Giáo án an toàn bảo mật -9

* 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,...
Nội dung trích xuất từ tài liệu:
Giáo án an toàn bảo mật -9 * 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ạtkhá 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ínhphương Danien Shaks, phương pháp đặc biệt của Ơle, phương pháp khai triểnliên phân số của Morrison và Brillhart, phương pháp sàng bậc hai củaPomerance, Dixon… là cố tìm được x ≠ ± y mod n sao cho x2 ≡ y2 mod n, cònkỹ 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ạngmong muốn x2 ≡ y2 mod n mà ta hy vọng sẽ đưa tới việc phân tích n và suy ragcd(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: 83409341562 ≡ 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 ≡ 5462 (mod n) Suy ra ⎧ x = 9 503435785 ⎨ ⎩ y = 546http://www.ebook.edu.vn 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) - α α α x2 ≡ p1 1j p2 2 j ...pBBj (mod n) Có đồng dư thức: - j Với 1 ≤ j ≤ C, mỗi j, xét véc tơ: a j = (α1 j mod2,α2 j mod2,...,αBj mod2) ∈ (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, 1, 0, 0, 0, 1) Suy ra a1 + a2 + a3 = (0, 0, 0, 0, 0, 0) mod 2 Trong trường hợp này nếu C B, sự phụ thuộc tuyến tính này nhất địnhphải tồn tại và ta có thể dễ dàng tìm được bằng phương pháp loại trừ Gaux.Lý do giải thích tại sao lấy C > B + 1 là do không có gì đảm bảo để một đồngdư thức cho trước bất kỳ sẽ tạo được phân tích n. Người ta chỉ ra rằng khoảng50% thời gian thuật toán cho ra x ≡ ± y (mod n). Tuy nhiên nếu C > B + 1 thìhttp://www.ebook.edu.vn 90có thể nhận được một vài đồng dư thức như vậy. Hy vọng là ít nhất một trongcác đồng dư thức kết quả sẽ dẫn đến việc phân tích n. Vấn đề cần đặt ra là phải làm như thế nào để nhận được các số nguyên xjmà các giá trị xj2 mod n có thể phân tích hoàn toàn trên cơ sở B. Một sốphương pháp có thể thực hiện được điều đó. Biện pháp sàng bậc hai doPomerance đưa ra dùng các số nguyên dạng xj = j + ⎢ n ⎥ , j = 1, 2, … dùng để ⎣⎦xác định các xj phân tích được trên B. Nếu B là một số lớn thì thích hợp hơn cả là nên phân tích số nguyên xjtrên B. Khi B càng lớn thì càng phải gom nhiều đồng dư thức hơn trước khicó thể tìm ra một số quan hệ phụ thuộc và điều này dẫn đến thời gian thựchiện cỡ 0(e(1+0(1) ln n lnln n) ) ∞ Với 0(1) là một hàm tiến tới 0 khi n tiến tới Thuật toán sàng trường số là thuật toán cũng phân tích n bằng cách xâydựng một đồng dư thức x2 ≡ y2 mod n, song nó lại được thực hiện bằng cáchtính toán trên vành các số đại số. * Thời gian tính các thuật toán trên thực tế Thuật toán đường cong Elliptic hiệu quả hơn nếu các thừa số nguyên tốcủa n có kích thước khác nhau. Một số rất lớn đã được phân tích bằng thuật ntoán đường cong Elliptic là số Fermat (2 −1) ( được Brent thực hiện năm 21988). Thời gian tính của thuật toán này được tính là (1+0(1) 2ln p lnln p ) 0(e ) p là thừa số nguyên tố nhỏ nhất của n Trong trường hợp nếu hai ước của n chênh lệch nhau nhiều thì thuật toánđường cong Elliptic tỏ ra hơn hẳn thuật toán sàng bậc hai. Tuy nhiên nếu haiước của n xấp xỉ nhau thì thuật toán sàng bậc hai nói chung trội hơn thuậttoán đường cong Elliptic.http://www.ebook.edu.vn ...