Thuật toán Miller-Rabin kiểm tra tính nguyên tố -- Miller-Rabin Primality Testing

Trong phần này chúng ta sẽ tìm hiểu bài toán kiểm tra tính nguyên tố (primality testing) của một số nguyên. Đây là một bài toán có rất nhiều ứng dụng trong các lĩnh vực của tin học, đặc biệt trong bảo mật thông tin. Bài toán phát biểu như sau:

Problem 1: Cho một số nguyên $N$, kiểm tra xem $N$ có phải là một số nguyên tố hay không.

 
Bằng cách duyệt qua mỗi phần tử $i \in \{2,3,\ldots,\lfloor\sqrt{N} \rfloor\}$ và kiểm tra xem $i$ có phải là ước của $N$ hay không, ta có thể giải bài toán này trong thời gian $O(\sqrt{N})$ (có thể tăng tốc thêm một chút bằng cách chỉ kiểm tra $2$ và các số lẻ).

AlmostBruteForceTesting($N$):
    if $ N \mod 2 = 0$
        return $\mathrm{COMPOSITE}$
    else
        $i \leftarrow 3$
        while $i \leq \lfloor \sqrt{N} \rfloor$
            if $N \mod i = 0$
                return $\mathrm{COMPOSITE}$
            $i \leftarrow i+2$
    return $\mathrm{PRIME}$

 

Thuật toán AlmostBruteForceTesting không phải là thuật toán có thời gian đa thức (polynomial time) vì đầu vào có thể biểu diễn bởi $O(\log N)$ bit trong khi thời gian tính toán là $O(\sqrt{N})$. Do đó, thuật toán này không thể áp dụng cho các số $N$ rất lớn. Bài toán kiểm tra tính nguyên tố có thể được thực hiện trong thời gian đa thức hay không là một câu hỏi mở trong một khoảng thời gian rất dài và được giải quyết năm 2002 bởi Manindra Agrawal, Neeraj Kayal, và Nitin Saxena (thuật toán AKS). Tuy nhiên thuật toán AKS sử dụng $O(\log^6(N))$ thao tác bít và vì vậy không phù hợp với các ứng dụng thực tế. Thuật toán Miller-Rabin là thuật toán ngẫu nhiên kiểm tra tính nguyên tố sử dụng $O(\log^3 N)$ thao tác bít với xác suất lỗi thấp. Do đó, thuật toán này được áp dụng khả phổ biển trong các ứng dụng thực tế. Ban đầu, thuật toán này được đề xuất bở Miller [1] và là thuật toán tất định (deterministic). Sau đó, Rabin [2] sửa đổi thành thuật toán ngẫu nhiên. Về lịch sử của thuật toán xem thêm tại Wikipedia.

Do phân tích các thuật toán trong phần này dùng một số kiến thức về đồng dư và lý thuyết nhóm, mình sẽ trình bày các bổ đề và thuật toán trước. Chứng minh và phân tích mình sẽ đẩy về cuối bài viết.

Trước hết chúng ta xem xét thuật toán dựa trên định lý nhỏ Fermat.

Thuật toán Fermat

Định lý nhỏ Fermat phát biểu như sau:

Fermat's Little Theorem: Cho $p$ là một số nguyên tố, với mọi số nguyên $a$, ta có:

$a^{p-1} \equiv 1 \mod p$

 

Dựa trên Fermat's Little Theorem, ta có thuật toán kiểm tra số nguyên tố của một số nguyên:

FermatTesting($N$):
    $a \leftarrow $ a random number in $\{2,\ldots,n-1\}$
    if GCD$(a,N) \not= 1$
        return $\mathrm{COMPOSITE}$
    else if ModPower$(a,N-1,N) \not= 1$        [[$a^{N-1} \not\equiv 1 \mod N$]]
        return $\mathrm{COMPOSITE}$
    else
        return $\mathrm{PRIME}$

 

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

 

ModPower($a,b, p$):
    if $b = 1$
        return $a$
    else
        $x \leftarrow $ ModPower($a,\lfloor \frac{b}{2} \rfloor, p$)
        if $b$ is even
            return $(x*x) \mod p$
        else
            return $(x*x*a)\mod p$

 

Code của giả mã bằng C:

#define PRIME 1
#define COMPOSITE 0

int fermat_testing(int N){
int a = 2 + rand()%(N-3);
if(gcd(a,N) != 1){
return COMPOSITE;
} else {
if(mod_power(a,N-1, N) != 1){
return COMPOSITE;
} else {
return PRIME;
}
}

}

int gcd(int a, int b){
int tmp;
while  (b != 0){
tmp  = b;
b = a % b;
a = tmp;
}
return a;
}

int mod_power(int a, int b, int p){
if (b == 1){
return a %p;
} else {
int x = mod_power(a, b/2, p);
if((b&1) == 0){ // b is even
return (x*x)%p;
} else {
return (((x*x)%p)*a)%p;
}
}
}

Trong giả mã trên, hàm GCD($a,b$) tính ước số chung lớn nhất giữa hai số nguyên $a,b$ dựa trên thuật toán Euclid. Hàm này sử dụng $O(\log a + \log b)$ thao tác cơ bản (cộng, trừ, modulo). Các thao tác cơ bản này đều được thực hiện sử dụng số phép thao tác bít bằng số lương bít biểu diễn. Hàm ModPower($a,b, p$) tính $a^b \mod p$ sử dụng $O(\log b)$ phép nhân 2 số $\log p$ bít. Để đơn giản ta sẽ giả sử phép nhân 2 số $ \log p$ bít được thực hiện sử dụng $O(\log^2 p)$ thao tác bít ( về mặt lý thuyết, ta có thể thực hiện phép nhân sử dụng $o(\log^2 b)$ thao tác bít). Do đó, ta có:

Theorem 1: Thuật toán FermatTesting sử dụng $O(\log^3 N)$ thao tác bít để kiểm tra tính nguyên tố của số nguyên $N$.

 

Theo định lí Fermat, thuật toán FermatTesting luôn trả lại kết quả đúng nếu đầu vào $N$ là số nguyên tố. Hầu hết các thuật toán kiểm tra nguyên tố ngẫu nhiên thỏa mãn tính chất này. Tuy nhiên, nếu đầu vào $N$ là một hợp số thì thuật toán vẫn có thể trả lại PRIME.

Một thuật toán ngẫu nhiên kiểm tra tính nguyên tố gọi là có lỗi nếu với một đầu vào là hợp số, đầu ra của thuật toán là PRIME. Với thuật toán FermatTesting, giả sử $N$ là một hợp số, thuật toán sẽ trả lại PRIME nếu số $a$ lựa chọn ngẫu nhiên trong thuật toán thỏa mãn $a^{N-1} \equiv 1 \mod N$. Tồi tệ hơn nữa, tồn tại những hợp số $N$ (gọi là số Carmichael) thỏa mãn tính chất: với mọi số $a \in \{2,3,\ldots, N-1\}$, $a^{N-1} \equiv 1 \mod N$. Do đó, thuật toán FermatTesting chỉ trả lại COMPOSITE khi $\gcd(a,N) \not=1$. Tuy nhiên, các ước số của $N$ cũng là những số lớn thì xác suất chọn được số nguyên $a$ có $\gcd(a,N) \not=1$ rất nhỏ. Tóm lại, nếu $N$ là số Carmichael thì thuật Fermat có lỗi khá cao. May mắn là số lượng các số Carmichael không nhiều (so với $N$), do đó, thuật toán FermatTesting vẫn được sử dụng trong một số ứng dụng.

Ngược lại, nếu $N$ không phải là số Carmichael, thuật toán FermatTesting trả lại kết qủa đúng với xác xuất khá cao:

Theorem 2: Nếu $N$ không phải là số Carmichael, xác suất thuật toán FermatTesting trả về PRIME với đầu vào hợp số $N$ là:

$\mathrm{Pr}[error] \leq \frac{1}{2}$

 

Do đó, bằng cách thực hiện lặp lại thuật toán FermatTesting 10 lần, xác suất lỗi của thuật toán chỉ còn $\frac{1}{2^{10}} < \frac{1}{1000}$.

Thuật toán Miller-Rabin

Thuật toán Miller-Rabin có độ chnh xác khá cao ngay cả khi đầu vào là số Carmichael. Thuật toán được xây dựng dựa trên định lí sau:

Theorem 3: Giả sử $p$ là một số nguyên tố lẻ. Gọi $k,m$ là hai số thỏa mãn $p-1 = 2^km$ trong đó $m$ là một số lẻ. Gọi $1 \leq a < p $. Ta có:

$(1)$ $a^m \equiv 1 \mod p$ hoặc

$(2)$ Tồn tại $i, 1 \leq i \leq k,$ thỏa mãn $a^{2^im} \equiv 1 \mod N$ và $a^{2^{i-1}m} \equiv -1 \mod N$

 
Chứng minh: Gọi số nguyên $x$ là căn bậc 2 đồng dư của $a$ modulo $p$ nếu $a \equiv x^2 \mod p$. Nếu $p$ là một số nguyên tố, ta có thể dễ dàng chứng minh được $pm 1$ là căn bậc 2 đồng dư duy nhất của $1$ modulo $p$.

Gọi $b_i = a^{2^im}, 0 \leq i \leq k$, ta có:

$b_i = b_{i-1}^2 \qquad \& \qquad b_k \equiv 1 \mod p \qquad (3)$

Gọi $i_0$ là số nhỏ nhất sao cho $b_{i_0} \equiv 1 \mod q$. Số $i_0$ tồn tại vì $b_k \equiv 1 \mod p$. Theo phương trình $(3)$, ta có $b_{i_0}^2 \equiv 1 \mod q $ và do đó, $b_{i_0} \equiv -1 \mod q $. Từ đó ta suy ra Theorem 3.


Gọi $a$ là một bằng chứng (witness) cho biết $n$ là hợp số nếu cả $(1)$ và $(2)$ trong Theorem 3 đều không thỏa mãn. Với bằng chứng $a$ và số nguyên $N$, thủ tục Witness($a,N$) sẽ trả về COMPOSITE nếu $a$ là bằng chứng cho biết $N$ là hợp số và trả về PRIME nếu ngược lại. Giả mã của thuật toán Miller-Rabin kiểm tra tính nguyên tố như sau:

MillerRabinTesting($N$):
    $a \leftarrow $ a random number in $\{2,\ldots,n-1\}$
    if GCD$(a,N) \not= 1$
        return $\mathrm{COMPOSITE}$
    else if ModPower$(a,N-1,N) \not= 1$         [[$a^{N-1} \not\equiv 1 \mod N$]]
        return $\mathrm{COMPOSITE}$
    else
        return Witness$(a,N)$

 

Witness($a,N$):
    $(k,m) \leftarrow $ Decompose($N-1$)         [[write $N-1 = 2^km$]]
    $B[0] \leftarrow $ ModPower($a, m, N$)
    if $B[0] = 1$
        return $\mathrm{PRIME}$
    else
        $i \leftarrow 1$
        while $i \leq k$
            $B[i] \leftarrow (B[i-1]*B[i-1])\mod N$
            if $B[i] = 1$         [[$i$ is the smallest s.t $b_i \equiv 1 \mod N$]]
                if $B[i-1] = N-1$         [[$B[i-1] \equiv -1 \mod N$]]
                    return $\mathrm{PRIME}$
                else
                    return $\mathrm{COMPOSITE}$
    return $\mathrm{COMPOSITE}$

 

Decompose($p$):
    $i \leftarrow 0$
    while $p$ is even
        $i \leftarrow i+1$
        $p \leftarrow \frac{p}{2}$
    return $(i,p)$

 

Code của giả mã bằng C:

#define PRIME 1
#define COMPOSITE 0

int witness(int a, int N){
int k,m;
decompose(N-1,&amp;k,&amp;m);
int B[k+1];
B[0] = mod_power(a,m,N);
if(B[0] == 1){
return PRIME;
} else {
int i = 1;
while(i &lt;= k){
B[i] = (B[i-1]*B[i-1])%N;
if(B[i] == 1){
if(B[i-1] == N-1){
return PRIME;
} else {
return COMPOSITE;
}
}
i++;
}
}
return COMPOSITE;
}

void decompose(int p, int *k, int *m){
int i = 0;
while ((p&amp;1) == 0){ // p is even
i++;
p = p &gt;&gt; 1; // p = p /2
}
*k = i;
*m = p;
}

Trong giả mã trên, $B[i]$ chỉ phụ thuộc vào $B[i-1]$. Do đó, bạn có thể tiết kiệm bộ nhớ một chút bằng cách sử dụng hai biến $X,Y$ thay vì cả mảng $B[1,2,\ldots,k]$. Thủ tục Decompose thực hiện $O(k)$ thao tác bít để tách $N-1 = 2^km$. Thủ tục Witness sử dụng $k$ phép nhân hai số $\log N$ bít và $O(k)$ phép toán cơ bản. Do $k \leq \log (N-1) $, ta suy ra:

Theorem 4: Thuật toán MillerRabinTesting sử dụng $O(\log^3 N)$ thao tác bít để kiểm tra tính nguyên tố của số nguyên $N$.

 

Ví dụ: $N = 561 = 3*11*17$ là số Carmichael, hãy xem thuật toán Miller-Rabi thực hiện như thế nào. Trước hếtt tách $N-1 = 560 = 2^4*35$, do đó $k = 5, m = 35$. Giả sử $a = 8$, ta có:

$\begin{array}{lcl} B[0] = a^m \mod N & = & 461 \\ B[1] = 461^2 \mod N & =& 463\\ B[2] = 463^2 \mod N & = & 67\\B[3] = 67^2 \mod N &=& 1 \end{array}$

Do $B[3] = 1, B[2] \not= N-1$, thuật toán Miller-Rabin sẽ trả lại $\mathrm{COMPOSITE}$
Theo Theorem 3, thuật toán Miller-Rabin luôn trả lại $\mathrm{PRIME}$ nếu đầu vào $N$ là số nguyên tố. Cũng như thuật toán Fermat, thuật toán Miller-Rabin cũng có lỗi nếu đầu vào là hợp số. Tuy nhiên, ngay cả khi đầu vào $N$ là số Carmichael, thuật toán Miller-Rabin có lỗi khá nhỏ. Do đó thuật toán này thường được sử dụng trong thực tế để kiểm tra tính nguyên tố của một số nguyên.

Theorem 5: Xác suất thuật toán MillerRabinTesting trả về PRIME với đầu vào hợp số $N$ là:

$\mathrm{Pr}[error] \leq \frac{1}{2}$

 
Về mặt lý thuyết có thể chứng minh được xác suất lỗi của thuật toán Miller-Rabin trong Theorem 5 là $\mathrm{Pr}[error] \leq \frac{1}{4}$. Tuy nhiên chứng minh sẽ phức tạp hơn.

Phân tích và chứng minh

Chứng minh Fermat's Little Theorem: Xét $p-1$ số sau:

$a,2a,3a, \ldots, (p-1)a$

Giả sử tồn tại hai số $0 < y < x < p$ sao cho $xa \equiv ya \mod p$ $ \Rightarrow (x-y)a \equiv a \mod p$. Do $p$ là một số nguyên tố, ta suy ra $p | (x-y)$ hoặc $ p| a$. Cả hai trường hợp đều không thể xảy ra. Từ đó suy ra không có hai số nào trong $(p-1)$ số trên đồng dư. Do đó, số dư của dãy số trên khi lấy modulo $p$ là hoán vị của $\{1,2,\ldots,p-1\}$. Do đó:

$ \begin{array}{lcl} a\cdot 2a \cdot 3a \cdots (p-a)a & \equiv & 1\cdot 2 \cdots (p-1) \mod p\\ \Leftrightarrow (p-1)!a^{p-1} & \equiv & (p-1)! \mod p \end{array}$

Từ đó suy ra định lý Fermat.


Một nhóm (group) $(G,*)$ là một cấu trúc đại số gồm một tập hợp $G$ và một phép toán $(*)$ kết hợp hai phần tử của $G$ tạo ra một phần tử thứ 3 thỏa mãn 4 tiên đề sau:

  1. Tính bao đóng: nếu $a,b \in G$ thì $a*b \in G$
  2. Tính kết hợp: nếu $a,b,c \in G$ thì $(a*b)*c = a*(b*c)$
  3. Phần tử đơn vị: $G$ chứa một phần tử $e$ gọ là phần tử đơn vị thỏa mãn: với mọi $a \in G$, ta có $a*e = e*a = a$
  4. Phần tử nghịch đảo: Với mọi $a \in G$, tồn tại phần tử $a^{-1} \in G$ sao cho $a*a^{-1} = 1$

Ví dụ $(\mathbb{Z}, +)$ với $e = 0$ là một nhóm. Bạn có thể kiểm tra 4 tiên đề của phép $+$ thao tác trên tập hợp các số nguyên. Chú ý: $(\mathbb{Z},.)$ với $e = 1$ không phải là một nhóm vì $2 \in \mathbb{Z}$ có phần tử nghịch đảo là $\frac{1}{2} \not\in \mathbb{Z}$.

Một nhóm $(G,*)$ được gọi là hữu hạn nếu số lượng các phần tử của $(G,*)$, thường gọi là bậc của nhóm v kí hiệu là $|G|$, hữu hạn. Một nhóm $(S,*)$ là một nhóm con của $(G,*)$ nếu hai phép toán thao tác trên hai tập này là một và $S \subseteq G$. Định lý nổi tiếng Largrange cho biết mối quan hệ giữa bậc của một nhóm và bậc của nhóm con của nó:

Theorem 6: Gọi $(S,*)$ là một nhóm con của một nhóm một hữu hạn $(G,*)$, bậc của $G$ sẽ chia hết cho bậc của $S$.

$|S|$ divides $|G|$

 

Ví dụ: $(\mathbb{Z}, +)$ là nhóm con của chính nó. Ví dụ khác: $(2\mathbb{Z}, +)$ trong đó $2\mathbb{Z} = \{a | a \in \mathbb{Z}, a \mbox{ is even} \} $ là một nhóm con của $(\mathbb{Z}, +)$.

Gọi $\mathbb{Z}_n = \{a | 1 \leq a \leq n-1, \gcd(a,n) = 1\}$ là tập các số nguyên tố cùng nhau với $n$ và nhỏ hơn $n$. Phép nhân đồng dư $(*)$ định nghĩa trên trên $\mathbb{Z}_n$ như sau: với $a,b \in \mathbb{Z}_n$, $ c = (a\cdot b) \mod n$ là tích của $a,b$ lấy đồng dư modulo $n$. Ta sẽ chứng minh: $(\mathbb{Z}_n,*)$ là một nhóm với $e = 1$. Ta kiểm tra 4 tiên đề của nhóm: 3 tiên đề đầu không khó để kiểm tra và coi như bài tập cho bạn đọc. Với tiên đề cuối cùng, gọi $a$ là một phần tử của $\mathbb{Z}_n$. Do $\gcd(a,n) = 1$, theo thuật toán Euclid mở rộng, tồn tại hai số nguyên $x,y$ sao cho $ax + yn = 1$. Suy ra, $ax \equiv 1 \mod n$, do đó, $x\mod n$ là phần tử nghịch đảo của $a$.

Từ đoạn này về cuối, ta chỉ xét nhóm $(\mathbb{Z}_N, *)$ và các nhóm con của nó. Để đơn giản, ta sẽ bỏ toán tử trong kí hiệu của nhóm, i.e, sử dụng luôn kí hiệu tập hợp $\mathbb{Z}_N$ thay cho $(\mathbb{Z}_N, *)$.

Chứng minh Theorem 2: Nếu $\gcd(a,N) \not= 1$, thuật toán Fermat sẽ trả lại $\mathrm{COMPOSITE}$. Phép kiểm tra ước chung lớn nhất chỉ thực sự hiệu quả (xác xuất tìm được số $a$ như vậy $\geq 1/2$) khi $N$ là số chẵn. Do đó, hiệu quả của thuật toán Fermat nằm ở bước kiểm tra $a^{N-1} \mod N$. Số $a$ ngẫu nhiên sau bước kiểm tra ước chung lớn nhất với $N$ sẽ là một phần tử của nhóm $\mathbb{Z}_N$. Giả sử $N$ là một hợp số và không là số Carmichael. Thuật toán Fermat sẽ trả lại $\mathrm{PRIME}$ (có lỗi) nếu số $a$ chọn ngẫu nhiên thỏa mãn: $a^{N-1} \equiv 1 \mod N$. Gọi $S = \{a\in \mathbb{Z}_N | a^{N-1} \equiv 1 \mod N\}$. Nhận thấy $S$ (coi như bài tập cho bạn đọc) là một nhóm con của $\mathbb{Z}_N$ (với phép nhân đồng dư module $N$). Do $N$ không phải là số Carmichael, $(S,*)$ là một nhóm con đúng của $\mathbb{Z}_N$ ($S \not= \mathbb{Z}_N$). Theo định lý Lagrange, $|S|$ là một ước số của $|\mathbb{Z}_N|$, do đó, $|S| \leq \frac{|\mathbb{Z}_N|}{2}$. Từ đó suy ra xác xuất có lỗi của thuật toán Fermat là:

$\mathrm{Pr}[error] \leq \frac{|S|}{|\mathbb{Z}_N|} \leq \frac{1}{2}$


Chứng minh Theorem 5 Ta chỉ cần chứng minh Theorem 5 với trường hợp $N$ là số Carmichael vì phép thử Fermat là một thủ tục con của thuật toán Miller-Rabin. Trước hết ta chứng minh:

Claim 1: Không có số Carmichael có dạng $N = p^t$ với $t\geq 2$ và $p$ là một số nguyên tố.

Thật vậy, giả sử Claim 1 là sai, i.e, tồn tại số Carmichael có dạng $N = p^t, t \geq 2$. Nhóm $\mathbb{Z}_N$ có bậc $|\mathbb{Z}_N| = \varphi(p^t) = p^{t-1}(p-1)$ trong đó $\varphi$ là hàm Euler. Từ đó suy ra $a^{p^{t-1}(p-1)} \equiv 1 \mod N$ vớ mọi $a \in \mathbb{Z}_N$. Do $N$ là số Carmichael, $a^{N-1} \equiv 1 \mod N$, từ đó suy ra: $p^{t-1}(p-1) | N = p^t-1$. Tuy nhiên, điều này là không thể vì $p^{t-1}(p-1)$ chia hết cho $p$ còn $p^t-1$ thì không. Do đó Claim 1 là đúng.

Như vậy, $N$ không phải là lũy thừa của một số nguyên tố. Gọi $x$ là một số mũ tồi nếu tồn tại $a$ sao cho $a^x \equiv -1 \mod N$. Định nghĩa $S_x = \{a| 1 \leq a \leq N-1, a^x \equiv \pm 1 \mod N\}$. Ta sẽ chứng minh:

Claim 2: Nếu $N$ là một hợp số lẻ và không phải là lũy thừa của một số nguyên tố thì $S_x$ là một nhóm con đúng của $\mathbb{Z}_N$.

Ta sẽ tìm một số $b \in \mathbb{Z}_N$ mà $b \not\in S_x$. Trước hết ta có thể kiểm tra (coi như bài tập cho bạn đọc) các tiên đề của nhóm đối với $S_x$. Vì $N$ là một hợp số lẻ và không phải là lũy thừa của một số nguyên tố, tồn tại $N_1,N_2$ lẻ, nguyên tố cùng nhau, sao cho $N = N_1\cdot N_2$. Vì $x$ là một số mũ tồi, tồn tại $a$ sao cho $a^x \equiv 1 \mod N$. Áp dụng Chinese Remainder Theorem, ta tìm được $b \in \mathbb{Z}_n$ sao cho:

\begin{array}{lcl} b & \equiv & a \mod N_1 \\ b & \equiv & 1 \mod N_2 \end{array}

Từ đó ta suy ra $b^x \equiv a^x \equiv -1 \mod N_1$ và $b^x \equiv 1 \mod N_2$.

Nếu $b \in S_x$, ta có $b^x \equiv \pm 1 \mod N$. Ta có hai trường hợp:

  1. $b^x \equiv 1 \mod N$, ta sẽ có $b^x \equiv 1 \mod N_1$, trái với điều ta vừa chứng minh
  2. $b^x \equiv -1 \mod N$, suy ra $b^x \equiv -1 \mod N_2$, trái với định nghĩa của $b$

Do đó, $b \not\in S_x$.

Như vậy, Claim 2 là đúng. Gọi $\bar{x} = 2^{\bar{i}}m$ với $0 \leq \bar{i} \leq k$ là số mũ tồi lớn nhất. $\bar{x}$ tồn tại vì $R$ lẻ và $(-1)^R \equiv -1 \mod N$. Giả sử $a \in \{2,3,\ldots,n-1\}$ không phải là bằng chứng cho biết $N$ là hợp số. Gọi $0 \leq i \leq k$ là số trong Theorem 3, có hai trường hợp:

  1. Nếu $a^{m} \equiv 1 \mod N \Rightarrow a^{\bar{x}} \equiv 1 \mod N$, suy ra $a \in S_{\bar{x}}$
  2. Nếu $a^{2^im} \equiv -1 \mod N$, suy ra $2^im$ là một số mũi tồi. Do $\bar{x}$ là số lớn nhất, ta có $\bar{i} \geq i$, và do đó $a^{\bar{x}} = (a^{2^im})^{2^{\bar{i} - i}} \equiv \pm 1 \mod N$. Suy ra $a \in S_{\bar{x}}$.

Theo Claim 2, $S_{\bar{x}}$ là một nhóm con đúng của $\mathbb{Z}_N$, ta có xác suất số ngẫu nhiên $a \in S_{\bar{x}}$ là $\mathrm{Pr}[a \in S_{\bar{x}}] \leq \frac{|S_{\bar{x}}|}{|\mathbb{Z}_N|} \leq 1/2$. Từ đó suy ra Theorem 5.


Một số vấn đề thực thi

Thông thường trong các ứng dụng, chúng ta phải kiểm tra tính nguyên tố của các số rất lớn. Các số này có số lượng bít biểu diễn lớn, do đó, rất dễ bị hiện tượng tràn số nếu chúng ta thực thi không cẩn thận. Xét trường hợp $N$ là số nguyên 31 bít, khi thực hiện tính $a^b \mod N$ sử dụng thủ tục ModPower($a,b, N$) ở trên, chúng ta sẽ phải thực hiên phép nhân $(x*x) \mod N$ hoặc $x*x*a \mod N$ với $x,a$ là các số nguyên 31 bít. Kết quả của các phép nhân này có thể vượt quá 32 bít, và do đó chúng ta sẽ bị tràn số nếu chúng ta sử dụng kiểu int (giả sử bạn sử dụng ngôn ngữ $C$). Ta có thể giải quyết vấn đề này như sau. Trước hết tính $(x*x*a)\mod N = ((x*x)\mod N)*a \mod N$. Sau đó, ta sẽ khai báo một biến kiểu unsigned long long để lưu giữ kết quả của $x*x$ trước khi lấy $\mod N$. Bạn có thể áp dụng kĩ thuật trên cho bài toán này. Tuy nhiên không phải lúc nào chúng ta cũng có thể sử dụng biến kiểu dữ liệu lớn hơn.

Giả sử kiểu dữ liệu lớn nhất chúng ta có là $k$ bít (thông thường là 64 bít hoặc 128 bít), trong khi $N$ có kích thước $k-1$ bít (như trong bài toán này). Để tính tích $(x*x)\mod N$, ta thể sử dụng hai số $k$ bít để lưu trữ tích của hai số $k-1$ bít trước khi lấy modulo, tuy nhiên ta sẽ phải tự thực hiện phép modulo. May mắn là có một kĩ thuật giúp chúng ta tính $(x*x)\mod N$ sử dụng các số $k$ bít mà không phải thực hiện lai phép modulo. Tuy nhiên, chúng ta sẽ phải sử dụng $O(\log^2 x)$ thao tác bít cho phép nhân $x*x$. Thuật toán như sau:

ModMultiplication($a,b, N$):
    if $b = 1$
        return $a$
    else
        $x \leftarrow $ ModMultiplication($a,\lfloor \frac{b}{2} \rfloor, p$)
        if $b$ is even
            return $(x+x) \mod N$
        else
            return $((x+x)\mod N+a)\mod N$

 
Mình khuyến khích bạn đọc thực thi và áp dụng vào bài toán kiểm tra tính nguyên tố ở đây. Code cho bài toán này mình đính ở cuối bài.

Code: prime-testing-all-in-one, prime-testing-accepted-code.
Tham khảo

[1] Miller, Gary L. Riemann's hypothesis and tests for primality." Journal of Computer and System Sciences 13.3 (1976): 300-317.
[2] Rabin, Michael O. Probabilistic algorithm for testing primality. Journal of Number Theory 12.1 (1980): 128-138.
[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.
[4] James R. Lee, Note on Primality Testing, University of Washington, Winter 2008.

Facebook Comments

Tags: , , ,

  1. HTS’s avatar

    Chỗ cái hàm FermatTesting, câu return cuối là PRIME bác ad ơi.

    Reply

    1. Hùng Lê’s avatar

      Đúng rồi bạn. trong code thật mình để Prime. Lỗi đánh máy. Cám ơn bạn đã chỉ ra.

      Hùng

      Reply

    2. SN’s avatar

      Anh cho em hỏi là, trong research , thì với cùng 1 cài đặt hoàn toàn như nhau, thuật toán ngẫu nhiên có xác suất lỗi <1/2 thì việc chứng minh <1/4 có nhiều ý nghĩa không ạ? Còn trong thực hành thì sao ạ?
      Dĩ nhiên là nếu chứng minh được 1/4 thì số lần lặp chỉ cần bằng 1 nửa so với nếu chỉ chứng minh được 1/2.

      Reply

    3. BK’s avatar

      Anh cho em hỏi là trong research, với cùng với cài đặt hoàn toàn như nhau, thuật toán ngẫu nhiên có xác suất lỗi <1/2, thì việc chứng minh tiếp <1/4 có nhiều ý nghĩa không ạ? còn trong thực tế thì sao ạ?
      Dĩ nhiên là nếu chứng minh được <1/4 thì số lần lặp chỉ cần bằng một nửa so với chỉ chứng minh được 1/2

      Reply

      1. Hùng Lê’s avatar

        Câu hỏi của bạn rất hay. Câu hỏi này để trả lời đầy đủ thì rất dài. Nhưng mình tạm trả lời ngắn gọn như sau:

        Nếu nói về ý nghĩa thì mình nghĩ là nhiều. Thứ nhất nó làm thay đổi cách hiểu về thuật toán (nếu thực sự xưa nay người ta chỉ mới chứng minh dc 1/2 nhưng có vừa mới có người chứng minh được 1/4). Thứ hai, các phân tích mới thường mang vào những ý tưởng mới hoặc công cụ mới. Các ý tưởng này có thể sẽ mở ra những hướng mới, không chỉ với bài toán hiện tại mà cả các bài toán liên quan.

        Trong thực tế thì cac phân tích mới không thay đổi tính chất của thuật toán hiện tại, nhưng nó thay đổi cách mà chúng ta nghĩ về nó và ứng dụng nó. Ví dụ anh A nghĩ ra một thuật toán A đơn giản, với xác suất 1/2, và có thể 1/4 nhưng chưa ai chứng minh được, còn anh B nghĩ ra thuật toán B, có thể chậm hơn 1.5 lần, nhưng đảm bảo xác suất 1/4. Nếu cài đặt thì có thể bạn sẽ chọn A hoặc B tùy vào bài toán. Nhưng nếu anh C chứng minh được thuật toán anh A có xác suất 1/4 thì có lẽ chả có lí do gì mà bạn chọn B cả.

        Hùng

        Reply

        1. BK’s avatar

          Vâng ạ, cám ơn a đã giải đáp rõ ràng ạ.

          Reply

        2. phongvu’s avatar

          Đối với code C cần highlight, bạn có thể dùng trang https://gist.github.com, tạo file .c và lấy link nhúm ở phần embed

          Reply

          1. Hung Le’s avatar

            Cám ơn bạn đã gợi ý. Thực ra C code không phải là trọng tâm. Chủ yếu là mình minh họa cho một số bạn chưa quen nhiều với lập trình. Còn các bạn đã quen thì hiểu ý tưởng là các bạn đã code được rồi.

            Reply

          2. quan’s avatar

            ad giải thích giúp mh trong hàm mod_power, tại sao b lại giảm thành b/2

            Reply

            1. Hung Le’s avatar

              Đó là áp dụng của kĩ thuật chia để trị, bạn có thể xem thêm tại đây: http://www.giaithuatlaptrinh.com/?p=48

              Hùng

              Reply

            2. manhduc’s avatar

              em chào anh ạ, em cảm ơn anh vì bài viết rất hay. Anh có thể cho em hỏi chỗ Fermat's Little Theorem nếu a^(p-1) đồng dư với 1 theo modul(p) thì chỉ với p là số nguyên tố và số a là số nguyên thỏa điều kiện a không chia hết cho p. Còn nếu với điều kiện mọi số nguyên a và p là số nguyên tố thì a^p đồng dư với a theo modul p chứ ạ?Anh có thể giải thích cho được không ạ, cảm ơn anh rất nhiều.

              Reply

Reply

Your email address will not be published. Required fields are marked *