/* a tuples of Fq  */

Range(a)={
local(F0,i0,ia0,ia1,RA0,RA1,ra0);
RA0=vector(q,i0,[i0-1]);
for(i0=1,a-1,ra0=length(RA0);
RA1=vector(q*ra0,i0,
ia0=(i0-1) % q;
ia1=(i0-1) \ q;
concat(RA0[1+ia1],ia0)
);
RA0=RA1
);
return(RA0);
}

/* deg <=a polys over Fq  */

PolRange(a)={
local(RA0,RA1,i0);
RA0=Range(a+1);RA1=[];
for(i0=1,length(RA0),
RA1=concat(RA1,Polrev(RA0[i0],t));
);
return(RA1);
}

/* List of deg=a irred poly */


Irred(a)={
local(RA0,RA1);
RA0=Range(a);RA1=[];
for(i=1,q^a,
g=t^a+Mod(Polrev(RA0[i],t),q);
if(polisirreducible(g)==1,RA1=concat(RA1,g))
);
return(RA1);
}

/* Polynomial Legendre Symbol */

LegPol(PA,QA)={
local(cA,iA);
cA=poldegree(QA);
return(lift(Mod(PA,QA)^((q^cA-1)/2)));
}


/* valuation inf=0*/
ValPol(PA,QA)={
local(i0);
i0=0;
if(PA==Mod(0,q),return(0));
while(PA%QA==Mod(0,q),i0=i0+1;PA=PA/QA);
return(i0);
}

/* Label -> Pol */
LabPol(iA)={
return(Mod(Pol(digits(iA,q),'t),q));
}


/* main */


{
/* cases */

q=3;r=3;Y=t;
q=3;r=4;Y=t;
q=3;r=5;Y=t;
q=5;r=3;Y=t;
q=5;r=4;Y=t;
q=7;r=3;Y=t;

q=3;r=3;Y=t;



d=2;

print("(q,r,Y)=("q","r","Y")");


n=(q^2-1)^2;


print("n="n);
m=d*n;

Y=Mod(Y,q);
if(polisirreducible(Y)<>1,print("reducible Y");return);



/*  norm computation    */

L=floor(poldegree(Y)/2);

e=znprimroot(q);

ZZ=[];

for(i=1,q^(L+1)-1,
for(j=0,1,
a=LabPol(i);b=e^j*Y;
g=x^2+a*x+b;
h=lift(Mod(x,g)^m);
Z=Mod(subst(h,x,-a)+subst(h,x,0),q);
ZZ=concat(ZZ,b^m-Z*Y^n+Y^m);
));

RP=[];nZZ=length(ZZ);
for(i=1,q^r-1,
g=Mod(t,q)^r+LabPol(i);
if(polisirreducible(g)<>1,next());
j0=0;
for(k=1,nZZ,
if(ZZ[k]==0,next());
if(Mod(ZZ[k],g)==0,j0=k;break())
);
if(j0==0,RP=concat(RP,g)));


if(RP==[],print(RP);return);;
for(k=1,length(RP),
print(lift(RP[k])));

}