Solving polynomial equations when you know in which number field the solutions live Suppose I have a bunch of polynomial equations with coefficients in a number field, and suppose further that I'm guaranteed a priori that they have a solution in that number field.  Can I leverage that knowledge into a technique for solving the equations more easily?  The cases we care about are massively overdetermined systems of linear and quadratic equations.
 A: By Scott's remark, it seems that the linear terms do not suffice for determining the set S. (what is the expected cardinality of S, btw?) I know nothing about programming or complexity, but my suggestion is to try taking the 2-duple embedding. Sure, you replace P^20 by P^200 or so, but now you end up with linear equations in the variables X_ij = x_i x_j. Of course, you still have the quadratic equations in X_ij which determine the image of the 2-uple embedding, but at least now you will have 10^5 linear terms and then < 200 quadratics, even if you have a few more variables...  If you are lucky, the linear space cut out in P^200 might actually be quite small.
A: Practically speaking: I would try to reduce the equations modulo several small primes (or prime powers), solve them by brute force, and then try to lift to solutions in your number field using the chinese remainder theorem. It might be helpful to combine this with solving them to high precision over the real (or complex) numbers.  
A: I have to say that this sounds suspiciously close to Matiyasevich's proof of Hilbert's 10th problem (Yuri V. Matiyasevich, Hilbert's Tenth Problem, MIT Press, Cambridge, Massachusetts, 1993). The "yoga" of his proof is that you can have some "Godel coding" on systems of quadratic and linear forms, which shows that solving a system of such equations is hard from a logic/TCS point of view.
A: Should be able to use Groebner bases and elimination theory to do it, I think.  Though in the case of linear and quadratic equations, I'm not sure how much help it will be.
A: One minor comment: if you can ever reduce to solving equations in a single variable, and looking for rational roots, then you can use the rational root theorem. You can reduce to the case where your number field is the rationals easily enough. (For example, if you started out looking for roots in Q(i), write everything as a+bi.) But I don't know that there is any good way to reduce to equations in a single variable.
A: Well, it's certainly easier to intersect lines and quadrics. I would simply go on intersecting all lines, and then select some nicer quadrics to intersect until I'm having a finite set of points, from which I would eliminate the wrong points by using more quadrics until one is left, the answer.
