Hướng dẫn cách giữ thông tin an toàn và bí mật phần 9 potx

http://www.ebook.edu.vn 89

* 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

≡ y

2

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 x

2

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 x

2

≡y

2

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:

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

9503435785

546

x

y

⎧ = ⎨

⎩ =