text: Find Square Root under Modulo p | Set 1 ( When p is in form of 4 * i + 3 ) | An efficient C ++ program to find square root under modulo p when p is 7 , 11 , 19 , 23 , 31 , ... etc . ; Utility function to do modular exponentiation . It returns ( x ^ y ) % p . ; int 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: #include <iostream> NEW_LINE using namespace std ; int power ( int x , int y , int p ) { while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } void squareRoot ( int n , int p ) { if ( p % 4 != 3 ) { cout << " Invalid ▁ Input " ; return ; } n = n % p ; int x = power ( n , ( p + 1 ) / 4 , p ) ; if ( ( x * x ) % p == n ) { cout << " Square ▁ root ▁ is ▁ " << x ; return ; } x = p - x ; if ( ( x * x ) % p == n ) { cout << " Square ▁ root ▁ is ▁ " << x ; return ; } cout << " Square ▁ root ▁ doesn ' t ▁ exist ▁ " ; } int main ( ) { int p = 7 ; int n = 2 ; squareRoot ( n , p ) ; return 0 ; }