1. ## Solving quadratics (mod p)

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?

2. Originally Posted by twells1303
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.
There is no method that gives you an "x" which works.
(There might be fast algorithms, but that I do not know.)

3. Originally Posted by ThePerfectHacker
you mind showing it to us?

4. Originally Posted by Jhevon
you mind showing it to us?
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.

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.

5. I know Guass's Reciprocity law and know quite a bit about quadratic reciprocities. But, I need to come up with a solution to the question I asked for the application I am working on. Anyone else have an idea?

6. Originally Posted by twells1303
I know Guass's Reciprocity law and know quite a bit about quadratic reciprocities. But, I need to come up with a solution to the question I asked for the application I am working on. Anyone else have an idea?

Okay, here is how you can use it.

Determine if,

x^2 = 10 (mod 101)

Has a solution.

7. ## more help

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.

8. Originally Posted by twells1303
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.)

9. Originally Posted by twells1303
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 heard you the first time. Just one time is all you got to tell me.

Say p is odd prime.

*)Note, if the discriminant (that is what it is if you realized) is =0 (mod p) the Legendre Symbol is undefined. But that case is trivial.

10. ## an algorithm?

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

11. Originally Posted by twells1303
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.

Originally Posted by Wikipedia
The problem of finding a square root in modular arithmetic, in other words solving the above for x given q and n, can be a difficult problem. For general composite n, the problem is known to be equivalent to integer factorization of n (an efficient solution to either problem could be used to solve the other efficiently). On the other hand, if we want to know if there is a solution for x less than some given limit c, this problem is NP-complete
Funny, it never addresses the question for prime numbers themselves.

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 ).

12. ## law of reciprocity

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.

13. Originally Posted by twells1303
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.
Say you have, p=101 and x^2=50(mod 101).

(50/101)=(25/101)*(2/101)=(2/101) because 25 is square.

Since 100=1 (mod 4) we can flip,

(101/2)=(1/2) because 101=1(mod 2).
So it is solvabe.

(This was bad example because 2 is an even prime, but whatever you get the idea).