保理费用$u^2-v^2$当$v\ll u$？

Question

分解N=u^2-v^2时v\ll u的近似计算成本是多少？假设u和v是未知整数，u足够大，使得n具有RSA模的大小。

我怀疑，随着v的增长，至少会有四个范围的，并怀疑袖口在哪里：

1. v足够小，对于u_0=\left\lceil\sqrt N\,\right\rceil来说，{u_0}^2-n是一个整数，因此u=u_0、v=\sqrt{u^2-N}和n=(u-v)(u+v)。
2. 费马保理和简单的改进是有竞争力的。基线依次尝试i，直到(u_0+i)^2-N是正方形，因此是u=u_0+i，其余的如上面所示。
3. 一种基于Coppersmith定理的方法是最好的。在这个答案之前我不知道它的存在。
4. GNFS成为国王。

更新:我发现(1)适用于v直至\sqrt2\,N^{1/4}。

Answer 1

费马方法在|p-q| = 2v < N^{1/4}时立即成功。

当纸使用基于Coppersmith的方法时，|p-q| = 2v < N^{1/3}声称多项式时间因式分解。