Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power
Chandan K. Dubey, Thomas Holenstein · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2014
Let p be a prime and k, t be positive integers. Given a quadratic equation Q(x1,x2,...,xn)=t mod p^k in n-variables; we present a polynomial time Las-Vegas algorithm that samples a uniformly random solution of the quadratic equation.