1
$\begingroup$
  • Let $\mathbb{F}=\mathbb{Z}/p\mathbb{Z}$ a cyclic field. Where $p$ is fixed
  • Let $(H)_{n\in\mathbb{N}} \in \mathbb{Z}[x_1,\dots]^{\mathbb{N}}$ a family of polynomials with $H_n\in \mathbb{Z}[x_1,\dots,x_n]$
  • Let $\varphi : \mathbb{Z}\rightarrow \mathbb{F}$ the ring isomorphism defined by $\varphi(x)=x\bmod p$
  • Let $f$ a positive increasing function of the size of polynomial.
  • Let $u_1,\dots,u_n \in\mathbb{F}$

With that, I was thinking about the following problem: Suppose that $\varphi(H_n^2)(u_1,\dots,u_n)$ can be calculated in $\mathcal{O}(f)$ time. Can we calculate $\varphi(H_n)(u_1,\dots,u_n)$ in $\mathcal{O}(f)$ times?


To illustrate an example, I will refer to the Vandermonde polynomials: $$ V_n(x_1,\dots,x_n)=\prod_{i<j}x_j-x_i $$ I was able to calculate $V_n^2(u_1,\dots,u_n)$ in $\mathcal{O}(M(n) \log n)$ as follow:

  • Build $P(x)=\prod_{i=1}^{m}x-u_i$
  • Calculate $P'(u_1),\dots,P'(u_n)$ using fast multi-point evaluation
  • The result is the product $\prod_{i=1}^{n} P'(u_i)$

Now, with $V^2_n(u_1,\dots,u_n)$ calculated. There are (usually) two candidates for $V_n(u_1,\dots,u_n)$ that can be calculated in $\mathcal{O}(1)$ (The cyclic field is fixed). I was not able to arrive to any method that can extracts the correct square root from both candidates.

That is it appears to me that both square roots are indistuinguishable in $\mathbb{F}.$ But they are in fact distinguishable in $\mathbb{Z}$ as we can infer the sign from the sign $\delta(\Pi)$ of the permutation $\Pi$ that sorts $(u_1,\dots,u_m)$ in their increasing order.

In the other hand I was able to have a $\mathcal{O}(M(n) (\log n)^2)$ algorithm as described here.

So to conclude, is calculating $V_n^2$ and $V_n$ in the same computational class?

$\endgroup$

1 Answer 1

0
$\begingroup$

I don't believe you can compute $\varphi(H_n)(u_1,\dots,u_n)$ from $\varphi(H_n^2)(u_1,\dots,u_n)$ in a black-box manner, because there are two possibilities for the square root, exactly as you wrote.

Whether you can compute $\varphi(H_n)(u_1,\dots,u_n)$ efficiently depends on $H_n$.

I don't know whether you can compute $V_n(u_1,\dots,u_n)$ in $O(M(n) \log n)$ time.

I realize this is probably not helpful. I'm trying to answer exactly the question you asked.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.