Given a quaternary quadratic equation of form $$Q(a,b,c,d)=m$$ in $\Bbb Z[a,b,c,d]$ with coefficient sizes and $|m|$ bounded in magnitude by $B\in\Bbb N$ where $m\neq0$ if we are looking for solutions modulo $q$ where $q$ is either a prime power or a composite then can the complexity with which we can solve this be $O(\log^\alpha (Bq))$ time at a fixed $\alpha>0$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
See the preprint https://arxiv.org/abs/1404.0281. I have just implemented this a month ago, and would be happy to share the code.
-
$\begingroup$ I am not looking for evaluation to $0$. $\endgroup$– TurboCommented Sep 20, 2017 at 5:21
-
$\begingroup$ also can you explain 'efficiently done by randomization'? $\endgroup$– TurboCommented Sep 20, 2017 at 5:28
-
2$\begingroup$ So what do you mean by solving? $\endgroup$ Commented Sep 21, 2017 at 6:29
-