Fermat法の

    2018/09/29 神奈川大学 後 保範 (Kanagawa University, Ushiro Yasunori )

1. Fermat法による因数分解

 Nが成数のとき(M+x)2-Nが平方数になるものをx=1,2,3...と増やして見つけ
 、N=P×Qと因数分解する。PとQが非常に近いとき有効。MはNの平方根の整数部
 PとQの比が整数a,bに近いと拡張Fermat法:(M+x)2-4abNが有効
 

2. FSS(高速平方探査法)

 FSS: Fast Squared Search method
 NAS2017での講演資料:FSS資料