冰情工作室

大數分解: 對於位數過大的正整數進行質因數分解, 會因為位數範圍與數字結構而選擇適當的分解方法

------

以下介紹幾個方法:

------

1. 費馬平方差法 (Fermat Method, Square Subtraction)

    n, a, b 為正整數, 滿足 n= a^2 - b^2, 即 n 是 a,b 兩數的平方差, 則可得知 n = (a+b).(a-b), a+b 與 a-b 皆為 n 的因數

    若 a+b 與 a-b 的差距很小, 則 n 被分解的速度會更快, 也就是 b = [(a+b)-(a-b)]/2 可從 0 開始嘗試, 則 n 即可被分解

    另, 發現 p 是 b 的奇質因數, 需滿足 (n/p)L = 1 or 0 (注1)

    另, a+b 與 a-b 若是 n 的因數, 其差距為 c.log2(n), c 為常數, 即可稱為幾乎相等 (注2)

      ////  注1: (n/p)L 是勒讓得符號, (n/p)L  =1 代表 n 是 p 的二次剩餘, (n/p)L  = 0 代表 n 是 p  的倍數, (n/p)L  = -1 代表 n 不是 p 的二次剩餘  ////

      ////  注2: log2(x), 是 x 以 2 為底的對數, 即 x = 2^(log2(x))  ////

-------

2. 二次剩餘篩法 (Quadratic Residue Sieve)

------

3. 雙公因數法 (Two Variants Co-factored Method)

------

有機會在介紹其他方法