Results 1 to 4 of 4

Math Help - Square root modulo a prime

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    25

    Square root modulo a prime

    Hello

    I hope someone can help me with this.

    I have the following equation -

    y^2 mod 269 = x^3 + 3*x + 5 mod 269

    Let's say x is 64.

    So -

    y^2 mod 269 = 64^3 + 3*64 + 5 mod 269
    y^2 mod 269 = 262144 + 192 + 5 mod 269
    y^2 mod 269 = 262341 mod 269
    y^2 mod 269 = 66

    Now, I happen to know off hand that y is 55, but if I didn't know this, how would I calculate y?

    I've been told it's as simple as "square root modulo a prime", but I cannot figure out how to do this.

    Can someone please explain this to me in simple steps?

    Any help appreciated.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hi,

    While looking for an answer to your question, I found this link : Square roots

    I'm still reading it, but it looks quite interesting with an overall view...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2008
    Posts
    25
    Thanks for the reply. I'm reading that now. Seems complicated!

    Do you understand it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    There is a way to determine if a number is a square root mod a prime.
    That is part of the law of quadradic reciprocity.
    But as far as actually find that square, I do not think there are known methods, only algorithms.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Square root inside square root equation
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 10th 2011, 05:17 PM
  2. Computing square roots modulo prime powers
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 3rd 2011, 08:50 PM
  3. Square Root Modulo Composite
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 2nd 2010, 04:59 PM
  4. square modulo the prime...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 12th 2010, 08:10 AM
  5. Replies: 12
    Last Post: November 22nd 2008, 01:41 PM

Search Tags


/mathhelpforum @mathhelpforum