GCD factorisation in $f(k) = k^2 + k + N$: is the clustering near $\lfloor\sqrt{N}\rfloor$ documented?
问题内容
For a semiprime $N = p×q$, consider the sequence $f(k) = k^2 + k + N$, for $k = 0, 1, 2, ...$ Since $f(k) ≡ k(k+1) \mod N$, we have gcd($f(k), N$) = gcd($k(k+1), N$). This means a factor of $N$ is revealed at position $k$ whenever $p$ divides $k$ or $k+1$.
For $N = 77 = 7×11, f(k) = k^2 + k + 77$ starts: $77, 79, 83, 89, 97, 107, 119, 133, 149, 167, 187, 209, ...$
$$k=6: f(6) = 119 = 7×17, gcd(119, 77) = 7$$ $$k=7: f(7) = 133 = 7×19, gcd(133, 77) = 7$$ $$k=10: f(10) = 187 = 11×17, gcd(187, 77) = 11$$ $$k=11: f(11) = 209 = 11×19, gcd(209, 77) = 11$$
Note that $\lfloor\sqrt{77}\rfloor = 8$. Both factors appear within $2$ steps of $k=8$. Empirical observation: scanning the window $k=\lfloor\sqrt{N}\rfloor± w$ reveals a factor of $N$ with the following success rates over odd semiprimes below $2000$:
$$w=0 (1 check): 38.9%$$ $$w=1 (3 checks): 63.8%$$ $$w=3 (7 checks): 83.1%$$ $$w=10 (21 checks): 98.5%$$ $$w=20 (41 checks): 100%$$
The heuristic: $k(k+1) ≈ N$ when $k ≈ \sqrt{N}$, putting us in the right neighbourhood to share factors with $N$. The window grows as $O(\sqrt{N})$ worst case, so no complexity wall is broken.
Question: Is this clustering near $\lfloor\sqrt{N}\rfloor$ documented anywhere? Is there a clean theoretical explanation for the success rate behaviour?
回答 (0)
暂无回答记录。