A Local-global Principle for Diophantine Equations
Lipton, Richard J.
Vishnoi, Nisheeth Kumar
MetadataShow full item record
We observe the following global-local principle for Diophantine equations: If an equation f(x₁,...,x[subscript t]) ϵ ℤ[x₁,...,x[subscript t] = p can be solved efficiently for a dense set of primes p, then one can efficiently obtain solutions to equations of the form f(x₁,...,x[subscript t]) Ξ r mod n. This is done without any knowledge of the factorization of n. We apply this principle to get the following results: - There is an efficient algorithm to solve a modular version of Fermat's equation x² + y² Ξ r (mod n). - Assuming factoring is hard, it is hard to solve the following equation for a dense set of primes p : x² - y² = p - 1. Randomness and Extended Riemann Hypothesis are essential in the proofs.