Qx := PolyAlg(Q,"X");



### Polynom S ist von der Form S=[ [S_(N-1),...,S_0], N,q]

FillPolyList := function(S)
   return( [ Concatenation(List([1..S[2]-Length(S[1])], i-> 0),S[1]), S[2], S[3]]);
end;


qPolyAdd := function(S,T)

   return( FillPolyList([PolyToList(((Poly(Zx,S[1])+Poly(Zx,T[1])) mod (x^S[2]-1)) mod S[3]),S[2],S[3]]));

end;


qPolyMult := function(S,T)

   return(FillPolyList([ PolyToList(( (Poly(Zx,S[1])*Poly(Zx,T[1])) mod (x^S[2]-1) ) mod S[3]) , S[2], S[3]]));

end;


qMultMat := function(S)

   local N,MON,f,MONIm,M;

      N    := S[2];
      MON  := List([0..N-1], i-> x^i);
      f    := Poly(Zx,S[1]);
      MONIm:= List(List(MON, i-> (((i*f) mod (x^S[2]-1)) mod S[3])), j-> Reversed(Concatenation(List([1..N-Length(PolyToList(j))], k-> 0),PolyToList(j))));

      M    := MatTrans(Mat(MONIm));
      
      return(M);
end;


qInv := function(S)       

   local A,dA,dAInv,AInv,l;

      if IntGcd(Eval(Poly(Zx,S[1]),1),S[3])=1 then
         A := qMultMat(S);
         dA:= MatDet(A);
         if IntGcd(dA,S[3])=1 then
            dAInv := IntXGcd(dA,S[3])[2][1];
            AInv  := MatInv(A)*MatDet(A)*dAInv;
            AInv  := Mat(List(MatToRowList(AInv), i-> List(i, j-> j mod S[3])) );
            l     := MatToColList(AInv)[1];
            return([ Reversed(l), S[2],S[3]]);
         fi;
      fi;
      return(false);

end; 
        

qInv2 := function(S)

   local RP,H;


      RP := PolyMove(x^S[2]-1,Qx);
      H := PolyXGcd( Poly(Qx,S[1]), RP)[2] mod RP;
      if ForAll(PolyToList(H), i-> IntGcd(Den(i),S[3])=1) then 
         H := Poly(Zx, List(PolyToList(H), i-> (i*Den(i)*IntXGcd(Den(i),S[3])[2][1]) mod S[3]));
         return([ PolyToList(H), S[2], S[3]]);
      fi;

      return(false);


end;


qHom := function(S)

  return(Eval(Poly(Zx, S[1]),1) mod S[3]);

end;


CreateRandomElement := function(N)

   local L,xx; 

      L := List([1..N], i-> IntRandomBits(i) mod 3);
      for xx in [1..Length(L)] do
         if L[xx]=2 then 
            L[xx] := -1;
         fi;
      od;
      return(L);

end;


CreateNTRUKeysD := function(N,p,q)    # q > p

   local g,f;
 
      g := CreateRandomElement(N);
      while Length(Filtered(g, i-> i=1)) <> Length(Filtered(g, i-> i=-1)) do
         g := CreateRandomElement(N);
      od;
      f := CreateRandomElement(N);
      while qInv2([f,N,p])=false and qInv2([f,N,q])=false or (Length(Filtered(f, i-> i=1))-1) <> Length(Filtered(f, i-> i=-1)) do
         f := CreateRandomElement(N);
      od;

   return([f,g]);

end;


CreateNTRUKeys := function(N,p,q)    # q > p

   local g,f;
 
      g := CreateRandomElement(N);
     
      f := CreateRandomElement(N);
      while qInv2([f,N,p])=false and qInv2([f,N,q])=false  do
         f := CreateRandomElement(N);
      od;

   return([f,g]);
end;


NTRUPublicKey := function(KEYS,N,q)

      return(qPolyMult([KEYS[1],N,q],[KEYS[2],N,q])[1]);
end;



SP := function(a,b)

   local m;

      m := Mat(a)*MatTrans(Mat(b));
      m := m[1][1];
      return(Re(m));
end;



CreateNTRULattice := function(h,alpha,q)    ### q > p

   local AlphaMat,HMat,MUpper,NullZeile,qMat,MLower,NTRULat;

      AlphaMat := MatToRowList(alpha*MatId(R, Length(h)));
      HMat     := List([1..Length(h)], i-> Concatenation(List([Length(h)-i+2..Length(h)], j-> h[j]), List([1..Length(h)-i+1], j-> h[j])));
      MUpper   := List([1..Length(h)], i-> Concatenation(AlphaMat[i],HMat[i]));
      NullZeile:= List([1..Length(h)], i-> 0); 
      qMat     := MatToRowList(q*MatId(R, Length(h)));
      MLower   := List([1..Length(h)], i-> Concatenation(NullZeile,qMat[i]));

      NTRULat  := Mat(R, Concatenation(MUpper,MLower));


   return(MatTrans(NTRULat)); 


end;


NTRULatticeMinimumCols := function(L)
   return(Sqrt(Minimum(List(MatToColList(L), i-> SP(i,i)))));
end;

NTRULatticeBasisLength := function(L)
   return(List(MatToColList(L), i-> Sqrt(SP(i,i))));
end;






ReverseLattice := function(L)

   local K;

      K := MatToColList(L);
      K := Reversed(K);
      K := MatTrans(Mat(K));     
      return(K);
end;
        

Permutation := function(N)

   local M,xx,a,b,l;
      
       M := MatId(R,N);
       for xx in [1..N] do
          repeat
            a := IntRandomBits(xx) mod (N+1);
            b := IntRandomBits(xx) mod (N+1);
          until (a > 0 and b >0);
          l := MatToRowList(M[a])[1];
          M[a] := M[b];
          M[b] := l;
          M    := Mat(M);
       od;  

       return(M);
end;



NTRUAttack := function(K,n,delta)

   local L,xx,U;

      L := Copy(K);
      for xx in [1..n] do
        
         L := MatLLL(L,delta)[1];
          #  Print(NTRULatticeBasisLength(L),"  ",xx,"\n");
         Print(NTRULatticeMinimumCols(L), " ",xx,"\n");
         U := Permutation(MatCols(K));
         L := L*U; 
      od;
end;