• Mar 29th 2007, 04:06 PM
twells1303
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?
• Mar 29th 2007, 06:06 PM
ThePerfectHacker
Quote:

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

• Mar 29th 2007, 06:48 PM
Jhevon
Quote:

Originally Posted by ThePerfectHacker

you mind showing it to us?
• Mar 29th 2007, 07:08 PM
ThePerfectHacker
Quote:

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.
• Mar 30th 2007, 05:20 AM
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?
• Mar 30th 2007, 07:55 AM
ThePerfectHacker
Quote:

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.
• Mar 30th 2007, 06:14 PM
twells1303
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.
• Mar 31st 2007, 08:01 AM
ecMathGeek
Quote:

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.)
• Mar 31st 2007, 04:40 PM
ThePerfectHacker
Quote:

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.
• Apr 7th 2007, 05:50 PM
twells1303
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
• Apr 7th 2007, 06:11 PM
ThePerfectHacker
Quote:

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.

Quote:

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 :cool: ).
• Apr 14th 2007, 02:28 PM
twells1303
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.
• Apr 14th 2007, 05:13 PM
ThePerfectHacker
Quote:

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