推 a016258 : 推 感謝 11/27 10:12
: 推 a016258 : #1OstxQhG (Grad-ProbAsk) 11/26 23:16
想補充一下這篇文提到的做法和樓上回文提到的多質數狀況
那個做法的本質如該文推文所言是平方差沒錯:
https://en.wikipedia.org/wiki/Fermat%27s_factorization_method
但多質數時不是不能做, 只是數字會非常不好找
以當時回文舉的 532381 為例, 它的平方根是 729.多
但得要找到 1055^2 = 1113025 差 580644 = 762^2 才是平方數
問題在於, 這個平方差法需要這數能拆成兩個差很少的數的乘積才容易找
(這兩數的差的一半會是這個平方數差的平方根)
換句話說就是原數在其平方根附近有因數
而這種題目的出法會出成兩個接近的質數相乘, 因此才能用這種方法來找
這種方法並不要求這接近其平方根的因數是質數:
以 765049 為例, 它的平方根約是 874.多
試 875 馬上可以看到 875^2 = 765625 差 576 = 24^2
於是我們就有 765049 = 875^2 - 24^2 = (875+24)(875-24) = 899*851
但這兩個因數也都是合數, 而且也很容易地可以用同法拆開:
899 = 900 - 1 = 30^2 - 1^2 = (30+1)(30-1) = 31*29
851 = 900 - 49 = 30^2 - 7^2 = (30+7)(30-7) = 37*23
所以我們得到 765049 = 23*29*31*37
一樣可以很快得到答案, 而這是因為 765049 在其平方根 874.多 附近有因數而已
====
那回到不好拆的部份
我上面引的維基百科條目有提到可以利用平方同餘的性質來加速搜尋
就拿文中提到的三個模數用在剛才的 532381 來看:
* 考慮模 20 同餘, 原數餘 1
平方數模 20 只會餘 0,1,4,5,9,16, 其中差 1 的只會是 5-4 和 1-0
所以大數平方模 20 餘 1 或 5, 即大數本身模 20 可能餘 1, 5, 9, 11, 15, 19
或簡化成模 10 餘 1, 5, 9
* 考慮模 16 同餘, 原數餘 13
平方數模 16 餘 0,1,4,9, 差 13 的只有 1-4
所以大數模 16 可能餘 1, 7, 9, 15, 或簡化為模 8 餘 1 或 7
* 考慮模 9 同餘, 原數餘 4
平方數模 9 同餘是 0,1,4,7 所以只會是 4-0, 所以大數模 9 餘 2 或 7
以上三個合併起來可以知道大數模 360 可能餘:
25, 65, 79, 119, 151, 169, 191, 209, 241, 281, 295, 335
那從 729 往上數會經過
745, 785, 799, 839, 871, 889, 911, 929, 961, 1001, 1015, 1055←就找到了
只是這一大段要用紙筆計算大概半個小時跑不掉吧...
====
延伸出來, 這個找平方差的方法如果找數字的策略改進的更聰明一點
就會成為目前世界上兩個最快的質因數分解演算法了
比較容易理解的是第二名 二次篩選法 https://tinyurl.com/s24k5k7
第一名的普通數域篩選法用到其他數論結果和多項式搜尋所以比較複雜一點
(中文維基百科的這一條根本就只寫了個開頭...)
也因此它是適用在像 RSA 模數這種等級的大數上面的演算法
--
有人喜歡邊玩遊戲邊上逼；
也有人喜歡邊聽歌邊打字。
但是，我有個請求，
選字的時候請專心好嗎？
-- 改編自「古 火田 任三郎」之開場白
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.3.123 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1574791524.A.40C.html