Results 1 to 2 of 2

Thread: Square root mod p

  1. #1
    Junior Member
    Nov 2008

    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
    Jan 2009

    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: Oct 10th 2011, 04:17 PM
  2. square root + cube root of a number
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Dec 5th 2010, 10:35 AM
  3. Replies: 12
    Last Post: Nov 22nd 2008, 12:41 PM
  4. Simplifying Square Root w/in square root
    Posted in the Algebra Forum
    Replies: 5
    Last Post: Sep 7th 2006, 08:01 AM
  5. Replies: 2
    Last Post: Apr 29th 2006, 01:13 AM

Search Tags

/mathhelpforum @mathhelpforum