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?

  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jun 3 at 23:09
  • $\begingroup$ @GerryMyerson Updated. Also $n!\bmod m$ is not known to be in $polylog(nm)$ time. $\endgroup$ – Turbo Jun 3 at 23:27
  • 1
    $\begingroup$ 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$. $\endgroup$ – Greg Martin Jun 4 at 6:39
  • $\begingroup$ @GregMartin good remark. One could first try the question with $m$ being a prime number, for which case the phrasing is correct. $\endgroup$ – Frank Waaldijk Jun 4 at 8:29
  • 1
    $\begingroup$ Eight edits in 16 hours. Hard to hit a moving target. $\endgroup$ – Gerry Myerson Jun 4 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.