Thuật toán rho của Pollard – Wikipedia

Thuật toán rho của Pollard là một thuật toán cho hệ số nguyên. Nó được phát minh bởi John Pollard vào năm 1975. ^[1] Nó chỉ sử dụng một lượng không gian nhỏ và thời gian chạy dự kiến của nó tỷ lệ với căn bậc hai của kích thước của thừa số nguyên tố nhỏ nhất của số hỗn hợp được tính.

Ý tưởng cốt lõi [ chỉnh sửa ]

Giả sử chúng ta cần nhân tố một số

{displaystyle n=pq}

$n = pq$ trong đó

{ displaystyle p}

$p$ là một yếu tố không tầm thường. Một modulo đa thức

{ displaystyle n}

$n$ được gọi là

{ (x)}

$g (x)$ (ví dụ:

{ displaystyle g (x) = (x ^ {2} +1) { bmod {n}}}

${ displaystyle g (x) = (x ^ {2} +1) { bmod {n}}}$ ), được sử dụng để tạo một chuỗi giả ngẫu nhiên : Giá trị bắt đầu, giả sử 2, được chọn, và trình tự tiếp tục là

{ displaystyle x_ {1} = g (2 )}

${ displaystyle x_ {1} = g (2)}$

{ displaystyle x_ {2} = g (g (2))}

${ displaystyle x_ {2} = g (g (2))}$

{ displaystyle x_ {3} = g (g (g (2)))}

${ displaystyle x_ {3} = g (g (g (2)))}$ v.v … Trình tự này có liên quan đến một chuỗi khác

{ displaystyle {x_ {k} { bmod {p}} }}

${ displaystyle {x_ {k} { bmod {p}} }}$ . Kể từ

{ displaystyle p}

$p$ không được biết trước, trình tự này không thể được tính toán rõ ràng trong thuật toán. Tuy nhiên, trong đó nằm ở ý tưởng cốt lõi của thuật toán.

Bởi vì số lượng các giá trị có thể có cho các chuỗi này là hữu hạn, cả

{displaystyle {x_{n}}}

{ displaystyle n}

${ displaystyle {x_ {n} { Trình tự bmod {p}} }}$ cuối cùng sẽ lặp lại, mặc dù chúng ta không biết cái sau. Giả sử rằng các chuỗi hành xử giống như số ngẫu nhiên. Do nghịch lý sinh nhật số lượng

{displaystyle x_{k}}

$x_ {k}$ trước khi sự lặp lại xảy ra được dự kiến là [19659122] O ( N ) { displaystyle O ({ sqrt {N}})}

${ displaystyle O ({ sqrt {N}})} [19659012]trong đó <span class=$

{ displaystyle N}

$N$ là số lượng các giá trị có thể. Vì vậy, trình tự

{ displaystyle {x_ {k} { bmod {p}} }} [19659090] { displaystyle {x_ {k} { bmod {p}} }} “/> có thể sẽ lặp lại sớm hơn nhiều so với trình tự

{ displaystyle x_ {1} { bmod {p}}}

${ displaystyle x_ {2} { bmod {p}}}$ v.v. được thể hiện dưới dạng các nút trong một đồ thị có hướng.

Điều này được phát hiện bởi thuật toán tìm chu kỳ của Floyd: hai nút

{ displaystyle i}

$i$ và

{ displaystyle j}

$j$ (tức là

{ displaystyle x_ {i}}

$x_ {i}$ và

{ displaystyle x_ {j}}

$x_ {j}$ ) được giữ nguyên. Trong mỗi bước, một người di chuyển đến nút tiếp theo trong chuỗi và người khác di chuyển đến nút sau nút tiếp theo. Sau đó, nó được kiểm tra xem

{ displaystyle gcd (x_ {i} -x_ {j}, n) neq 1}

${ displaystyle gcd (x_ {i} - x_ {j}, n) neq 1}$ . Nếu nó không phải là 1, thì điều này có nghĩa là có sự lặp lại trong

{ displaystyle {x_ { k} { bmod {p}} }}

${ displaystyle {x_ {k} { bmod {p}} }}$ trình tự (ví dụ

{ displaystyle x_ {i} { bmod {p}} = x_ { j} { bmod {p}})}

${ displaystyle x_ {i} { bmod {p}} = x_ {j} { bmod {p}})}$ . Điều này hoạt động bởi vì nếu

{ displaystyle x_ {i} { bmod {p}}}

${ displaystyle x_ {i} { bmod {p}}}$ giống với

{ displaystyle x_ {j} { bmod {p}}} [19659231] { displaystyle x_ {j} { bmod {p}}} “/>sự khác biệt giữa

{ displaystyle x_ {i}}

Thuật toán [ chỉnh sửa ]

Thuật toán lấy làm đầu vào của nó $n$ số nguyên được xác định; và

{ displaystyle g (x)}

$g (x)$ một đa thức trong $x$ modulo $n$ . Trong thuật toán ban đầu,

{ displaystyle g (x) = (x ^ {2} -1) { bmod {n}}}

${ displaystyle g (x) = ( x ^ {2} -1) { bmod {n}}}$ nhưng ngày nay người ta thường sử dụng

{ displaystyle g (x) = (x ^ {2} +1) { bmod {n}}}

${ displaystyle g (x) = (x ^ {2} +1) { bmod {n}}}$ . Đầu ra là một yếu tố không tầm thường của $n$ hoặc thất bại. Nó thực hiện các bước sau: ^[2]

     x ← 2; y ← 2; d ← 1      trong khi  d = 1:         x ← g (x)         y ← g (g (y))         d ← gcd (| x - y |, n)      nếu  d = n:          thất bại trở lại       khác :          trở lại  d

Ở đây $x$ và $y$ tương ứng với

{ displaystyle x_ {i}}

$x_ {$ và

{ displaystyle x_ {j}}

$x_ {j}$ trong phần về ý tưởng cốt lõi. Lưu ý rằng thuật toán này có thể không tìm thấy một yếu tố không cần thiết ngay cả khi $n$ là hợp số. Trong trường hợp đó, phương pháp có thể được thử lại, sử dụng giá trị bắt đầu khác 2 hoặc khác

{ displaystyle g (x)} [19659026] g (x) “/>.

Hệ số hóa ví dụ [ chỉnh sửa ]

Đặt n = 8051 và g ( x x ² + 1) mod 8051.

i	x	y	$GCD (\| x - y \|, 8051)$
1 [1965932] 5 [1965932] Năm 1969932] 1
2	26	7474	1
3	677	871	97
4	7474	1481	1

97 là một yếu tố không tầm thường của 8051. Các giá trị bắt đầu không phải là x = y = 2 có thể cung cấp cho đồng sáng lập (83) thay vì 97. Một lần lặp thêm được hiển thị ở trên để làm rõ rằng y di chuyển nhanh gấp đôi x. Lưu ý rằng ngay cả sau khi lặp lại, GCD có thể trở về 1.

Các biến thể [ chỉnh sửa ]

Năm 1980, Richard Brent đã xuất bản một biến thể nhanh hơn của thuật toán rho. Ông đã sử dụng các ý tưởng cốt lõi tương tự như Pollard nhưng một phương pháp phát hiện chu kỳ khác, thay thế thuật toán tìm chu kỳ của Floyd bằng phương pháp tìm chu trình của Brent [3] ] Một cải tiến hơn nữa đã được thực hiện bởi Pollard và Brent. Họ đã quan sát thấy rằng nếu

{ displaystyle gcd (a, n)&gt; 1}

x	x _{đã sửa}	x mod 101	x _{đã sửa} mod 101	bước
2	2	2	2	0
5	2	5	2	1
26	2	26	2	2
677	26	71	26	3
598	26	93	26	4
3903	26	65	26	5
3418	26	85	26	6
156	3418	55	85	7
3531	3418	97	85	8
5168	3418	17	85	9
3724	3418	88	85	10
979 [1965932] 3418	69	85	11
9812	3418	15	85	12
5983	3418	24	85	13
9970	3418	72	85	14
236	9970	34	72	15
3682	9970	46	72	16
2016	9970	97	72	17
7087	9970	17	72	18
10289	9970	88	72	19
2594	9970	69	72	20
8499	9970	15	72	21
4973	9970	24	72	22
2799	9970	72	72	23

Wiki

Thuật toán rho của Pollard – Wikipedia

Ý tưởng cốt lõi [ chỉnh sửa ]

Thuật toán [ chỉnh sửa ]

Hệ số hóa ví dụ [ chỉnh sửa ]

Các biến thể [ chỉnh sửa ]

Ứng dụng [ chỉnh sửa ]

Ví dụ n = 10403 = 101 · 103 [ chỉnh sửa ]

Mẫu mã C [ chỉnh sửa ]

Mẫu mã Python [ chỉnh sửa ]

Kết quả [ chỉnh sửa ]

Độ phức tạp [ chỉnh sửa ]

Đọc thêm [ chỉnh sửa ]

19659258]]