Thread: 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?

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

However, there is a method to determine whether a quadradic congruence is solvable. It is called "Quadradic Reciprocity".

Originally Posted by ThePerfectHacker

However, there is a method to determine whether a quadradic congruence is solvable. It is called "Quadradic Reciprocity".

you mind showing it to us?

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.

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.

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?

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.

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.

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

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.

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

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

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.

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