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
def pow1 ( base , exponent , modulus ) : NEW_LINE INDENT result = 1 ; NEW_LINE base = base % modulus ; NEW_LINE while ( exponent > 0 ) : NEW_LINE INDENT if ( exponent % 2 == 1 ) : NEW_LINE INDENT result = ( result * base ) % modulus ; NEW_LINE DEDENT exponent = int ( exponent ) >> 1 ; NEW_LINE base = ( base * base ) % modulus ; NEW_LINE DEDENT return result ; NEW_LINE DEDENT def gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a ; NEW_LINE DEDENT else : NEW_LINE INDENT return gcd ( b , a % b ) ; NEW_LINE DEDENT DEDENT def order ( p , b ) : NEW_LINE INDENT if ( gcd ( p , b ) != 1 ) : NEW_LINE INDENT print ( " p and b are not co - prime . " ) ; NEW_LINE return - 1 ; NEW_LINE DEDENT k = 3 ; NEW_LINE while ( True ) : NEW_LINE INDENT if ( pow1 ( b , k , p ) == 1 ) : NEW_LINE INDENT return k ; NEW_LINE DEDENT k += 1 ; NEW_LINE DEDENT DEDENT def convertx2e ( x ) : NEW_LINE INDENT z = 0 ; NEW_LINE while ( x % 2 == 0 ) : NEW_LINE INDENT x = x / 2 ; NEW_LINE z += 1 ; NEW_LINE DEDENT return [ x , z ] ; NEW_LINE DEDENT def STonelli ( n , p ) : NEW_LINE INDENT if ( gcd ( n , p ) != 1 ) : NEW_LINE INDENT print ( " a and p are not coprime " ) ; NEW_LINE return - 1 ; NEW_LINE DEDENT if ( pow1 ( n , ( p - 1 ) / 2 , p ) == ( p - 1 ) ) : NEW_LINE INDENT print ( " no sqrt possible " ) ; NEW_LINE return - 1 ; NEW_LINE DEDENT ar = convertx2e ( p - 1 ) ; NEW_LINE s = ar [ 0 ] ; NEW_LINE e = ar [ 1 ] ; NEW_LINE q = 2 ; NEW_LINE while ( True ) : NEW_LINE INDENT if ( pow1 ( q , ( p - 1 ) / 2 , p ) == ( p - 1 ) ) : NEW_LINE INDENT break ; NEW_LINE DEDENT q += 1 ; NEW_LINE DEDENT x = pow1 ( n , ( s + 1 ) / 2 , p ) ; NEW_LINE b = pow1 ( n , s , p ) ; NEW_LINE g = pow1 ( q , s , p ) ; NEW_LINE r = e ; NEW_LINE while ( True ) : NEW_LINE INDENT m = 0 ; NEW_LINE while ( m < r ) : NEW_LINE INDENT if ( order ( p , b ) == - 1 ) : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT if ( order ( p , b ) == pow ( 2 , m ) ) : NEW_LINE INDENT break ; NEW_LINE DEDENT m += 1 ; NEW_LINE DEDENT if ( m == 0 ) : NEW_LINE INDENT return x ; NEW_LINE DEDENT x = ( x * pow1 ( g , pow ( 2 , r - m - 1 ) , p ) ) % p ; NEW_LINE g = pow1 ( g , pow ( 2 , r - m ) , p ) ; NEW_LINE b = ( b * g ) % p ; NEW_LINE if ( b == 1 ) : NEW_LINE INDENT return x ; NEW_LINE DEDENT r = m ; NEW_LINE DEDENT DEDENT n = 2 ; NEW_LINE p = 113 ; NEW_LINE x = STonelli ( n , p ) ; NEW_LINE if ( x == - 1 ) : NEW_LINE INDENT print ( " Modular square root is not exist " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Modular ▁ square ▁ root ▁ of " , n , " and " , p , " is " , x ) ; NEW_LINE DEDENT