用篩法。我們僅考慮分解奇數。（原因？）現在我們可以假設n=pq,pq必可寫作(x+y)(x-y)也即我們需要找到x2≡y2 (mod n)我們可以考慮，在 kn 附近的完全平方數 x2 中，分解 x2 mod n. 由於 x2 接近 kn, 因此 x2 mod n 一般因數比較小。對於每個這樣的完全平方數都逐個分解是很慢的，這個時候我們就可以使用篩法。在找到了足夠多 x2 mod n 的因數分解後，我們就可以用線性代數方法找到一個 y2 了。具體怎麼做請自行思考。Upd: 有心情所以再來寫點。你可以考慮在一個模 n 意義下的橢圓曲線上做加法。如果 n=pq, 你有一個橢圓曲線 E 和一個在橢圓曲線上的點 a, 那麼有當你在計算 ta 時，如果 #E(F_p) | t, 則會到無窮遠點，這個時候你在模 n 意義下計算就能得到 p 的值。這個演算法可行的原因是關於 #E(F_p) 的Hasse定理和一個關於其分佈的 conjecture. (當然還有smooth number相關的那些估計)Upd Upd: 表示勘誤。注意這些提到的演算法都不保證能找到一個解，但是找到一個非平凡解的機率可以很高。這兩個演算法都稍遜於 SoTA(GNFS).
用篩法。我們僅考慮分解奇數。（原因？）現在我們可以假設n=pq,pq必可寫作(x+y)(x-y)也即我們需要找到x2≡y2 (mod n)我們可以考慮，在 kn 附近的完全平方數 x2 中，分解 x2 mod n. 由於 x2 接近 kn, 因此 x2 mod n 一般因數比較小。對於每個這樣的完全平方數都逐個分解是很慢的，這個時候我們就可以使用篩法。在找到了足夠多 x2 mod n 的因數分解後，我們就可以用線性代數方法找到一個 y2 了。具體怎麼做請自行思考。Upd: 有心情所以再來寫點。你可以考慮在一個模 n 意義下的橢圓曲線上做加法。如果 n=pq, 你有一個橢圓曲線 E 和一個在橢圓曲線上的點 a, 那麼有當你在計算 ta 時，如果 #E(F_p) | t, 則會到無窮遠點，這個時候你在模 n 意義下計算就能得到 p 的值。這個演算法可行的原因是關於 #E(F_p) 的Hasse定理和一個關於其分佈的 conjecture. (當然還有smooth number相關的那些估計)Upd Upd: 表示勘誤。注意這些提到的演算法都不保證能找到一個解，但是找到一個非平凡解的機率可以很高。這兩個演算法都稍遜於 SoTA(GNFS).