If $N=PQ$ is a semi-prime with $P=N^{\frac12 +\delta}$ and $Q=N^{\frac12-\delta}$ then if we know $\delta\in(0,\frac12)$ to a reasonable precision we can factor $N$ quickly. What precision (number of bits in real representation of $\delta$) suffices with current technology and is there a reference?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
Direct factoring of $N$ with the NFS will take $$M=exp(c \ln N^{1/3} \ln \ln N^{2/3})$$ computations. Take $N$ large enough so that the best factoring algorithm is the NFS.
Let $\delta>0$ and for simplicity say you know that $t-1,$ most significant bits of $$(1/2)-\delta=0.b_1 b_2\cdots b_t\cdots$$ are zero, which implies $\delta \in (0,2^{-t}).$
By the PNT you have approximately $$ F=\frac{2 N^{1/2}}{\ln N} $$ candidate primes in this interval (subtracting the primes up to $\sqrt{N}2^{-t}$ asymptoticaly makes little difference). Deterministic primality testing by AKS algorithm will cost $O((\ln N)^{6}),$ thus the inequality $$ F < M (\ln N)^{-6} \quad (1) $$ must hold for this to be better than NFS. Taking logs gives $$ \ln\left[ 2 \sqrt{N} ( \ln N)^5 \right] \sim \frac12 \ln N + 5 \ln \ln N < c \ln N^{1/3} \ln \ln N^{2/3}, $$ which means this aproach is worse than the NFS.
Of course there are the constants in front of the big oh expressions that are machine dependent which need to be estimated.
Bounds on smooth/rough numbers in intervals don't seem to give anything substantially better at a quick glance. But some experts here may know more.
