Find Square Root under Modulo p | Set 2 ( Shanks Tonelli algorithm ) | JavaScript program to implement Shanks Tonelli algorithm for finding Modular Square Roots ; 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
let z = 0 ; function pow1 ( base1 , exponent , modulus ) { let result = 1 ; base1 = base1 % modulus ; while ( exponent > 0 ) { if ( exponent % 2 == 1 ) result = ( result * base1 ) % modulus ; exponent = exponent >> 1 ; base1 = ( base1 * base1 ) % 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 ) { document . write ( " " + " " + " " ) ; return - 1 ; } let k = 3 ; while ( true ) { if ( pow1 ( b , k , p ) == 1 ) return k ; k ++ ; } } function convertx2e ( x ) { z = 0 ; while ( x % 2 == 0 ) { x /= 2 ; z ++ ; } return x ; } function STonelli ( n , p ) { if ( gcd ( n , p ) != 1 ) { System . out . prletln ( " " ) ; return - 1 ; } if ( pow1 ( n , ( p - 1 ) / 2 , p ) == ( p - 1 ) ) { document . write ( " " + " " ) ; return - 1 ; } let s , e ; s = convertx2e ( p - 1 ) ; e = z ; let q ; for ( q = 2 ; ; q ++ ) { if ( pow1 ( q , ( p - 1 ) / 2 , p ) == ( p - 1 ) ) break ; } let x = pow1 ( n , ( s + 1 ) / 2 , p ) ; let b = pow1 ( n , s , p ) ; let g = pow1 ( q , s , p ) ; let r = e ; while ( true ) { let m ; for ( m = 0 ; m < r ; m ++ ) { if ( order ( p , b ) == - 1 ) return - 1 ; if ( order ( p , b ) == Math . pow ( 2 , m ) ) break ; } if ( m == 0 ) return x ; x = ( x * pow1 ( g , Math . pow ( 2 , r - m - 1 ) , p ) ) % p ; g = pow1 ( g , Math . pow ( 2 , r - m ) , p ) ; b = ( b * g ) % p ; if ( b == 1 ) return x ; r = m ; } } let n = 2 ; let p = 113 ; let x = STonelli ( n , p ) ; if ( x == - 1 ) document . write ( " " + " " ) ; else document . write ( " " + n + " " + p + " " + x + " " ) ;