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 . ; Initialize result ; 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 / 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 Code
< ? php function power ( $ x , $ y , $ p ) { $ res = 1 ; $ x = $ x % $ p ; while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ p ; $ y = $ y >> 1 ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } function squareRoot ( $ n , $ p ) { if ( $ p % 4 != 3 ) { echo " Invalid ▁ Input " ; return ; } $ n = $ n % $ p ; $ x = power ( $ n , ( $ p + 1 ) / 4 , $ p ) ; if ( ( $ x * $ x ) % $ p == $ n ) { echo " Square ▁ root ▁ is ▁ " , $ x ; return ; } $ x = $ p - $ x ; if ( ( $ x * $ x ) % $ p == $ n ) { echo " Square ▁ root ▁ is ▁ " , $ x ; return ; } echo " Square ▁ root ▁ doesn ' t ▁ exist ▁ " ; } $ p = 7 ; $ n = 2 ; squareRoot ( $ n , $ p ) ; ? >