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$?
Solving quaternary quadratic forms modulo $q$ efficiently
Turbo
- 13.9k
- 1
- 27
- 76