integer factorization

You are currently browsing articles tagged integer factorization.

Bài này là tiếp nối của bài trước về bài toán phân tích ra thừa số. Trong bài này, chúng ta sẽ thảo luận thuật toán Pollard-Rho được đề xuất bởi Pollard [1] và năm 1975. Độ phức tạp của thuật toán là $\tilde{O}(\sqrt[4]{N})$.

Chúng ta tạm quên bài toán phân tích ra thừa số để xét hai bài toán thú vị sau:

Nghịch lý ngày sinh nhật

Như ta đã biết theo nguyên lý Dirichlet (hay nguyên lí nhốt chim), trong 366 người thì sẽ có ít nhất hai người có cùng ngày sinh (không tính năm nhuận nhé). Không có gì đặc biệt trong phát biểu này. Tuy nhiên nhìn dưới quan điểm của xác suất thì mở rộng của phát biểu này có những tính chất rất thú vị.

Theo quan điểm của xác suất, phát biểu trên có thể được phát biểu lại như sau: trong 366 người, xác suất tìm được hai người có cúng ngày sinh là $1$. Giả sử xác xuất một người bất kì có ngày sinh vào một ngày nào đó trong năm là $1/365$. Ta mở rộng phát biểu đó ra bài toán sau:

Problem 1: Cần bao nhiêu người để xác suất tìm được hai người có cùng ngày sinh ít nhất là $1/2$.

 
Lời giải của bài toán trên vô cùng kinh ngạc: chỉ cần 23 người. Lời giải đó minh họa cho một nghịch lí mà người ta gọi là ngịch lí ngày sinh nhất (the birthday paradox).

Lời giải: Gọi $A_k$ là sự kiện trong $k$ người không có hai người nào có cùng ngày sinh. Cố định ngày sinh của người thứ nhất. Ta có:

  1. Xác suất để người thứ 2 không có cùng ngày sinh với người thứ $1$ là $1-\frac{1}{365}$.
  2. Xác suất để người thứ 3 không có cùng ngày sinh với người thứ $1,2$, biết rằng hai người $\{1,2\}$ có ngày sinh khác nhau, là $1-\frac{2}{365}$
  3. Xác suất để người thứ 4 không có cùng ngày sinh với người thứ $1,2,3$, biết rằng ba người $\{1,2,3\}$ có ngày sinh đôi một khác nhau, là $1-\frac{3}{365}$
  4. Cứ như vậy $\ldots$
  5. Xác suất để người thứ $k$ không có cùng ngày sinh với người thứ $1,2,\ldots,k-1$, biết rằng $k-1$ người $\{1,2,\ldots,k-1\}$ có ngày sinh đôi một khác nhau, là $1-\frac{k-1}{365}$

Do đó, ta có:

$\mathrm{Pr}[A_k] = (1-\frac{1}{365})(1-\frac{2}{365})\ldots (1-\frac{k-1}{365}) \qquad (1)$

Với $k = 23$, ta có (sử dụng máy tính để tính) $\mathrm{Pr}[A_k] = 0.49\ldots < 1/2$, do đó, xác suất để ít nhất hai người có cùng ngày sinh là $1 - \mathrm{Pr}[A_k] > 1/2$.


Mở rộng ra trường hợp trong thế giới $X$, một năm có $d$ ngày. Ta có định lý sau:

Theorem 1: Nếu một năm có $d$ ngày thì trong xấp xỉ $\sqrt{2\ln 2}\sqrt{d}\sim 1.2\sqrt{d}$ người, xác suất tìm được hai người có cùng ngày sinh ít nhất là $1/2$.

 
Chứng minh Bằng phân tích tương tự như trên, xác suất để không có hai người nào trong số $k$ người có cùng ngày sinh trong thế giới $X$ là:

$\mathrm{Pr}[A_k] = (1-\frac{1}{d})(1-\frac{2}{d})\ldots (1-\frac{k-1}{d}) \qquad (2)$

Giả sử $k$ nhỏ hơn nhiều so với $d$ (như $23$ với $365$ cũng là nhỏ hơn nhiều rồi), sử dụng xấp xỉ $1 - \frac{s}{d} \sim e^{-s/d}$, ta có:

$\mathrm{Pr}[A_k] \sim \Pi_{i=1}^{k-1} e^{-\frac{i}{d}} = e^{-\sum_{i=1}^{k-1}\frac{i}{d}} = e^{-\frac{k(k-1)}{2d}} \sim e^{-k^2/2d} \qquad(3)$

Thay $k = \sqrt{2\ln 2}\sqrt{d}$ thì ta có $\mathrm{Pr}[A_k] \sim 1/2$. Từ đó suy ra xác suất tìm được hai người có cùng ngày sinh ít nhất là $1 - \mathrm{Pr}[A_k] \sim 1/2$.


Để thử độ chính xác xấp xỉ trong Theorem 1, thay $d = 365$ ta tính được $k\sim 22.45$.

Vòng trong danh sách liên kết

Problem 2: Giả sử chúng ta có một danh sách liên kết $L$ bắt đầu từ phần tử $\mathrm{head}$. Với mỗi phần tử $a \in L$, ta có thể truy cập phần tử tiếp sau nó, gọi là $b$, qua con trỏ $\mathrm{next}$ như sau: $b = \mathrm{next}(a)$. Theo quy ước, phần tử cuối cùng của danh sách luôn trỏ đến $\mathrm{NULL}$. Tuy nhiên, vì một lí do nào đó, phần tử cuối cùng của danh sách lại trỏ đến một phần tử nào đó trong danh sách tạo nên một vòng. Bài toán đặt ra là với một danh sách $L$ cho trước, kiểm tra xem $L$ có vòng hay không.

 

Để giải bài toán này, chúng ta có thể tiến hành duyệt danh sách từ phần tử $\mathrm{head}$, lưu giữ thông tin về những phần tử đã duyệt qua. Mỗi lần duyệt đến phần tử mới, ta lại so sánh với các phần tử đã duyệt qua để phát hiện vòng. Thuật toán này sẽ mất thời gian $O(n^2)$ và bộ nhớ $O(n)$.
circle-disc

Tuy nhiên, thuật toán rùa và thỏ (tortois and hare, hay còn gọi thuật toán Floy) sẽ cho ta lời giải với thời gian $O(n)$ và bộ nhớ $O(1)$. Như cái tên của thuật toán, ta sẽ sử dụng hai con trỏ. Một con trỏ "chạy" với vận tốc $2$ và con kia "chạy" với vận tốc $1$. Nếu hai con trỏ gặp nhau thì danh sách có vòng. Giả mã như sau:

CycleDiscovery($L$):
    $\mathrm{ptr1} \leftarrow \mathrm{head}(L)$
    $\mathrm{ptr2} \leftarrow \mathrm{head}(L)$
    while $\mathrm{ptr2} \not= $ Null and $\mathrm{next}(\mathrm{ptr2}) \not= $ Null
        $\mathrm{ptr1} \leftarrow \mathrm{next}(\mathrm{ptr1})$
        $\mathrm{ptr2} \leftarrow \mathrm{next}(\mathrm{next}(\mathrm{ptr2}))$
       if $\mathrm{ptr1} = \mathrm{ptr2}$
            return Yes
    return No

 
Bây giờ chúng ta sẽ quay trở lại bài toán phân tích ra thừa số.

Thuật toán $\tilde{O}(\sqrt[4]{N})$

Thuật toán Pollard kết hợp ý tưởng từ hai bài toán tưỏng chừng như chả liên quan gì ở trên. Để việc phân tích và trình bày thuật toán đơn giản, giả sử $N = pq$ trong đó $p \leq q$ là hai số nguyên tố. Việc mở rộng phân tích ra trường hợp tổng quát coi như bài tập cho bạn đọc.

Giả sử ta chọn $k$ số ngẫu nhiên $x_1,x_2,\ldots, x_k$ trong khoảng ${2,3,\ldots, N-1}$. Xét dãy $\{x_1 \mod p, x_2\mod p, \ldots, x_k\mod p\}$. Nếu tồn tại hai số $x_i,x_j, i \not= j$ sao cho $x_i \mod p = x_j \mod p$, thì ta có $x_i \equiv x_j \mod p$. Từ đó suy ra $|x_i-x_j|$ chia hết cho $p$. Do đó ta có thể tính:

$p = \gcd(|x_i -x_j|, N) \qquad (4)$

Remark Tính ước chung lớn nhất có thể được thực hiện khá hiệu quả, sử dụng $O(\log^2 N)$ thao tác bít.

Một câu hỏi đặt ra là cần sinh bao nhiêu số ngẫu nhiên thì xác suất tìm được $x_i \equiv x_j \mod q$ là khá cao? Nếu phân tích kĩ bài toán này thì đây chính là bài toán trong nghịch lý ngày sinh. Thế giới $X$ ở đây chính là "thế giớ" đồng dư modulo $p$ và số ngày ở đây là $p$. Do đó, nếu chọn $k = 1.2\sqrt{p}$ thì xác suất tìm được hai số $x_i,x_j$ (ta gọi là cặp số tốt) như vậy ít nhất là $1/2$. Để tăng xác suất tìm được cặp số tốt, ta chỉ việc tăng $k$ lên. Cụ thể, nếu tăng $k$ lên $1.2c\sqrt{p}$ thì xác suất là $1 - 1/2^c$ (chứng minh coi như bài tập - chỉ cần mở rộng chứng minh ở trên). Ví dụ ta muốn xác suất là $99,9%$ thì ta sẽ tăng $k$ lên $12\sqrt{p}$ ($c = 10$).

Nhưng ở đây ta đang đi tìm $p$, làm sao ta xác định được $k$? Thực tế, ta không cần xác định $k$ mà ta cứ sinh ngẫu nhiên $x_1,x_2,\ldots$ (có thể vô hạn) cho đến khi ta tìm được $x_i,x_j$ thỏa mãn $\gcd(|x_i -x_j|, N) \not= 1 $. Phân tích trên chỉ ra rằng quá trình sinh đó sẽ dừng sau $k = 12\sqrt{p}$ bước với xác suất là 99.9%..

Gỉa sử ta đã sinh được $k$ số ngẫu nhiên và ta cũng đã biết rằng sẽ tồn tại một cặp số tốt trong số các số đã sinh đó. Để tìm cặp số tốt này, ta phải duyệt qua $O(k^2)$ cặp. Thời gian để duyệt đó là $O(k^2) = O(\sqrt{N})$ (nhắc lại $p = \sqrt[4]{N}$); cách này không tốt hơn thuật toán thử tất cả các ước số mà chúng ta đã biết. Wait! Bài toán phát hiện vòng trong danh sách liên kết có thể có liên quan gì đó ở đây? Sự thông minh của thuật toán Pollard chính là ở chỗ này.

Để giải quyết vấn để này, Pollard đề xuất sử dụng một hàm giả ngẫu nhiên để sinh dãy $x_1,x_2,\ldots, x_k$. Hàm đơn giản nhất thỏa mãn tính chất này là:

$f(x) = x^2 + 1 \mod N \qquad (5)$

Mình không đi sâu giải thích tại sao, Knuth [2] là nguồn tham khảo khá đầy đủ của vấn đề này. Như vậy, ta sẽ chỉ sinh một số $x_1$ hoàn toàn ngẫu nhiên và các phần tử còn lại sẽ sinh được sinh dựa trên $(5)$. Dãy số ngẫu nhiên ta thu được cuối cùng là:

$x_1, x_2 = f(x_1), x_3 = f(x_2), \ldots, x_{k} = f(x_{k-1}) \qquad (6)$

Do dãy $\{x_2,x_3,\ldots, x_k\}$ được sinh bởi hàm $f(x)$, nếu tồn tại $x_i \equiv x_j \mod p$ thì ta dễ dàng suy ra:

$x_{i+1} \equiv x_{j+1} \mod p,x_{i+2} \equiv x_{j+2} \mod p, \ldots \qquad (7)$

Nói cách khác, ta sẽ có một vòng (cycle) trong các dãy số bở $f(x)$ khi lấy $\mod p$ (giống như hình vẽ vòng của danh sách liên kết ở trên). Để tìm được giá trị $x_i,x_j, i\not=j$ thỏa mãn $\gcd(|x_i-x_j|,N) \not = 1$ (hay tương đương với $x_i \equiv x_j \mod p$), ta chỉ cần phát hiện ra vòng trong dãy này. Đó chính là vấn đề chúng ta đã giải quyết trong phần phát hiện vòng của danh sách liên kết.

Như vậy, ta đã có đầy đủ các công cụ cần thiết để thực thi thuật toán Pollard. Giả mã như sau:

PollardRhoFact($N$):
    if$ N == 1$
        return
    else if $N$ is too small         $(*)$
        FastNativeFact($N$)
    else if MillerRabinTesting$(N) = $ Prime
        output $N$
    else
        $p \leftarrow 0$
        while $p = 0$ or $p = N$
            $p \leftarrow $ FindFactor$(N)$
        PollardRhoFact($p$):
        PollardRhoFact($\frac{N}{p}$):

 

FindFactor($N$):
    $x \leftarrow$ a random number from $\{2,3,\ldots,N\}$
    $y \leftarrow x$
    $p \leftarrow 1$
    repeat
        $x \leftarrow f(x, N)$         $\ll f(x,N) = x^2+1 \mod N \gg$
        $y \leftarrow f(f(y,N),N)$
        $p \leftarrow$ GCD$(|x-y|,N)$         $(**)$
    until $p \not= 1$
    return $p$

 

GCD($a,b$):
    while $b \not = 0$
        $\mathrm{tmp} \leftarrow b$
        $b \leftarrow a \mod b$
        $a \leftarrow \mathrm{tmp}$
    return $a$

 
Code của giả mã bằng C. Code đầu đủ được đính ở cuối bài:

#define PRIME 1
#define COMPOSITE 0
#define MAXNUMFACT 64 // the maximum number of factors

typedef unsigned long long int LLU; // using unsigned long long type to avoid overflow

LLU Fa[MAXNUMFACT];// the array storing factors
int nfact = -1; // the number of factors

void pollard_rho_fact(LLU N){
if(N == (LLU)1){
return;
}else if(N &lt; (((LLU)1) &lt;&lt; 10)){ // if N is too small
fast_native_fact(N);
}else if(miller_rabin_testing(10, N) == PRIME){ // 10 is the accuracy of the test which corresponds to 1 - 1/2^(10)
Fa[++nfact] = N; // found a prime factor
} else {
LLU p = (LLU)0;
while(p == 0 || p == N){
p = find_factor(N);
}
pollard_rho_fact(p);
pollard_rho_fact(N/p);
}
}

LLU find_factor(LLU N){
LLU x = random64()% N;
LLU y = x;
LLU p = 1;
do{
x = next_prng(x,N);  // x = f(x,N)
y = next_prng(next_prng(y,N), N); // y = f(f(y,N),N)
if(x &gt; y){
p = gcd(x-y,N);
} else {
p = gcd(y-x,N);
}
}while(p == 1);
return p;
}
/*
* compute f(x,N) = (x^2 + 1) mod N
*/
LLU next_prng(LLU x, LLU N){
LLU xs = mod_mul(x,x,N);
return xs + (LLU)1;
}

Thủ tục MillerRabinTesting$(N)$ kiểm tra xem $N$ có phải là số nguyên tố hay không sử dụng thuật toán Miller-Rabin.

Chú ý do các phân tích trên chỉ đúng khi $N$ đủ lớn. Do đó, nếu $N$ quá nhỏ, ta có thể sử dụng thuật toán thử các ước số (chính là dòng $(*)$ trong giả mã trên).

Phân tích thuật toán
Gọi $p_1$ là ước số nguyên tố nhỏ nhất của $N$. Gọi $T(N)$ là thời gian để thuật toán tìm được $p_1$. Do $N$ có tối đa $\log N$ ước số (xem phần phân tích thuật toán của bài này), thuật toán sẽ mất $O(T(N)\log N)$ để phân tích $N$ thành các thừa số nguyên tố.

Theo phân tích ở trên, thủ tục FindFactor($N$) có thời gian kì vọng là $O(\sqrt(p_1))$ để tìm ra một thừa số $q_1$ của $N$ (có thể không nguyên tố do phép lấy ước chúng ở dòng $(**)$ của giả mã) mà $p_1$ là một thừa số nguyên tố của $q_1$. Sau khi đã tìm được $q$, thuật toán tiếp tục gọi đệ quy để tìm $p_1$. Nếu $q_1$ không quá nhỏ (nếu không ta có thể tìm được $p$ với thời gian hằng số), ta sẽ tiếp tục sử dụng FindFactor($q_1$), trong thời gian kì vọng $O(\sqrt(p_1))$, để tìm ra một thừa số của $q_2$ mà $p$ là một thừa số nguyên tố của $q_2$. Tiếp tục như vậy, ta sẽ phả mất thời gian là $T(N) = O(\sqrt(p_1) \log N)$, trong đó $\log N$ là số thừa số nguyên tố của $N$. Do $p_1 \leq \sqrt{N}$, ta có $T(N) = O(\sqrt[4]{N}\log N)$. Do đó, ta có:

Theorem 2: Thời gian phân tích một số $N$ thành các nhân tử là các số nguyên tố của thuật toán Pollard-Rho là $\tilde{O}(\sqrt[4]{N})$.

 

Code: pollard-rho-factorization.

Tham khảo

[1] Pollard, J. M. (1975). A Monte Carlo method for factorization, BIT Numerical Mathematics 15 (3): 331–334.
[3] Knuth, Donald E. The Art of Computer Programming, vol. 2. Seminumerical Algorithms (1981).
[3] Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Introduction to Algorithms (2nd ed.), Chapter 31. MIT Press and McGraw-Hill (2001). ISBN 0-262-03293-7

Tags: , , ,

« Older entries