Factorization

Factorization

因式分解。這裡談的是把一個正整數分解成質因數的連乘積:

n = 2^m1 * 3^m2 * 5^m3 * 7^m4 * 11^m5 * …

凡是正整數都可以分解成一個獨一無二的式子,不同的n就會對應不同的(m1, m2, m3, …),反方向亦同。

因數分解問題屬於NP問題,目前尚未有好解法。

Trial Division Factorization Method

演算法

把所有可能的因數拿來試除。用質因數會更好。

當要因式分解的數字有很多筆時,可以先建好質數表,然後只拿質因數來試除。

UVa 516 583 10179 10290 10329 10392 10622 10780 10791

Fermat's Factorization Method

演算法

把一個數字分解成兩個數的乘積(這兩個數不一定會是質數)。一直遞迴分解下去,無法再分解的時候就找到質因數了。分解手法如下:

現在要找出 a 和 b 讓 n = a*b
使用公式 x^2 – y^2 = (x+y) * (x-y)
令 n = x^2 – y^2, a = x+y, b = x-y
窮舉整數 x,看看 sqrt(x^2-n) 是不是剛好就是一個整數 y,
如果是整數就找到一組 a 和 b 了。

Pollard's p-1 Factorization Method

演算法

這個方法可以找出n的其中一個質因數p。數學家Pollard證明當p-1的質因數都不大於b時,則p = gcd(2^b! - 1, n)。各位可以從wiki找到證明。:)

選定一個適當的b後,就可以進行演算法。有可能會找不到質因數。

Pollard's ρ Factorization Method

演算法大意

這個方法可以找出n的其中一個質因數p。有可能會失敗。

若有兩數x和y,p可以整除x-y,n不能整除x-y,則p = gcd(x-y, n)。

這個p可能是1、n、n的質因數,但是只要努力不懈地列舉x和y,就有機會求得n的質因數。

以亂數產生器列舉x和y

首先使用一個簡單的亂數產生器f(ai+1) = ai2 + c,以及亂數種子a0,其中c為整數常數。然後以(a1 , a0) (a2 , a1) (a3 , a2) … (an-1 , an-2)這些數對作為x和y。

讀者可在此思考一下:

一、為何亂數產生器不選用f(ai+1) = ai + c這條更加簡單的式子?

二、為何a0至少要是+2?

三、為何c不可以是0,也不可以是-2?讀者可將亂數產生器的式子,代入到x和y之中,計算一下x-y,並計算gcd(abs(x-y), n)。

四、如果我們將x和y對調,對結果有影響嗎?

五、為何p等於n的時候,就要結束迴圈,宣告失敗,不繼續找了?

小改進:x和y可以先模n,防止溢位

計算gcd(abs(x-y), n)的時候,其實就會拿abs(x-y)去模n。所以我們可以讓x和y每次都先模n,或者是讓亂數產生器每次都模n,這麼做不影響結果。不斷模n,可以防止x和y溢位,好處多多。

小改進:偵測循環

方才的列舉方式並不完美。我們知道,在模n的情況下,x和y最終必會重複出現,產生循環。我們得在循環開始時,就立刻結束演算法,否則接下來就會一直遇到重複的數字,進行重覆的運算。況且越早進入循環,就有越多數字白算。

Pollard採用了Floyd's Cycle Finding Algorithm的概念來偵測循環,以(a1 , a2) (a2 , a4) (a3 , a6) … (an , a2n)這些數對作為x和y,一旦an等於a2n即發現循環(當有模n的情況下),馬上結束演算法。

演算法到此告一段落!各位在實作時,如果演算法失敗,可以更換a0和c,或許就可以找出質因數了!

至於這個演算法的名稱由來,是因為不斷列舉a0 , a1 , a2 , ...,最終必會循環,繪圖時可以畫成一個ρ (rho)的形狀,因而得名。

非常可惜,沒有練習題!