global(p,d,w,l,X,D1,D2,F,m,r,s,aa,bb,F0aa,fbra,fdec,mdec,mbra); \\ global variables
allocatemem(100 000 000);

rpol(ld=0,md=1000,var=t) = { \\generates random element in F_p[var], with degree in the range (ld,md)
	local(n,res);
	if (md>ld,n = random(md-ld)+ld,n = md);
	res = Mod(random(p),p);
	for (i=0,n-2,res = res*var + Mod(random(p),p));
	return(res+var^n*(Mod(random(p-1)+1,p)));
}

getMaxPol(mat) = {
	local(count,degree);
	degree = -1;

	for(i=1,matsize(mat)[1],if(poldegree(mat[i,1])>degree,count=i;degree=poldegree(mat[i,1])));
	return(mat[count,1]);
}

printtime(str="Operation performed in",niceoutput=1) = {
	local(gt);
	gt = gettime();
	if (niceoutput,print(str,": ",gt\60000," min ",(gt%60000)\1000," sec ",gt%1000," ms"),print(str,": ",gt));
	return(gt);
}

gsubst(G,x,y,z1,z2) = subst(subst(G,x,z1),y,z2); \\substitutes x=z1 and x=z2 in X(x,y,...)

\\---------------------------------------------------------------------------
keygen(pp=2) = { \\returns nothing

local(lx,ly,vx,vy,ux,uy,c10);

p = pp; \\ p is the characteristic of the prime field F_p, 2 by default
d = 50; \\ maximal degree of the section elements
w = 0; \\ degree of X(x,y,t) in xy
while(w%p==0,w=5+random(3));
l;      \\ minimum degree of f(t)
dt = d*w; \\ max degree in t of the coefficients of X(x,y,t)

\\generate the sections
lx = rpol(2,d,t);
ly = rpol(1,d+1-poldegree(lx,t))*lx;

vy = rpol(0,poldegree(ly,t),t); uy = vy + ly;
vx = rpol(2,d+1,t); ux = lx + vx;
D1 = Mod(1,p)*([ux,uy,t]);
D2 = Mod(1,p)*([vx,vy,t]);

 \\generate X(x,y,t);
X = sum(  j=1,w,y^j*( sum(i=0,w-j, x^i*rpol(0,dt)) )  ) + sum( i=2,w,x^i*rpol(0,dt));
c10 = (-gsubst(X,x,y,ux,uy)+gsubst(X,x,y,vx,vy))/(ux-vx);
X = X + c10*x;
X = X - gsubst(X,x,y,ux,uy);

l = max(poldegree(X,t),(2*w+4)*d)+random(100); \\to do: choose l better
printtime("Keys generated in");

} \\end keygen()

\\--------------------------------------------------------------------
encrypt({mm=0}) = { \\returns the encrypted message

local(degx,degy,maxdegt,xy);
if(mm,m = mm,m = rpol(l-1,l,t));  \\random message, if not specified

gettime(); \\resets the time

\\generate s(x,y,t)
xy = 2*w+2 + random(l\d-2*w-2-1);
degx = 1+w+random(xy-2*w-1);
degy = xy-degx;
maxdegt = l-xy*d;
s = sum(  i=0,degx,x^i*( sum(j=0,degy, y^j*rpol(0,maxdegt,t)) )  );

\\generate r(x,y,t)
degx = 2+random(l\d);  \\these two can vary more
degy = 2+random(l\d);
r = sum(  i=0,degx,x^i*( sum(j=0,degy, y^j*rpol(0,l,t)) )  );

\\generate f(t)
f = subst(ffinit(p,l+random(l)),x,t);

\\cipher polynomial F(t,x,y)
F = m+f*s+X*r;

return(printtime("Message encrypted in"));
} \\end encrypt()

\\------------------------------------------------------------------
decrypt() = {  \\returns the decrypted message

local(h1,h2);

gettime(); \\resets the time

h1 = gsubst(F,x,y,D1[1],D1[2]);
h2 = gsubst(F,x,y,D2[1],D2[2]);

fdec = getMaxPol(factor(h1-h2));

mdec = h1%fdec;

if(mdec==m,
return(printtime("Message decrypted in")) ,
return(printtime("!!Mistake in the decryption!!"));
);

} \\end decrypt()

\\------------------------------------------------------------------
attack() = { \\returns the revealed message

\\local(dd, ff, loc,loc1, trbbF, trbb1F);

gettime(); \\resets the time

\\X0aa is X(aa,0)
X0aa = subst(X,y,0);

\\ aa is the image of x in S = F_p[t][x]/(X(t,x,0))
aa = Mod(Mod(1,p)*x,X0aa);

\\ F0aa is F(aa,0)
F0aa = Mod(subst(F,y,0),X0aa);

dd=poldegree(X0aa,x); \\dd = trace(1);

\\ bb and bb1  are elements of S of trace 0 over F_p[t]
loc=0; loc1=0;
for(i=1,20,bb=aa^i-trace(aa^i)/dd; trbbF=trace(bb*F0aa);if(trbbF!=0,loc=i;break) );
for(i=loc+1,loc+21,bb1=aa^i-trace(aa^i)/dd; trbb1F=trace(bb1*F0aa);if(trbb1F!=0,loc1=i;break) );

if(loc==0, print("Attack fails"); break,

\\ find f

if(loc1!=0,ff = gcd(trbb1F,trbbF),ff = trbbF);
fbra = getMaxPol(factor(ff));

\\find m
mbra = (trace(F0aa)%fbra)/dd;

if(mbra==m,
return(printtime("Message revealed in")),
return(printtime("!!Mistake in the revealing!!"));
)

);
} \\end attack()