<s> try : <EOL> from . native . library import NATIVE_LIBRARY <EOL> except ImportError : <EOL> NATIVE_LIBRARY = None <EOL> def inverse_mod ( a , m ) : <EOL> """<STR_LIT>""" <EOL> if a < <NUM_LIT:0> or m <= a : a = a % m <EOL> c , d = a , m <EOL> uc , vc , ud , vd = <NUM_LIT:1> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:1> <EOL> while c != <NUM_LIT:0> : <EOL> q , c , d = divmod ( d , c ) + ( c , ) <EOL> uc , vc , ud , vd = ud - q * uc , vd - q * vc , uc , vc <EOL> assert d == <NUM_LIT:1> <EOL> if ud > <NUM_LIT:0> : return ud <EOL> else : return ud + m <EOL> if NATIVE_LIBRARY : <EOL> inverse_mod = NATIVE_LIBRARY . inverse_mod <EOL> def modular_sqrt ( a , p ) : <EOL> """<STR_LIT>""" <EOL> if legendre_symbol ( a , p ) != <NUM_LIT:1> : <EOL> return <NUM_LIT:0> <EOL> elif a == <NUM_LIT:0> : <EOL> return <NUM_LIT:0> <EOL> elif p == <NUM_LIT:2> : <EOL> return a <EOL> elif p % <NUM_LIT:4> == <NUM_LIT:3> : <EOL> return pow ( a , ( p + <NUM_LIT:1> ) // <NUM_LIT:4> , p ) <EOL> s = p - <NUM_LIT:1> <EOL> e = <NUM_LIT:0> <EOL> while s % <NUM_LIT:2> == <NUM_LIT:0> : <EOL> s /= <NUM_LIT:2> <EOL> e += <NUM_LIT:1> <EOL> n = <NUM_LIT:2> <EOL> while legendre_symbol ( n , p ) != - <NUM_LIT:1> : <EOL> n += <NUM_LIT:1> <EOL> x = pow ( a , ( s + <NUM_LIT:1> ) // <NUM_LIT:2> , p ) <EOL> b = pow ( a , s , p ) <EOL> g = pow ( n , s , p ) <EOL> r = e <EOL> while True : <EOL> t = b <EOL> m = <NUM_LIT:0> <EOL> for m in xrange ( r ) : <EOL> if t == <NUM_LIT:1> : <EOL> break <EOL> t = pow ( t , <NUM_LIT:2> , p ) <EOL> if m == <NUM_LIT:0> : <EOL> return x <EOL> gs = pow ( g , <NUM_LIT:1> << ( r - m - <NUM_LIT:1> ) , p ) <EOL> g = ( gs * gs ) % p <EOL> x = ( x * gs ) % p <EOL> b = ( b * g ) % p <EOL> r = m <EOL> def legendre_symbol ( a , p ) : <EOL> """<STR_LIT>""" <EOL> ls = pow ( a , ( p - <NUM_LIT:1> ) // <NUM_LIT:2> , p ) <EOL> return - <NUM_LIT:1> if ls == p - <NUM_LIT:1> else ls </s>
