I have a question. I am interested in finding the solution to congruences of the form:
x^2 + ax + b = 0 (mod p) with p a large prime. I am interested in an algoirthm for finding solutions to this that is more efficient then checking all of the numbers 1,....,p-1. Also, I would like to know what conditions can be put on a, b and p to guarantee the existence of an integer solution to this congruence.
Any ideas?
You are not going to understand it.
This Law (Quadradic Reciprocity) is among the most beautiful equations I have ever seen. Below is the elegant way of writing it. If you do not understand it, I will not explain it, it will take a long time.
An equivalent formulation of Quadradic Reciprocity (but not as elegant) is,
x^2 = p (mod q) has a solution.
And,
q=1 (mod 4) or p=1 (mod 4)
Then,
x^2 = q (mod p) has a solution.
Otherwise none.
Note p,q are distinct primes.
yes,
but what you are writing helps me to look at solutions of the form x^2 + b =0 (mod p), but not the form I want x^2 + bx + c = 0 (mod p).
I know the stuff you are saying...what I need is an algorithm that efficiently checks for solutions and also would like to know if there are some conditions that could be put on b,c, and p that would guarantee a solution to this.
It doesn't seem like you are addressing my question, but really adressing a much simpler question using quadratic residue theory.
I'm not a number theory student, but I have some advice that might help you: As you have pointed out, you can find if an answer exists to the form x^2 + b = 0 (mod p). If so, then a little algibraic manipulation might help confirm whether a solution exists to x^2 + bx + c = 0 (mod p). Complete the Square:
(x + b/2)^2 + (c - [b/2]^2) = 0 (mod p)
Does that help any? (I have no clue whether that works, I just thought I'd throw something out there for you to consider.)
So, PerfectHacker....I have another question. I now see how to determine whether there is a solution. How do I actually find the solutions based upon what you wrote...? Is there an algorithm that will lead me from what you wrote to find the actual solutions to a given quadratic (mod p). If possible, could you illustrate with an example of a polynomial and a solution..? Thanks so much for your help. I am not a number theorist, but this will be useful in my research
twells
As I mentioned before, I do not know of a formula that gives a solution, rather than trial an error.
Furthermore, I am not an algorithmist, however, the algorithm is not very nice.
Funny, it never addresses the question for prime numbers themselves.Originally Posted by Wikipedia
Maybe there is one.
----
I can tell you how to find solutions to p^2,p^3,p^4,...
Ones you find it for p.
And then I can tell you how to find it for composite numbers because they can be factorized in terms of prime powers (my signature tell you that ).
you mentioned using the law of reciprocity to determine whether a quadratic (mod p) has a solution or not? How would you actually use that law?
Because if p is a large prime, then determing whether (a^2-4b/ p) is 1 or -1 is also a nontrivial problem if p is huge.