<s> """<STR_LIT>""" <EOL> from __future__ import print_function , division <EOL> from random import uniform <EOL> from math import ceil as _ceil , sqrt as _sqrt <EOL> from sympy . core . compatibility import SYMPY_INTS , range <EOL> from sympy . core . mul import prod <EOL> from sympy . polys . polyutils import _sort_factors <EOL> from sympy . polys . polyconfig import query <EOL> from sympy . polys . polyerrors import ExactQuotientFailed <EOL> from sympy . ntheory import factorint <EOL> def gf_crt ( U , M , K = None ) : <EOL> """<STR_LIT>""" <EOL> p = prod ( M , start = K . one ) <EOL> v = K . zero <EOL> for u , m in zip ( U , M ) : <EOL> e = p // m <EOL> s , _ , _ = K . gcdex ( e , m ) <EOL> v += e * ( u * s % m ) <EOL> return v % p <EOL> def gf_crt1 ( M , K ) : <EOL> """<STR_LIT>""" <EOL> E , S = [ ] , [ ] <EOL> p = prod ( M , start = K . one ) <EOL> for m in M : <EOL> E . append ( p // m ) <EOL> S . append ( K . gcdex ( E [ - <NUM_LIT:1> ] , m ) [ <NUM_LIT:0> ] % m ) <EOL> return p , E , S <EOL> def gf_crt2 ( U , M , p , E , S , K ) : <EOL> """<STR_LIT>""" <EOL> v = K . zero <EOL> for u , m , e , s in zip ( U , M , E , S ) : <EOL> v += e * ( u * s % m ) <EOL> return v % p <EOL> def gf_int ( a , p ) : <EOL> """<STR_LIT>""" <EOL> if a <= p // <NUM_LIT:2> : <EOL> return a <EOL> else : <EOL> return a - p <EOL> def gf_degree ( f ) : <EOL> """<STR_LIT>""" <EOL> return len ( f ) - <NUM_LIT:1> <EOL> def gf_LC ( f , K ) : <EOL> """<STR_LIT>""" <EOL> if not f : <EOL> return K . zero <EOL> else : <EOL> return f [ <NUM_LIT:0> ] <EOL> def gf_TC ( f , K ) : <EOL> """<STR_LIT>""" <EOL> if not f : <EOL> return K . zero <EOL> else : <EOL> return f [ - <NUM_LIT:1> ] <EOL> def gf_strip ( f ) : <EOL> """<STR_LIT>""" <EOL> if not f or f [ <NUM_LIT:0> ] : <EOL> return f <EOL> k = <NUM_LIT:0> <EOL> for coeff in f : <EOL> if coeff : <EOL> break <EOL> else : <EOL> k += <NUM_LIT:1> <EOL> return f [ k : ] <EOL> def gf_trunc ( f , p ) : <EOL> """<STR_LIT>""" <EOL> return gf_strip ( [ a % p for a in f ] ) <EOL> def gf_normal ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> return gf_trunc ( list ( map ( K , f ) ) , p ) <EOL> def gf_from_dict ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> n , h = max ( f . keys ( ) ) , [ ] <EOL> if isinstance ( n , SYMPY_INTS ) : <EOL> for k in range ( n , - <NUM_LIT:1> , - <NUM_LIT:1> ) : <EOL> h . append ( f . get ( k , K . zero ) % p ) <EOL> else : <EOL> ( n , ) = n <EOL> for k in range ( n , - <NUM_LIT:1> , - <NUM_LIT:1> ) : <EOL> h . append ( f . get ( ( k , ) , K . zero ) % p ) <EOL> return gf_trunc ( h , p ) <EOL> def gf_to_dict ( f , p , symmetric = True ) : <EOL> """<STR_LIT>""" <EOL> n , result = gf_degree ( f ) , { } <EOL> for k in range ( <NUM_LIT:0> , n + <NUM_LIT:1> ) : <EOL> if symmetric : <EOL> a = gf_int ( f [ n - k ] , p ) <EOL> else : <EOL> a = f [ n - k ] <EOL> if a : <EOL> result [ k ] = a <EOL> return result <EOL> def gf_from_int_poly ( f , p ) : <EOL> """<STR_LIT>""" <EOL> return gf_trunc ( f , p ) <EOL> def gf_to_int_poly ( f , p , symmetric = True ) : <EOL> """<STR_LIT>""" <EOL> if symmetric : <EOL> return [ gf_int ( c , p ) for c in f ] <EOL> else : <EOL> return f <EOL> def gf_neg ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> return [ - coeff % p for coeff in f ] <EOL> def gf_add_ground ( f , a , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not f : <EOL> a = a % p <EOL> else : <EOL> a = ( f [ - <NUM_LIT:1> ] + a ) % p <EOL> if len ( f ) > <NUM_LIT:1> : <EOL> return f [ : - <NUM_LIT:1> ] + [ a ] <EOL> if not a : <EOL> return [ ] <EOL> else : <EOL> return [ a ] <EOL> def gf_sub_ground ( f , a , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not f : <EOL> a = - a % p <EOL> else : <EOL> a = ( f [ - <NUM_LIT:1> ] - a ) % p <EOL> if len ( f ) > <NUM_LIT:1> : <EOL> return f [ : - <NUM_LIT:1> ] + [ a ] <EOL> if not a : <EOL> return [ ] <EOL> else : <EOL> return [ a ] <EOL> def gf_mul_ground ( f , a , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not a : <EOL> return [ ] <EOL> else : <EOL> return [ ( a * b ) % p for b in f ] <EOL> def gf_quo_ground ( f , a , p , K ) : <EOL> """<STR_LIT>""" <EOL> return gf_mul_ground ( f , K . invert ( a , p ) , p , K ) <EOL> def gf_add ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not f : <EOL> return g <EOL> if not g : <EOL> return f <EOL> df = gf_degree ( f ) <EOL> dg = gf_degree ( g ) <EOL> if df == dg : <EOL> return gf_strip ( [ ( a + b ) % p for a , b in zip ( f , g ) ] ) <EOL> else : <EOL> k = abs ( df - dg ) <EOL> if df > dg : <EOL> h , f = f [ : k ] , f [ k : ] <EOL> else : <EOL> h , g = g [ : k ] , g [ k : ] <EOL> return h + [ ( a + b ) % p for a , b in zip ( f , g ) ] <EOL> def gf_sub ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not g : <EOL> return f <EOL> if not f : <EOL> return gf_neg ( g , p , K ) <EOL> df = gf_degree ( f ) <EOL> dg = gf_degree ( g ) <EOL> if df == dg : <EOL> return gf_strip ( [ ( a - b ) % p for a , b in zip ( f , g ) ] ) <EOL> else : <EOL> k = abs ( df - dg ) <EOL> if df > dg : <EOL> h , f = f [ : k ] , f [ k : ] <EOL> else : <EOL> h , g = gf_neg ( g [ : k ] , p , K ) , g [ k : ] <EOL> return h + [ ( a - b ) % p for a , b in zip ( f , g ) ] <EOL> def gf_mul ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> df = gf_degree ( f ) <EOL> dg = gf_degree ( g ) <EOL> dh = df + dg <EOL> h = [ <NUM_LIT:0> ] * ( dh + <NUM_LIT:1> ) <EOL> for i in range ( <NUM_LIT:0> , dh + <NUM_LIT:1> ) : <EOL> coeff = K . zero <EOL> for j in range ( max ( <NUM_LIT:0> , i - dg ) , min ( i , df ) + <NUM_LIT:1> ) : <EOL> coeff += f [ j ] * g [ i - j ] <EOL> h [ i ] = coeff % p <EOL> return gf_strip ( h ) <EOL> def gf_sqr ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> df = gf_degree ( f ) <EOL> dh = <NUM_LIT:2> * df <EOL> h = [ <NUM_LIT:0> ] * ( dh + <NUM_LIT:1> ) <EOL> for i in range ( <NUM_LIT:0> , dh + <NUM_LIT:1> ) : <EOL> coeff = K . zero <EOL> jmin = max ( <NUM_LIT:0> , i - df ) <EOL> jmax = min ( i , df ) <EOL> n = jmax - jmin + <NUM_LIT:1> <EOL> jmax = jmin + n // <NUM_LIT:2> - <NUM_LIT:1> <EOL> for j in range ( jmin , jmax + <NUM_LIT:1> ) : <EOL> coeff += f [ j ] * f [ i - j ] <EOL> coeff += coeff <EOL> if n & <NUM_LIT:1> : <EOL> elem = f [ jmax + <NUM_LIT:1> ] <EOL> coeff += elem ** <NUM_LIT:2> <EOL> h [ i ] = coeff % p <EOL> return gf_strip ( h ) <EOL> def gf_add_mul ( f , g , h , p , K ) : <EOL> """<STR_LIT>""" <EOL> return gf_add ( f , gf_mul ( g , h , p , K ) , p , K ) <EOL> def gf_sub_mul ( f , g , h , p , K ) : <EOL> """<STR_LIT>""" <EOL> return gf_sub ( f , gf_mul ( g , h , p , K ) , p , K ) <EOL> def gf_expand ( F , p , K ) : <EOL> """<STR_LIT>""" <EOL> if type ( F ) is tuple : <EOL> lc , F = F <EOL> else : <EOL> lc = K . one <EOL> g = [ lc ] <EOL> for f , k in F : <EOL> f = gf_pow ( f , k , p , K ) <EOL> g = gf_mul ( g , f , p , K ) <EOL> return g <EOL> def gf_div ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> df = gf_degree ( f ) <EOL> dg = gf_degree ( g ) <EOL> if not g : <EOL> raise ZeroDivisionError ( "<STR_LIT>" ) <EOL> elif df < dg : <EOL> return [ ] , f <EOL> inv = K . invert ( g [ <NUM_LIT:0> ] , p ) <EOL> h , dq , dr = list ( f ) , df - dg , dg - <NUM_LIT:1> <EOL> for i in range ( <NUM_LIT:0> , df + <NUM_LIT:1> ) : <EOL> coeff = h [ i ] <EOL> for j in range ( max ( <NUM_LIT:0> , dg - i ) , min ( df - i , dr ) + <NUM_LIT:1> ) : <EOL> coeff -= h [ i + j - dg ] * g [ dg - j ] <EOL> if i <= dq : <EOL> coeff *= inv <EOL> h [ i ] = coeff % p <EOL> return h [ : dq + <NUM_LIT:1> ] , gf_strip ( h [ dq + <NUM_LIT:1> : ] ) <EOL> def gf_rem ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> return gf_div ( f , g , p , K ) [ <NUM_LIT:1> ] <EOL> def gf_quo ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> df = gf_degree ( f ) <EOL> dg = gf_degree ( g ) <EOL> if not g : <EOL> raise ZeroDivisionError ( "<STR_LIT>" ) <EOL> elif df < dg : <EOL> return [ ] <EOL> inv = K . invert ( g [ <NUM_LIT:0> ] , p ) <EOL> h , dq , dr = f [ : ] , df - dg , dg - <NUM_LIT:1> <EOL> for i in range ( <NUM_LIT:0> , dq + <NUM_LIT:1> ) : <EOL> coeff = h [ i ] <EOL> for j in range ( max ( <NUM_LIT:0> , dg - i ) , min ( df - i , dr ) + <NUM_LIT:1> ) : <EOL> coeff -= h [ i + j - dg ] * g [ dg - j ] <EOL> h [ i ] = ( coeff * inv ) % p <EOL> return h [ : dq + <NUM_LIT:1> ] <EOL> def gf_exquo ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> q , r = gf_div ( f , g , p , K ) <EOL> if not r : <EOL> return q <EOL> else : <EOL> raise ExactQuotientFailed ( f , g ) <EOL> def gf_lshift ( f , n , K ) : <EOL> """<STR_LIT>""" <EOL> if not f : <EOL> return f <EOL> else : <EOL> return f + [ K . zero ] * n <EOL> def gf_rshift ( f , n , K ) : <EOL> """<STR_LIT>""" <EOL> if not n : <EOL> return f , [ ] <EOL> else : <EOL> return f [ : - n ] , f [ - n : ] <EOL> def gf_pow ( f , n , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not n : <EOL> return [ K . one ] <EOL> elif n == <NUM_LIT:1> : <EOL> return f <EOL> elif n == <NUM_LIT:2> : <EOL> return gf_sqr ( f , p , K ) <EOL> h = [ K . one ] <EOL> while True : <EOL> if n & <NUM_LIT:1> : <EOL> h = gf_mul ( h , f , p , K ) <EOL> n -= <NUM_LIT:1> <EOL> n >>= <NUM_LIT:1> <EOL> if not n : <EOL> break <EOL> f = gf_sqr ( f , p , K ) <EOL> return h <EOL> def gf_frobenius_monomial_base ( g , p , K ) : <EOL> """<STR_LIT>""" <EOL> n = gf_degree ( g ) <EOL> if n == <NUM_LIT:0> : <EOL> return [ ] <EOL> b = [ <NUM_LIT:0> ] * n <EOL> b [ <NUM_LIT:0> ] = [ <NUM_LIT:1> ] <EOL> if p < n : <EOL> for i in range ( <NUM_LIT:1> , n ) : <EOL> mon = gf_lshift ( b [ i - <NUM_LIT:1> ] , p , K ) <EOL> b [ i ] = gf_rem ( mon , g , p , K ) <EOL> elif n > <NUM_LIT:1> : <EOL> b [ <NUM_LIT:1> ] = gf_pow_mod ( [ K . one , K . zero ] , p , g , p , K ) <EOL> for i in range ( <NUM_LIT:2> , n ) : <EOL> b [ i ] = gf_mul ( b [ i - <NUM_LIT:1> ] , b [ <NUM_LIT:1> ] , p , K ) <EOL> b [ i ] = gf_rem ( b [ i ] , g , p , K ) <EOL> return b <EOL> def gf_frobenius_map ( f , g , b , p , K ) : <EOL> """<STR_LIT>""" <EOL> m = gf_degree ( g ) <EOL> if gf_degree ( f ) >= m : <EOL> f = gf_rem ( f , g , p , K ) <EOL> if not f : <EOL> return [ ] <EOL> n = gf_degree ( f ) <EOL> sf = [ f [ - <NUM_LIT:1> ] ] <EOL> for i in range ( <NUM_LIT:1> , n + <NUM_LIT:1> ) : <EOL> v = gf_mul_ground ( b [ i ] , f [ n - i ] , p , K ) <EOL> sf = gf_add ( sf , v , p , K ) <EOL> return sf <EOL> def _gf_pow_pnm1d2 ( f , n , g , b , p , K ) : <EOL> """<STR_LIT>""" <EOL> f = gf_rem ( f , g , p , K ) <EOL> h = f <EOL> r = f <EOL> for i in range ( <NUM_LIT:1> , n ) : <EOL> h = gf_frobenius_map ( h , g , b , p , K ) <EOL> r = gf_mul ( r , h , p , K ) <EOL> r = gf_rem ( r , g , p , K ) <EOL> res = gf_pow_mod ( r , ( p - <NUM_LIT:1> ) // <NUM_LIT:2> , g , p , K ) <EOL> return res <EOL> def gf_pow_mod ( f , n , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not n : <EOL> return [ K . one ] <EOL> elif n == <NUM_LIT:1> : <EOL> return gf_rem ( f , g , p , K ) <EOL> elif n == <NUM_LIT:2> : <EOL> return gf_rem ( gf_sqr ( f , p , K ) , g , p , K ) <EOL> h = [ K . one ] <EOL> while True : <EOL> if n & <NUM_LIT:1> : <EOL> h = gf_mul ( h , f , p , K ) <EOL> h = gf_rem ( h , g , p , K ) <EOL> n -= <NUM_LIT:1> <EOL> n >>= <NUM_LIT:1> <EOL> if not n : <EOL> break <EOL> f = gf_sqr ( f , p , K ) <EOL> f = gf_rem ( f , g , p , K ) <EOL> return h <EOL> def gf_gcd ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> while g : <EOL> f , g = g , gf_rem ( f , g , p , K ) <EOL> return gf_monic ( f , p , K ) [ <NUM_LIT:1> ] <EOL> def gf_lcm ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not f or not g : <EOL> return [ ] <EOL> h = gf_quo ( gf_mul ( f , g , p , K ) , <EOL> gf_gcd ( f , g , p , K ) , p , K ) <EOL> return gf_monic ( h , p , K ) [ <NUM_LIT:1> ] <EOL> def gf_cofactors ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not f and not g : <EOL> return ( [ ] , [ ] , [ ] ) <EOL> h = gf_gcd ( f , g , p , K ) <EOL> return ( h , gf_quo ( f , h , p , K ) , <EOL> gf_quo ( g , h , p , K ) ) <EOL> def gf_gcdex ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not ( f or g ) : <EOL> return [ K . one ] , [ ] , [ ] <EOL> p0 , r0 = gf_monic ( f , p , K ) <EOL> p1 , r1 = gf_monic ( g , p , K ) <EOL> if not f : <EOL> return [ ] , [ K . invert ( p1 , p ) ] , r1 <EOL> if not g : <EOL> return [ K . invert ( p0 , p ) ] , [ ] , r0 <EOL> s0 , s1 = [ K . invert ( p0 , p ) ] , [ ] <EOL> t0 , t1 = [ ] , [ K . invert ( p1 , p ) ] <EOL> while True : <EOL> Q , R = gf_div ( r0 , r1 , p , K ) <EOL> if not R : <EOL> break <EOL> ( lc , r1 ) , r0 = gf_monic ( R , p , K ) , r1 <EOL> inv = K . invert ( lc , p ) <EOL> s = gf_sub_mul ( s0 , s1 , Q , p , K ) <EOL> t = gf_sub_mul ( t0 , t1 , Q , p , K ) <EOL> s1 , s0 = gf_mul_ground ( s , inv , p , K ) , s1 <EOL> t1 , t0 = gf_mul_ground ( t , inv , p , K ) , t1 <EOL> return s1 , t1 , r1 <EOL> def gf_monic ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not f : <EOL> return K . zero , [ ] <EOL> else : <EOL> lc = f [ <NUM_LIT:0> ] <EOL> if K . is_one ( lc ) : <EOL> return lc , list ( f ) <EOL> else : <EOL> return lc , gf_quo_ground ( f , lc , p , K ) <EOL> def gf_diff ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> df = gf_degree ( f ) <EOL> h , n = [ K . zero ] * df , df <EOL> for coeff in f [ : - <NUM_LIT:1> ] : <EOL> coeff *= K ( n ) <EOL> coeff %= p <EOL> if coeff : <EOL> h [ df - n ] = coeff <EOL> n -= <NUM_LIT:1> <EOL> return gf_strip ( h ) <EOL> def gf_eval ( f , a , p , K ) : <EOL> """<STR_LIT>""" <EOL> result = K . zero <EOL> for c in f : <EOL> result *= a <EOL> result += c <EOL> result %= p <EOL> return result <EOL> def gf_multi_eval ( f , A , p , K ) : <EOL> """<STR_LIT>""" <EOL> return [ gf_eval ( f , a , p , K ) for a in A ] <EOL> def gf_compose ( f , g , p , K ) : <EOL> """<STR_LIT>""" <EOL> if len ( g ) <= <NUM_LIT:1> : <EOL> return gf_strip ( [ gf_eval ( f , gf_LC ( g , K ) , p , K ) ] ) <EOL> if not f : <EOL> return [ ] <EOL> h = [ f [ <NUM_LIT:0> ] ] <EOL> for c in f [ <NUM_LIT:1> : ] : <EOL> h = gf_mul ( h , g , p , K ) <EOL> h = gf_add_ground ( h , c , p , K ) <EOL> return h <EOL> def gf_compose_mod ( g , h , f , p , K ) : <EOL> """<STR_LIT>""" <EOL> if not g : <EOL> return [ ] <EOL> comp = [ g [ <NUM_LIT:0> ] ] <EOL> for a in g [ <NUM_LIT:1> : ] : <EOL> comp = gf_mul ( comp , h , p , K ) <EOL> comp = gf_add_ground ( comp , a , p , K ) <EOL> comp = gf_rem ( comp , f , p , K ) <EOL> return comp <EOL> def gf_trace_map ( a , b , c , n , f , p , K ) : <EOL> """<STR_LIT>""" <EOL> u = gf_compose_mod ( a , b , f , p , K ) <EOL> v = b <EOL> if n & <NUM_LIT:1> : <EOL> U = gf_add ( a , u , p , K ) <EOL> V = b <EOL> else : <EOL> U = a <EOL> V = c <EOL> n >>= <NUM_LIT:1> <EOL> while n : <EOL> u = gf_add ( u , gf_compose_mod ( u , v , f , p , K ) , p , K ) <EOL> v = gf_compose_mod ( v , v , f , p , K ) <EOL> if n & <NUM_LIT:1> : <EOL> U = gf_add ( U , gf_compose_mod ( u , V , f , p , K ) , p , K ) <EOL> V = gf_compose_mod ( v , V , f , p , K ) <EOL> n >>= <NUM_LIT:1> <EOL> return gf_compose_mod ( a , V , f , p , K ) , U <EOL> def _gf_trace_map ( f , n , g , b , p , K ) : <EOL> """<STR_LIT>""" <EOL> f = gf_rem ( f , g , p , K ) <EOL> h = f <EOL> r = f <EOL> for i in range ( <NUM_LIT:1> , n ) : <EOL> h = gf_frobenius_map ( h , g , b , p , K ) <EOL> r = gf_add ( r , h , p , K ) <EOL> r = gf_rem ( r , g , p , K ) <EOL> return r <EOL> def gf_random ( n , p , K ) : <EOL> """<STR_LIT>""" <EOL> return [ K . one ] + [ K ( int ( uniform ( <NUM_LIT:0> , p ) ) ) for i in range ( <NUM_LIT:0> , n ) ] <EOL> def gf_irreducible ( n , p , K ) : <EOL> """<STR_LIT>""" <EOL> while True : <EOL> f = gf_random ( n , p , K ) <EOL> if gf_irreducible_p ( f , p , K ) : <EOL> return f <EOL> def gf_irred_p_ben_or ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> n = gf_degree ( f ) <EOL> if n <= <NUM_LIT:1> : <EOL> return True <EOL> _ , f = gf_monic ( f , p , K ) <EOL> if n < <NUM_LIT:5> : <EOL> H = h = gf_pow_mod ( [ K . one , K . zero ] , p , f , p , K ) <EOL> for i in range ( <NUM_LIT:0> , n // <NUM_LIT:2> ) : <EOL> g = gf_sub ( h , [ K . one , K . zero ] , p , K ) <EOL> if gf_gcd ( f , g , p , K ) == [ K . one ] : <EOL> h = gf_compose_mod ( h , H , f , p , K ) <EOL> else : <EOL> return False <EOL> else : <EOL> b = gf_frobenius_monomial_base ( f , p , K ) <EOL> H = h = gf_frobenius_map ( [ K . one , K . zero ] , f , b , p , K ) <EOL> for i in range ( <NUM_LIT:0> , n // <NUM_LIT:2> ) : <EOL> g = gf_sub ( h , [ K . one , K . zero ] , p , K ) <EOL> if gf_gcd ( f , g , p , K ) == [ K . one ] : <EOL> h = gf_frobenius_map ( h , f , b , p , K ) <EOL> else : <EOL> return False <EOL> return True <EOL> def gf_irred_p_rabin ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> n = gf_degree ( f ) <EOL> if n <= <NUM_LIT:1> : <EOL> return True <EOL> _ , f = gf_monic ( f , p , K ) <EOL> x = [ K . one , K . zero ] <EOL> indices = { n // d for d in factorint ( n ) } <EOL> b = gf_frobenius_monomial_base ( f , p , K ) <EOL> h = b [ <NUM_LIT:1> ] <EOL> for i in range ( <NUM_LIT:1> , n ) : <EOL> if i in indices : <EOL> g = gf_sub ( h , x , p , K ) <EOL> if gf_gcd ( f , g , p , K ) != [ K . one ] : <EOL> return False <EOL> h = gf_frobenius_map ( h , f , b , p , K ) <EOL> return h == x <EOL> _irred_methods = { <EOL> '<STR_LIT>' : gf_irred_p_ben_or , <EOL> '<STR_LIT>' : gf_irred_p_rabin , <EOL> } <EOL> def gf_irreducible_p ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> method = query ( '<STR_LIT>' ) <EOL> if method is not None : <EOL> irred = _irred_methods [ method ] ( f , p , K ) <EOL> else : <EOL> irred = gf_irred_p_rabin ( f , p , K ) <EOL> return irred <EOL> def gf_sqf_p ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> _ , f = gf_monic ( f , p , K ) <EOL> if not f : <EOL> return True <EOL> else : <EOL> return gf_gcd ( f , gf_diff ( f , p , K ) , p , K ) == [ K . one ] <EOL> def gf_sqf_part ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> _ , sqf = gf_sqf_list ( f , p , K ) <EOL> g = [ K . one ] <EOL> for f , _ in sqf : <EOL> g = gf_mul ( g , f , p , K ) <EOL> return g <EOL> def gf_sqf_list ( f , p , K , all = False ) : <EOL> """<STR_LIT>""" <EOL> n , sqf , factors , r = <NUM_LIT:1> , False , [ ] , int ( p ) <EOL> lc , f = gf_monic ( f , p , K ) <EOL> if gf_degree ( f ) < <NUM_LIT:1> : <EOL> return lc , [ ] <EOL> while True : <EOL> F = gf_diff ( f , p , K ) <EOL> if F != [ ] : <EOL> g = gf_gcd ( f , F , p , K ) <EOL> h = gf_quo ( f , g , p , K ) <EOL> i = <NUM_LIT:1> <EOL> while h != [ K . one ] : <EOL> G = gf_gcd ( g , h , p , K ) <EOL> H = gf_quo ( h , G , p , K ) <EOL> if gf_degree ( H ) > <NUM_LIT:0> : <EOL> factors . append ( ( H , i * n ) ) <EOL> g , h , i = gf_quo ( g , G , p , K ) , G , i + <NUM_LIT:1> <EOL> if g == [ K . one ] : <EOL> sqf = True <EOL> else : <EOL> f = g <EOL> if not sqf : <EOL> d = gf_degree ( f ) // r <EOL> for i in range ( <NUM_LIT:0> , d + <NUM_LIT:1> ) : <EOL> f [ i ] = f [ i * r ] <EOL> f , n = f [ : d + <NUM_LIT:1> ] , n * r <EOL> else : <EOL> break <EOL> if all : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> return lc , factors <EOL> def gf_Qmatrix ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> n , r = gf_degree ( f ) , int ( p ) <EOL> q = [ K . one ] + [ K . zero ] * ( n - <NUM_LIT:1> ) <EOL> Q = [ list ( q ) ] + [ [ ] ] * ( n - <NUM_LIT:1> ) <EOL> for i in range ( <NUM_LIT:1> , ( n - <NUM_LIT:1> ) * r + <NUM_LIT:1> ) : <EOL> qq , c = [ ( - q [ - <NUM_LIT:1> ] * f [ - <NUM_LIT:1> ] ) % p ] , q [ - <NUM_LIT:1> ] <EOL> for j in range ( <NUM_LIT:1> , n ) : <EOL> qq . append ( ( q [ j - <NUM_LIT:1> ] - c * f [ - j - <NUM_LIT:1> ] ) % p ) <EOL> if not ( i % r ) : <EOL> Q [ i // r ] = list ( qq ) <EOL> q = qq <EOL> return Q <EOL> def gf_Qbasis ( Q , p , K ) : <EOL> """<STR_LIT>""" <EOL> Q , n = [ list ( q ) for q in Q ] , len ( Q ) <EOL> for k in range ( <NUM_LIT:0> , n ) : <EOL> Q [ k ] [ k ] = ( Q [ k ] [ k ] - K . one ) % p <EOL> for k in range ( <NUM_LIT:0> , n ) : <EOL> for i in range ( k , n ) : <EOL> if Q [ k ] [ i ] : <EOL> break <EOL> else : <EOL> continue <EOL> inv = K . invert ( Q [ k ] [ i ] , p ) <EOL> for j in range ( <NUM_LIT:0> , n ) : <EOL> Q [ j ] [ i ] = ( Q [ j ] [ i ] * inv ) % p <EOL> for j in range ( <NUM_LIT:0> , n ) : <EOL> t = Q [ j ] [ k ] <EOL> Q [ j ] [ k ] = Q [ j ] [ i ] <EOL> Q [ j ] [ i ] = t <EOL> for i in range ( <NUM_LIT:0> , n ) : <EOL> if i != k : <EOL> q = Q [ k ] [ i ] <EOL> for j in range ( <NUM_LIT:0> , n ) : <EOL> Q [ j ] [ i ] = ( Q [ j ] [ i ] - Q [ j ] [ k ] * q ) % p <EOL> for i in range ( <NUM_LIT:0> , n ) : <EOL> for j in range ( <NUM_LIT:0> , n ) : <EOL> if i == j : <EOL> Q [ i ] [ j ] = ( K . one - Q [ i ] [ j ] ) % p <EOL> else : <EOL> Q [ i ] [ j ] = ( - Q [ i ] [ j ] ) % p <EOL> basis = [ ] <EOL> for q in Q : <EOL> if any ( q ) : <EOL> basis . append ( q ) <EOL> return basis <EOL> def gf_berlekamp ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> Q = gf_Qmatrix ( f , p , K ) <EOL> V = gf_Qbasis ( Q , p , K ) <EOL> for i , v in enumerate ( V ) : <EOL> V [ i ] = gf_strip ( list ( reversed ( v ) ) ) <EOL> factors = [ f ] <EOL> for k in range ( <NUM_LIT:1> , len ( V ) ) : <EOL> for f in list ( factors ) : <EOL> s = K . zero <EOL> while s < p : <EOL> g = gf_sub_ground ( V [ k ] , s , p , K ) <EOL> h = gf_gcd ( f , g , p , K ) <EOL> if h != [ K . one ] and h != f : <EOL> factors . remove ( f ) <EOL> f = gf_quo ( f , h , p , K ) <EOL> factors . extend ( [ f , h ] ) <EOL> if len ( factors ) == len ( V ) : <EOL> return _sort_factors ( factors , multiple = False ) <EOL> s += K . one <EOL> return _sort_factors ( factors , multiple = False ) <EOL> def gf_ddf_zassenhaus ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> i , g , factors = <NUM_LIT:1> , [ K . one , K . zero ] , [ ] <EOL> b = gf_frobenius_monomial_base ( f , p , K ) <EOL> while <NUM_LIT:2> * i <= gf_degree ( f ) : <EOL> g = gf_frobenius_map ( g , f , b , p , K ) <EOL> h = gf_gcd ( f , gf_sub ( g , [ K . one , K . zero ] , p , K ) , p , K ) <EOL> if h != [ K . one ] : <EOL> factors . append ( ( h , i ) ) <EOL> f = gf_quo ( f , h , p , K ) <EOL> g = gf_rem ( g , f , p , K ) <EOL> b = gf_frobenius_monomial_base ( f , p , K ) <EOL> i += <NUM_LIT:1> <EOL> if f != [ K . one ] : <EOL> return factors + [ ( f , gf_degree ( f ) ) ] <EOL> else : <EOL> return factors <EOL> def gf_edf_zassenhaus ( f , n , p , K ) : <EOL> """<STR_LIT>""" <EOL> factors , q = [ f ] , int ( p ) <EOL> if gf_degree ( f ) <= n : <EOL> return factors <EOL> N = gf_degree ( f ) // n <EOL> if p != <NUM_LIT:2> : <EOL> b = gf_frobenius_monomial_base ( f , p , K ) <EOL> while len ( factors ) < N : <EOL> r = gf_random ( <NUM_LIT:2> * n - <NUM_LIT:1> , p , K ) <EOL> if p == <NUM_LIT:2> : <EOL> h = r <EOL> for i in range ( <NUM_LIT:0> , <NUM_LIT:2> ** ( n * N - <NUM_LIT:1> ) ) : <EOL> r = gf_pow_mod ( r , <NUM_LIT:2> , f , p , K ) <EOL> h = gf_add ( h , r , p , K ) <EOL> g = gf_gcd ( f , h , p , K ) <EOL> else : <EOL> h = _gf_pow_pnm1d2 ( r , n , f , b , p , K ) <EOL> g = gf_gcd ( f , gf_sub_ground ( h , K . one , p , K ) , p , K ) <EOL> if g != [ K . one ] and g != f : <EOL> factors = gf_edf_zassenhaus ( g , n , p , K ) + gf_edf_zassenhaus ( gf_quo ( f , g , p , K ) , n , p , K ) <EOL> return _sort_factors ( factors , multiple = False ) <EOL> def gf_ddf_shoup ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> n = gf_degree ( f ) <EOL> k = int ( _ceil ( _sqrt ( n // <NUM_LIT:2> ) ) ) <EOL> b = gf_frobenius_monomial_base ( f , p , K ) <EOL> h = gf_frobenius_map ( [ K . one , K . zero ] , f , b , p , K ) <EOL> U = [ [ K . one , K . zero ] , h ] + [ K . zero ] * ( k - <NUM_LIT:1> ) <EOL> for i in range ( <NUM_LIT:2> , k + <NUM_LIT:1> ) : <EOL> U [ i ] = gf_frobenius_map ( U [ i - <NUM_LIT:1> ] , f , b , p , K ) <EOL> h , U = U [ k ] , U [ : k ] <EOL> V = [ h ] + [ K . zero ] * ( k - <NUM_LIT:1> ) <EOL> for i in range ( <NUM_LIT:1> , k ) : <EOL> V [ i ] = gf_compose_mod ( V [ i - <NUM_LIT:1> ] , h , f , p , K ) <EOL> factors = [ ] <EOL> for i , v in enumerate ( V ) : <EOL> h , j = [ K . one ] , k - <NUM_LIT:1> <EOL> for u in U : <EOL> g = gf_sub ( v , u , p , K ) <EOL> h = gf_mul ( h , g , p , K ) <EOL> h = gf_rem ( h , f , p , K ) <EOL> g = gf_gcd ( f , h , p , K ) <EOL> f = gf_quo ( f , g , p , K ) <EOL> for u in reversed ( U ) : <EOL> h = gf_sub ( v , u , p , K ) <EOL> F = gf_gcd ( g , h , p , K ) <EOL> if F != [ K . one ] : <EOL> factors . append ( ( F , k * ( i + <NUM_LIT:1> ) - j ) ) <EOL> g , j = gf_quo ( g , F , p , K ) , j - <NUM_LIT:1> <EOL> if f != [ K . one ] : <EOL> factors . append ( ( f , gf_degree ( f ) ) ) <EOL> return factors <EOL> def gf_edf_shoup ( f , n , p , K ) : <EOL> """<STR_LIT>""" <EOL> N , q = gf_degree ( f ) , int ( p ) <EOL> if not N : <EOL> return [ ] <EOL> if N <= n : <EOL> return [ f ] <EOL> factors , x = [ f ] , [ K . one , K . zero ] <EOL> r = gf_random ( N - <NUM_LIT:1> , p , K ) <EOL> if p == <NUM_LIT:2> : <EOL> h = gf_pow_mod ( x , q , f , p , K ) <EOL> H = gf_trace_map ( r , h , x , n - <NUM_LIT:1> , f , p , K ) [ <NUM_LIT:1> ] <EOL> h1 = gf_gcd ( f , H , p , K ) <EOL> h2 = gf_quo ( f , h1 , p , K ) <EOL> factors = gf_edf_shoup ( h1 , n , p , K ) + gf_edf_shoup ( h2 , n , p , K ) <EOL> else : <EOL> b = gf_frobenius_monomial_base ( f , p , K ) <EOL> H = _gf_trace_map ( r , n , f , b , p , K ) <EOL> h = gf_pow_mod ( H , ( q - <NUM_LIT:1> ) // <NUM_LIT:2> , f , p , K ) <EOL> h1 = gf_gcd ( f , h , p , K ) <EOL> h2 = gf_gcd ( f , gf_sub_ground ( h , K . one , p , K ) , p , K ) <EOL> h3 = gf_quo ( f , gf_mul ( h1 , h2 , p , K ) , p , K ) <EOL> factors = gf_edf_shoup ( h1 , n , p , K ) + gf_edf_shoup ( h2 , n , p , K ) + gf_edf_shoup ( h3 , n , p , K ) <EOL> return _sort_factors ( factors , multiple = False ) <EOL> def gf_zassenhaus ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> factors = [ ] <EOL> for factor , n in gf_ddf_zassenhaus ( f , p , K ) : <EOL> factors += gf_edf_zassenhaus ( factor , n , p , K ) <EOL> return _sort_factors ( factors , multiple = False ) <EOL> def gf_shoup ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> factors = [ ] <EOL> for factor , n in gf_ddf_shoup ( f , p , K ) : <EOL> factors += gf_edf_shoup ( factor , n , p , K ) <EOL> return _sort_factors ( factors , multiple = False ) <EOL> _factor_methods = { <EOL> '<STR_LIT>' : gf_berlekamp , <EOL> '<STR_LIT>' : gf_zassenhaus , <EOL> '<STR_LIT>' : gf_shoup , <EOL> } <EOL> def gf_factor_sqf ( f , p , K , method = None ) : <EOL> """<STR_LIT>""" <EOL> lc , f = gf_monic ( f , p , K ) <EOL> if gf_degree ( f ) < <NUM_LIT:1> : <EOL> return lc , [ ] <EOL> method = method or query ( '<STR_LIT>' ) <EOL> if method is not None : <EOL> factors = _factor_methods [ method ] ( f , p , K ) <EOL> else : <EOL> factors = gf_zassenhaus ( f , p , K ) <EOL> return lc , factors <EOL> def gf_factor ( f , p , K ) : <EOL> """<STR_LIT>""" <EOL> lc , f = gf_monic ( f , p , K ) <EOL> if gf_degree ( f ) < <NUM_LIT:1> : <EOL> return lc , [ ] <EOL> factors = [ ] <EOL> for g , n in gf_sqf_list ( f , p , K ) [ <NUM_LIT:1> ] : <EOL> for h in gf_factor_sqf ( g , p , K ) [ <NUM_LIT:1> ] : <EOL> factors . append ( ( h , n ) ) <EOL> return lc , _sort_factors ( factors ) <EOL> def gf_value ( f , a ) : <EOL> """<STR_LIT>""" <EOL> result = <NUM_LIT:0> <EOL> for c in f : <EOL> result *= a <EOL> result += c <EOL> return result <EOL> def linear_congruence ( a , b , m ) : <EOL> """<STR_LIT>""" <EOL> from sympy . polys . polytools import gcdex <EOL> if a % m == <NUM_LIT:0> : <EOL> if b % m == <NUM_LIT:0> : <EOL> return list ( range ( m ) ) <EOL> else : <EOL> return [ ] <EOL> r , _ , g = gcdex ( a , m ) <EOL> if b % g != <NUM_LIT:0> : <EOL> return [ ] <EOL> return [ ( r * b // g + t * m // g ) % m for t in range ( g ) ] <EOL> def _raise_mod_power ( x , s , p , f ) : <EOL> """<STR_LIT>""" <EOL> from sympy . polys . domains import ZZ <EOL> f_f = gf_diff ( f , p , ZZ ) <EOL> alpha = gf_value ( f_f , x ) <EOL> beta = - gf_value ( f , x ) // p ** s <EOL> return linear_congruence ( alpha , beta , p ) <EOL> def csolve_prime ( f , p , e = <NUM_LIT:1> ) : <EOL> """<STR_LIT>""" <EOL> from sympy . polys . domains import ZZ <EOL> X1 = [ i for i in range ( p ) if gf_eval ( f , i , p , ZZ ) == <NUM_LIT:0> ] <EOL> if e == <NUM_LIT:1> : <EOL> return X1 <EOL> X = [ ] <EOL> S = list ( zip ( X1 , [ <NUM_LIT:1> ] * len ( X1 ) ) ) <EOL> while S : <EOL> x , s = S . pop ( ) <EOL> if s == e : <EOL> X . append ( x ) <EOL> else : <EOL> s1 = s + <NUM_LIT:1> <EOL> ps = p ** s <EOL> S . extend ( [ ( x + v * ps , s1 ) for v in _raise_mod_power ( x , s , p , f ) ] ) <EOL> return sorted ( X ) <EOL> def gf_csolve ( f , n ) : <EOL> """<STR_LIT>""" <EOL> from sympy . polys . domains import ZZ <EOL> P = factorint ( n ) <EOL> X = [ csolve_prime ( f , p , e ) for p , e in P . items ( ) ] <EOL> pools = list ( map ( tuple , X ) ) <EOL> perms = [ [ ] ] <EOL> for pool in pools : <EOL> perms = [ x + [ y ] for x in perms for y in pool ] <EOL> dist_factors = [ pow ( p , e ) for p , e in P . items ( ) ] <EOL> return sorted ( [ gf_crt ( per , dist_factors , ZZ ) for per in perms ] ) </s>
