def _euclidean_algorithm(f, g, minpoly, p):
 ring = f.ring
 f = _trunc(f, minpoly, p)
 g = _trunc(g, minpoly, p)
 while g:
  rem = f
  deg = g.degree(0)
  (lcinv, _, gcd) = _gf_gcdex(ring.dmp_LC(g), minpoly, p)
  if (not (gcd == 1)):
   return None
  while True:
   degrem = rem.degree(0)
   if (degrem < deg):
    break
   quo = (lcinv * ring.dmp_LC(rem)).set_ring(ring)
   rem = _trunc((rem - (g.mul_monom(((degrem - deg), 0)) * quo)), minpoly, p)
  f = g
  g = rem
 lcfinv = _gf_gcdex(ring.dmp_LC(f), minpoly, p)[0].set_ring(ring)
 return _trunc((f * lcfinv), minpoly, p)

def _euclidean_algorithm ( f , g , minpoly , p ) : ring = f . ring f = _trunc ( f , minpoly , p ) g = _trunc ( g , minpoly , p ) while g : rem = f deg = g . degree ( 0 ) ( lcinv , _ , gcd ) = _gf_gcdex ( ring . dmp_LC ( g ) , minpoly , p ) if ( not ( gcd == 1 ) ) : return None while True : degrem = rem . degree ( 0 ) if ( degrem < deg ) : break quo = ( lcinv * ring . dmp_LC ( rem ) ) . set_ring ( ring ) rem = _trunc ( ( rem - ( g . mul_monom ( ( ( degrem - deg ) , 0 ) ) * quo ) ) , minpoly , p ) f = g g = rem lcfinv = _gf_gcdex ( ring . dmp_LC ( f ) , minpoly , p ) [ 0 ] . set_ring ( ring ) return _trunc ( ( f * lcfinv ) , minpoly , p )
compute the monic gcd of two univariate polynomials in mathbb{z}_p[z]/(check m_{alpha}(z))[x] with the euclidean algorithm .