Help:=proc(): print(`LM(p,x), Red(p,q,x), GB1(p,q,x),`):
print(` Ra(K,x,d)`): end:

LM:=proc(p,x): coeff(p,x,degree(p,x))*x^degree(p,x):end:

Red:=proc(p,q,x) local fp,qp,h:
fp:=LM(p,x): qp:=LM(q,x):
h:=normal(fp/qp):
if degree(h,x)<0 then
 RETURN(Red(q,p,x)):
else
 RETURN(expand(p-h*q),q):
fi:
end:

GB1:=proc(p,q,x) :
if p=0 then
 RETURN(normal(q/coeff(q,x,degree(q,x)))):
elif q=0 then
  RETURN(normal(p/coeff(p,x,degree(p,x)))):
else
 GB1(Red(p,q,x),x):
fi:
end:

#Ra(K,x,d): a random polynomial of degree d
#in x with integer coeffs. in the range [-K,K]
Ra:=proc(K,x,d) local i,ra:
ra:=rand(-K..K):
add(ra()*x^i,i=0..d):
end:

Test:=proc(K,d) local x,P,Q:
P:=Ra(K,x,d): Q:=Ra(K,x,d):
 evalb(GB1(P,Q,x)=gcd(P,Q)):
end: