Take two integers $n$ and $m$ with $0<\log_2m<n<m$ and let $r_1=f_1(n)\bmod m$ and $r_2=f_2(n)\bmod m$ for functions $f_1,f_2:\mathbb Z\rightarrow\mathbb Z$.
Denote the $\ell$ roots of $(f_i(n)\bmod m)^2\bmod m$ to be $r_i[1],\dots, r_i[\ell]$ and we know one of $r_i[j]$ is $r_i$.
Denote $\pi(a,b)$ to be product of all integers from $a$ to $b$.
Let $f_1(n)=2\pi(a,\lfloor\frac{b-a}2\rfloor)+1$ and $f_2(n)=2\pi(\lfloor\frac{b-a}2\rfloor+1,b)+1$.
Given $m$ and an integer $r$ can we find an $n\in[r,2r]\cap\mathbb Z$ such that $r_1[1]=r_1$ and $r_2[1]=r_2$ in $\mathsf{polylog}(mr)$ time?
Essentially I give you $m$ and $r$ can we find such an $n$?
On average it takes about $\ell^2$ trials to get both $r_1[1]=r_1$ and $r_2[1]=r_2$ however it is not verifiable that easily. Essentially I am asking if we can derandomize this and verify this?
