Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Hi there,
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest

Square root modulo a prime

  • 16-06-2008 6:43pm
    #1
    AARRRGH
    Closed Accounts Posts: 12,382 ✭✭✭✭


    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!


Comments

  • #2
    LeixlipRed
    Closed Accounts Posts: 6,081 ✭✭✭LeixlipRed


    Try googling quadratic residues.


  • #3
    hivizman
    Registered Users, Registered Users 2 Posts: 1,163 ✭✭✭hivizman


    If a is a solution to y^2=x mod p, then so is (p-a). So as well as 55, a solution to the equation y^2=66 mod 269 is 214 (214^2 = 45796 = 269*70 + 66).

    In general, there isn't a closed form formula to calculate a square root modulo a prime, but there are some special cases. Fortunately, the prime number 269 fits into one of these cases: p = 8*k+5. For p=269, k=33. To calculate the square root of q mod 269, check whether q^(2*k+1) = 1 mod 269. I used Excel for this, and confirmed that 66^67=1 mod 269. When this holds, a square root of q mod p is q^(k+1). 66^34 mod 269 is 214. The other square root is thus 269-214 = 55.

    This all comes from http://mathworld.wolfram.com/QuadraticResidue.html, which is the first item that comes up if you Google "quadratic residue".


  • #4
    idunnoutellme
    Closed Accounts Posts: 390 ✭✭idunnoutellme


    you find it using the discreet logarithm problem methinks. thats taking logs across so that you can bring the powers down and then its calculated mod p-1


  • #5
    hivizman
    Registered Users, Registered Users 2 Posts: 1,163 ✭✭✭hivizman


    Yes, it's a special case of the discrete logarithm problem. This is the problem of finding x, given g and h, such that g^x = h mod p. The method I used for the square root problem was to find k such that h^(2k+1) = 1 mod p. Then it follows that h^(2k+2) = h mod p (multiplying both sides by h). But h^(2k+2)=(h^(k+1))^2, so h^(k+1) is the square root of h mod p. This only works, though, if p can be expressed in the form 8k+5, which it can for p=269.

    However, I don't think that there's a general solution for the discrete logarithm problem, so it has to be solved algorithmically in most cases.


Advertisement