Skip to main content
1 of 5
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Solving quaternary quadratic forms modulo $q$ efficiently

Given a quaternary quadratic form $Q(a,b,c,d)\in\Bbb Z[a,b,c,d]$ with coefficient size bounded in magnitude by $B$ if we are looking for solutions modulo $q$ where $q$ is either a prime power or a composite what is the complexity with which we can solve this in $O(\log^\alpha (Bq))$ time at a fixed $\alpha>0$?

Turbo
  • 13.9k
  • 1
  • 27
  • 76