Results 1 to 13 of 13

Math Help - Solving quadratics (mod p)

  1. #1
    Newbie
    Joined
    Mar 2007
    Posts
    5

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by twells1303 View Post
    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".
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ThePerfectHacker View Post
    However, there is a method to determine whether a quadradic congruence is solvable. It is called "Quadradic Reciprocity".
    you mind showing it to us?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Jhevon View Post
    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.
    Attached Thumbnails Attached Thumbnails Solving quadratics (mod p)-picture27.gif  
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2007
    Posts
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by twells1303 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2007
    Posts
    5

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by twells1303 View Post
    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.)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by twells1303 View Post
    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.
    Attached Thumbnails Attached Thumbnails Solving quadratics (mod p)-picture1.gif  
    Last edited by ThePerfectHacker; March 31st 2007 at 06:13 PM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Mar 2007
    Posts
    5

    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
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by twells1303 View Post
    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 ).
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Mar 2007
    Posts
    5

    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by twells1303 View Post
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quadratics further solving
    Posted in the Algebra Forum
    Replies: 13
    Last Post: November 11th 2010, 08:35 AM
  2. Problem Solving with Quadratics
    Posted in the Algebra Forum
    Replies: 6
    Last Post: September 13th 2009, 08:21 AM
  3. Solving, Algebra, Quadratics
    Posted in the Algebra Forum
    Replies: 6
    Last Post: August 29th 2008, 01:42 AM
  4. Solving quadratics! help please
    Posted in the Algebra Forum
    Replies: 7
    Last Post: April 8th 2008, 05:09 AM
  5. Problem Solving with Quadratics
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: August 2nd 2007, 09:37 AM

Search Tags


/mathhelpforum @mathhelpforum