Related to open problem and this question.
Let $N=p q$ be integer with unknown factorization.
Q1 Given $N=pq$, with what complexity we can find integer $a : q-\sqrt{q} < a <q+\sqrt{q}$?
Assume that an oracle answers if given integer satisfies the inequality.
Something subexponential in $\log{q}$ will be of great interest.
Trivial upper bound of $O(\sqrt{q})$. Choose upper bound $B$ for $q$. Try $\sqrt{B}$ random integers in the range $(1,B)$.
Let $D$ be real constant $ 0 < B <1$.
Q2 Given $N,B$, with what complexity we can find integer $a : q-q^B < a <q+q^B$?
By the above construction we get $O(q^{1-B})$.
Q1 Is related to the order of the elliptic curve over $GF(q)$. Using smooth integers, in subexponential time we get multiple of $a$, but recovering $a$ depends on many small factors.
