Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power

Download
Full text (published version) (PDF, 497.1Kb)
Thumbnail
Open access
ccby
Author
Dubey, Chandan
Holenstein, Thomascc
Date
2014
Type
    Conference Paper
Rights / license
Creative Commons Attribution 3.0 Unported
Abstract
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.
Permanent link
https://doi.org/10.3929/ethz-b-000094269
Publication status
published
External links
Search via SFX
Editor
Jansen, Klaus
Rolim, José D.P.
Devanur, Nikhil R.
Book title
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Journal / series
Leibniz International Proceedings in Informatics
Volume
28
Pages / Article No.
643 - 653
Publisher
Schloss Dagstuhl-Leibniz-Zentrum für Informatik
Event
17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2014), and the 18th International Workshop on Randomization and Computation (RANDOM 2014), Barcelona, Spain, September 4-6, 2014
Subject
Quadratic Forms; Lattices; Modular; p-adic
Organisational unit
03841 - Holenstein, Thomas  
More
Show all metadata
ETH Bibliography
yes
Altmetrics