Phân tích ra thừa số -- Integer factorization

Bài toán phân tích một số nguyên thành tích của các thừa số nguyên tố là một bài toán khó (nằm trong lớp các bài tóan \mathrm{NP} \cap \mathrm{Co-NP}). Hiện tai, chưa có thuật toán thời gian đa thức (polynomial time) nào có thể giải được bài toán này (nếu có thì toàn bộ các hệ thống bảo mật hiện tại sẽ đổ vỡ). Tuy nhiên, điều đó không có nghĩa là chúng ta hoàn toàn không giải được. Trong phần này, chúng ta sẽ thảo luận một số thuật toán (thời gian lũy thừa) để giải bài toán này, qua đó có một cái nhìn sâu hơn về bài toán.

Problem 1: Cho một số nguyên N, tìm các số nguyên tố p_1 \leq p_2 \leq \ldots \leq p_t sao cho N = p_1p_2\cdots p_t.

 
Chú ý: theo định lý cơ bản của số học (the fundamental theorem of arithmetic), phép phân tích N = p_1p_2\cdots p_t với p_1 \leq p_2 \leq \ldots \leq p_t là duy nhất.

Thuật toán \tilde{O}(\sqrt{N})

Ý tưởng cơ bản nhất để giải quyết bài toán này là duyệt dãy số nguyên tố:

P = \{ 2,3,5,7,11,13,17,\ldots \}

để tìm ước nguyên tố của N. Thông thường, sinh dãy số nguyên tố như vậy có thể rất tốn kém (phương pháp thường dùng là sử dụng Sàng Eratosthenes tốn khá nhiều bộ nhớ). Do đó, ta sẽ duyệt qua một dãy Q[1,2,\ldots,] = \{q_1,q_2,\ldots\} dễ sinh hơn dãy P sao cho P \subseteq Q (Q có thể chứa hợp số). Donald Knuth [1, p.364] đề xuất sử dụng dãy:

Q[1,2,\ldots] = \{ 2,3,5,7,11,13,17,19, 23, 25, 29, 31, 35,37,41,\ldots \} \qquad(1)

Ngoại trừ 2 số đầu tiên, dãy Q có khoảng cách giữa hai số kề nhau thay đổi liên tục giữa 24. Giả mã như sau:

NativeFact(N):
    Q[1,2,\ldots] = \{ q_1,q_2,q_3,q_4,\ldots \}
    i \leftarrow 1
    while Q[i] \leq N
        if N \mod Q[i] = 0         [[Q[i] is a divisor of N]]
            output Q[i]
            N \leftarrow \frac{N}{Q[i]}
        else
            i \leftarrow i+1

 
Mặc dù Q có thể chứa hợp số, ta có thể dễ dàng chứng minh (coi như bài tập cho bạn) các số Q[i] đầu ra của thuật toán luôn là các số nguyên tố và có giá trị tăng dần.

Từ giả mã trên ta thấy số lần lặp của vòng lặp while chính bằng số phần tử Q[i] \leq N của dãy Q. Hơn nữa, dãy Q càng gần dãy P thì số lần lặp càng ít. Trong trường hợp dãy Q như đề xuất (1), số lần lặp xấp xỉ bằng N/3. Trường hợp Q = P, số phần tử của Q chính là số lượng các số nguyên tố \leq N. Gọi \pi(x) là số các số nguyên tố nhỏ hơn hoặc bằng x. Định lý sau cho chúng ta biết giá trị tiệm cận của \pi(x):

Theorem 1 (Prime number theorem):

\pi(x) \sim \frac{x}{\ln x}

 

Do đó, theo prime number theorem, số lần lặp của vòng while trong trường hợp Q = PO( N/ \log N), tốt hơn đề xuất (1) O(\log N) lần. Với số nguyên N là rất lớn, sự khác nhau này thực sự không nhiều.

Chúng ta có thể cải tiến thuật toán dựa trên nhận xét sau:

Nhận xét: Nếu N không phải số nguyên tố thì p_1^2 \leq N.

Do đó, trong vòng lặp while ở trên, ta chỉ việc thêm thủ tục kiểm tra tính nguyên tố của N (sử dụng thuật toán Miller-Rabin) và thay điều kiện Q[i] \leq N bằng Q[i] \leq \lfloor \sqrt{N} \rfloor. Giả mã của thuật toán như sau:

FastNativeFact(N):
    Q[1,2,\ldots] = \{ q_1,q_2,q_3,q_4,\ldots \}
   if MillerRabinTesting(N) = \mathrm{PRIME}
       output N and exit
    i \leftarrow 1
    while Q[i] \leq \lfloor \sqrt{N} \rfloor
        if N \mod Q[i] = 0         [[Q[i] is a divisor of N]]
            output P[i]
            N \leftarrow \frac{N}{Q[i]}
            if MillerRabinTesting(N) = \mathrm{PRIME} \qquad(*)
                output N and exit
        else
            i \leftarrow i+1

 
Code của giả mã bằng C (code đầy đủ được đính kèm ở cuối bài):

#define PRIME 1
#define COMPOSITE 0
#define MAXNUMFACT 20 // 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

LLU llu_fsqrt(LLU N); // this function compute the floor of the square root of N

void fast_native_fact(LLU N){
	if(N == 1){
		return;
	}
	while (N % 2 == 0){
		Fa[++nfact] = (LLU)2;
		N = N/2;
	}
	while (N % 3 == 0){
		Fa[++nfact] = (LLU)3;
		N = N/3;
	}
	if( miller_rabin_testing(10, N) == PRIME ){
			Fa[++nfact] = N;
			return;
	}
	LLU Q = 5;
	int diff = 2;
	int sqrtN = llu_fsqrt(N);
	while(Q <= sqrtN){
		if(N %Q == 0){
			Fa[++nfact] = Q;
			N = N/Q;
			sqrtN = llu_fsqrt(N);
			if(miller_rabin_testing(10, N) == PRIME ){
				Fa[++nfact] = N;
				return;
			}
		}else {
			Q = Q + (LLU)diff;
			diff = (diff&2) + 2;// diff is alternating between 2 and 4
		}
	}
}

Phân tích thuật toán: Nhắc lại: p_{t-1} là ước số nguyên tố lớn thứ 2 của N. Vòng lặp while ít nhất phải duyệt đến phần tử thứ i của mảng Q sao cho Q[i] = p_{t-1}. Sau khi đã duyệt và in ra Q[i] = p_{t}, N = \frac{N}{Q[i]} = p_{t}, do đó, thủ tục kiểm tra tính nguyên tố ở dòng (*) sẽ in ra p_{t} và thuật toán kết thúc. Từ đó suy ra số lần lặp xấp xỉ là p_{t-1}. Do p_{t-1} < \sqrt{N}, số lần lặp là O(\sqrt{N}).

Ta sẽ tính tổng số phép kiểm tra tính nguyên tố (mỗi phép kiểm tra sử dụng O(\log^3 N) thao tác bít). Thủ tục kiểm tra tính nguyên tố sẽ được gọi mỗi lần tìm thấy một ước số của N. Do đó, tổng số phép kiểm tra tính nguyên tố xấp xỉ t. Ta có:

2^t \leq p_1p_2\cdots p_t \Rightarrow t \leq \log N

Từ đó suy ra tổng số phép kiểm tra nguyên tố là \log N.

Tương tự như vậy, tổng số phép tính \lfloor \sqrt{N} \rfloor xấp xỉ là t  \leq \log N. Mỗi phép khai căn \lfloor \sqrt{N} \rfloor có thể được thực hiện sử dụng O(\log^2 N) thao tác bít. Do đó, tổng thời gian cho phép khai căn là O(\log ^3 N).

Như vậy, tổng thời gian của thuật toán là O(\sqrt(N)\log N) = \tilde{O}(\sqrt{N}) trong đó nhân tử \log N là thời gian để thực hiện một phép cộng hoặc đồng dư O(\log N) bít.


Thuật toán trình bày ở trên chỉ thực hiện tốt khi N có khoảng từ 15-20 chữ số. Mình khuyến khích bạn đọc sử dụng thuật toán đó để giải bài toán này. Code đầy đủ đã accept mình đính kèm ở cuối bài. Bài tiếp theo mình sẽ trình bày thuật toán thời gian O(\sqrt[4]{N}), do đó, có thể phân tích các số tự nhiên có giá trị lớn hơn nhiều.

Code: fast-native-fact, fast-native-fact-spoj-accepted.

Tham khảo

[1] Knuth, Donald E. The Art of Computer Programming, vol. 2. Seminumerical Algorithms (1981).
[2] 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
[3] Pollard, John M. A Monte Carlo method for factorization. BIT Numerical Mathematics 15.3 (1975): 331-334.

Tags: , ,

Reply

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