text: Find Square Root under Modulo p | Set 1 ( When p is in form of 4 * i + 3 ) | Utility function to do modular exponentiation . It returns ( x ^ y ) % p . ; let res = 1 ; Initialize result x = x % p ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 ; y = y / 2 ; Returns true if square root of n under modulo p exists Assumption : p is of the form 3 * i + 4 where i >= 1 ; Try " + ( n ^ ( ( p ▁ + ▁ 1 ) / 4 ) ) " ; Try " - ( n ▁ ^ ▁ ( ( p ▁ + ▁ 1 ) / 4 ) ) " ; If none of the above two work , then square root doesn 't exist ; Driver program to test
code: function power ( x , y , p ) { while ( y > 0 ) { if ( y % 2 == 1 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } function squareRoot ( n , p ) { if ( p % 4 != 3 ) { document . write ( " " ) ; return ; } n = n % p ; let x = power ( n , Math . floor ( ( p + 1 ) / 4 ) , p ) ; if ( ( x * x ) % p == n ) { document . write ( " " + x ) ; return ; } x = p - x ; if ( ( x * x ) % p == n ) { document . write ( " " + x ) ; return ; } document . write ( " " ) ; } let p = 7 ; let n = 2 ; squareRoot ( n , p ) ;