# Deterministically finding a subsequence of integers matching modular roots?

Take two integers $$n$$ and $$m$$ with $$0<\log_2m 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?

• I don't understand. If I'm given $m$ and $n$, I can just calculate $r$ and get it right 100% of the time with no "statistical test". If all I'm given is $r_1$ and $r_2$ then deciding which one is $r$ requires mindreading, not statistics. Please edit your question to clarify what's going on here. – Gerry Myerson Jun 3 at 23:09
• @GerryMyerson Updated. Also $n!\bmod m$ is not known to be in $polylog(nm)$ time. – Turbo Jun 3 at 23:27
• Your setup has a problem: the number of square roots, modulo $m$, of $f_i(n)^2$ is usually far more than $2$. Indeed, if $m$ has $k$ prime factors, then the number of square roots will be $2^{k-1}$, $2^k$, or $2^{k+1}$ depending on the power of $2$ dividing $m$. – Greg Martin Jun 4 at 6:39
• @GregMartin good remark. One could first try the question with $m$ being a prime number, for which case the phrasing is correct. – Frank Waaldijk Jun 4 at 8:29
• Eight edits in 16 hours. Hard to hit a moving target. – Gerry Myerson Jun 4 at 13:07