Find Square Root under Modulo p | Set 2 ( Shanks Tonelli algorithm ) | utility function to find pow ( base , exponent ) % modulus ; utility function to find gcd ; Returns k such that b ^ k = 1 ( mod p ) ; Initializing k with first odd prime number ; function return p - 1 ( = x argument ) as x * 2 ^ e , where x will be odd sending e as reference because updation is needed in actual e ; Main function for finding the modular square root ; a and p should be coprime for finding the modular square root ; If below expression return ( p - 1 ) then modular square root is not possible ; expressing p - 1 , in terms of s * 2 ^ e , where s is odd number ; finding smallest q such that q ^ ( ( p - 1 ) / 2 ) ( mod p ) = p - 1 ; q - 1 is in place of ( - 1 % p ) ; Initializing variable x , b and g ; keep looping until b become 1 or m becomes 0 ; finding m such that b ^ ( 2 ^ m ) = 1 ; updating value of x , g and b according to algorithm ; Driver Code ; p should be prime
< ? php function pow1 ( $ base , $ exponent , $ modulus ) { $ result = 1 ; $ base = $ base % $ modulus ; while ( $ exponent > 0 ) { if ( $ exponent % 2 == 1 ) $ result = ( $ result * $ base ) % $ modulus ; $ exponent = $ exponent >> 1 ; $ base = ( $ base * $ base ) % $ modulus ; } return $ result ; } function gcd ( $ a , $ b ) { if ( $ b == 0 ) return $ a ; else return gcd ( $ b , $ a % $ b ) ; } function order ( $ p , $ b ) { if ( gcd ( $ p , $ b ) != 1 ) { print ( " p ▁ and ▁ b ▁ are ▁ not ▁ co - prime . STRNEWLINE " ) ; return -1 ; } $ k = 3 ; while ( 1 ) { if ( pow1 ( $ b , $ k , $ p ) == 1 ) return $ k ; $ k ++ ; } } function convertx2e ( $ x , & $ e ) { $ e = 0 ; while ( $ x % 2 == 0 ) { $ x = ( int ) ( $ x / 2 ) ; $ e ++ ; } return $ x ; } function STonelli ( $ n , $ p ) { if ( gcd ( $ n , $ p ) != 1 ) { print ( " a ▁ and ▁ p ▁ are ▁ not ▁ coprime STRNEWLINE " ) ; return -1 ; } if ( pow1 ( $ n , ( $ p - 1 ) / 2 , $ p ) == ( $ p - 1 ) ) { printf ( " no ▁ sqrt ▁ possible STRNEWLINE " ) ; return -1 ; } $ e = 0 ; $ s = convertx2e ( $ p - 1 , $ e ) ; $ q = 2 ; for ( ; ; $ q ++ ) { if ( pow1 ( $ q , ( $ p - 1 ) / 2 , $ p ) == ( $ p - 1 ) ) break ; } $ x = pow1 ( $ n , ( $ s + 1 ) / 2 , $ p ) ; $ b = pow1 ( $ n , $ s , $ p ) ; $ g = pow1 ( $ q , $ s , $ p ) ; $ r = $ e ; while ( 1 ) { $ m = 0 ; for ( ; $ m < $ r ; $ m ++ ) { if ( order ( $ p , $ b ) == -1 ) return -1 ; if ( order ( $ p , $ b ) == pow ( 2 , $ m ) ) break ; } if ( $ m == 0 ) return $ x ; $ x = ( $ x * pow1 ( $ g , pow ( 2 , $ r - $ m - 1 ) , $ p ) ) % $ p ; $ g = pow1 ( $ g , pow ( 2 , $ r - $ m ) , $ p ) ; $ b = ( $ b * $ g ) % $ p ; if ( $ b == 1 ) return $ x ; $ r = $ m ; } } $ n = 2 ; $ p = 113 ; $ x = STonelli ( $ n , $ p ) ; if ( $ x == -1 ) print ( " Modular ▁ square ▁ root ▁ is ▁ not ▁ exist STRNEWLINE " ) ; else print ( " Modular ▁ square ▁ root ▁ of ▁ " . " $ n ▁ and ▁ $ p ▁ is ▁ $ x STRNEWLINE " ) ; ? >