def gf_trace_map(a, b, c, n, f, p, K):
 u = gf_compose_mod(a, b, f, p, K)
 v = b
 if (n & 1):
  U = gf_add(a, u, p, K)
  V = b
 else:
  U = a
  V = c
 n >>= 1
 while n:
  u = gf_add(u, gf_compose_mod(u, v, f, p, K), p, K)
  v = gf_compose_mod(v, v, f, p, K)
  if (n & 1):
   U = gf_add(U, gf_compose_mod(u, V, f, p, K), p, K)
   V = gf_compose_mod(v, V, f, p, K)
  n >>= 1
 return (gf_compose_mod(a, V, f, p, K), U)

def gf_trace_map ( a , b , c , n , f , p , K ) : u = gf_compose_mod ( a , b , f , p , K ) v = b if ( n & 1 ) : U = gf_add ( a , u , p , K ) V = b else : U = a V = c n >>= 1 while n : u = gf_add ( u , gf_compose_mod ( u , v , f , p , K ) , p , K ) v = gf_compose_mod ( v , v , f , p , K ) if ( n & 1 ) : U = gf_add ( U , gf_compose_mod ( u , V , f , p , K ) , p , K ) V = gf_compose_mod ( v , V , f , p , K ) n >>= 1 return ( gf_compose_mod ( a , V , f , p , K ) , U )
compute polynomial trace map in gf(p)[x]/(f) .