Results 1 to 2 of 2

Math Help - Square root mod p

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    55

    Square root mod p

    I need an efficient way to calculate the square root of a large number modulo a huge prime p, i.e. a way to calculate x^2 = q mod p, where q and p are given. q is in my case 13 digits and p 16 digits, which makes it practically impossible to bruteforce (in reasonable time).

    I can't find anything helpful anywhere except tests whether it is a quadratic residue or not, and special cases... The tests seem to take as long as simply trying to bruteforce by testing if q, q+p, q+2p, q+3p, ..., are square roots. And my prime isn't on the form 4k+3 nor 8k+5 (which allegedly would mean that calculating the square root would be easy).

    I would be very grateful for any help at all.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Shanks-Tonnelli

    Use internet and search for the algorithm. It is the most efficient as far and I know. There are several several variations.
    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. square root + cube root of a number
    Posted in the Algebra Forum
    Replies: 2
    Last Post: December 5th 2010, 11:35 AM
  3. Replies: 12
    Last Post: November 22nd 2008, 01:41 PM
  4. Simplifying Square Root w/in square root
    Posted in the Algebra Forum
    Replies: 5
    Last Post: September 7th 2006, 09:01 AM
  5. Replies: 2
    Last Post: April 29th 2006, 02:13 AM

Search Tags


/mathhelpforum @mathhelpforum