費馬法分解因數

↑↑相關文章在這裡↑↑

將一個合數分解成素數相乘，是數論基本問題。

我們凡人的思路是，從2,3,5,7,11……開始一一試，如果能整除則可以將合數分解，如果判斷到開方數還沒有整除，則這個整數本身就是一個素數。

如分解10379

10379≡1(mod 2)

10379≡2(mod 3)

10379≡4(mod 5)

10379≡5(mod 7)

10379≡6(mod 11)

……

10379≡0(mod 97)

所以，10379被97整除，有一個因數是97

所以，10379=97×107

97和107都是素數，分解完成。

凡人解法優在簡單易理解。

我們看看高人費馬是如何分解的。

搞定！帥死人

其基本思路是，

等等，這樣算出來，你怎麼保證分解完成了，如果97還能繼續分解呢？

要判斷97是不是素數，只要試2,3,5,7這幾個素數就夠了，很顯然，這幾個數都不能整除97，所以，97是素數，不能再分解

對於107，也只要試2,3,5,7就夠了，顯然它也是素數。

所以，10379=97×107

我們再算一個數93343

再看269，只要用前幾個素數除即可

269≡1(mod 2)

269≡2(mod 3)

269≡4(mod 5)

269≡3(mod 7)

269≡5(mod 11)

269≡9(mod 13)

所以，269是素數

再看347，也只要用前幾個素數試試即可

347≡1(mod 2)

347≡2(mod 3)

347≡2(mod 5)

347≡4(mod 7)

347≡6(mod 11)

347≡9(mod 13)

347≡7(mod 17)

所以347是素數

所以，93343=269×347

再看一個更大的數：2027651281

所以，2027651281=(45041-1020)(45041+1020)=46061×44021

我們發現，凡人的思路是從小往中間試，費馬的思路是從中間往小試。

於是對於兩個因子接近的大數分解，費馬法有優勢，而兩個因子相差很大，凡人的思路還快點。如果待分解的數很大很大，我們並不知道它的因子差是大還是小，蠻難選擇的。

所以，費馬法分解因數，也就玩玩吧。實用價值不大。

我們致力於讓您不討厭的數學，如果覺得有趣，點個「在看」