def gf_irred_p_rabin(f, p, K):
 n = gf_degree(f)
 if (n <= 1):
  return True
 (_, f) = gf_monic(f, p, K)
 x = [K.one, K.zero]
 indices = {(n // d) for d in factorint(n)}
 b = gf_frobenius_monomial_base(f, p, K)
 h = b[1]
 for i in range(1, n):
  if (i in indices):
   g = gf_sub(h, x, p, K)
   if (gf_gcd(f, g, p, K) != [K.one]):
    return False
  h = gf_frobenius_map(h, f, b, p, K)
 return (h == x)

def gf_irred_p_rabin ( f , p , K ) : n = gf_degree ( f ) if ( n <= 1 ) : return True ( _ , f ) = gf_monic ( f , p , K ) x = [ K . one , K . zero ] indices = { ( n // d ) for d in factorint ( n ) } b = gf_frobenius_monomial_base ( f , p , K ) h = b [ 1 ] for i in range ( 1 , n ) : if ( i in indices ) : g = gf_sub ( h , x , p , K ) if ( gf_gcd ( f , g , p , K ) != [ K . one ] ) : return False h = gf_frobenius_map ( h , f , b , p , K ) return ( h == x )
rabins polynomial irreducibility test over finite fields .