/*
Master Pro ISFA filiere CCS, 2007-2008
TP4 pour le cours de Reseaux Euclidiens et Applications
Damien Stehle
*/




{
Build_family_of_polynomials (P, N, m, t) =
  local(sol); local(d);
  d =poldegree (P);
  sol = [];  


  for (i=0, m-1, 
    for (j=0, d-1, sol = concat(sol, [x^j * P^i *N^(m-i)])));
  
  for (i=0, t, sol = concat(sol, [P^m*x^i]));

  return(sol)
} 
  
  

{
Univariate_coppersmith (P, N, X, m, t) =
   local(set); local (d); local (mat); local(T); local (Pres);
   local(nb); local(roots); local (sol);

   set = Build_family_of_polynomials (P, N, m, t);
   d = length(set);
   mat = matid (d);

   for (i=1, d, 
     for (j=1, d, 
       mat[j,i] = X^(j-1)*polcoeff(set[i], j-1)
   ));

   T = qflll(mat);
   mat = mat*T; 
   
   Pres = 0;
   for (i=1, d, Pres = Pres + x^(i-1) * mat[i,1] / X^(i-1));

/*
   l = 0; for (i=1, d, l=l+mat[i,1]^2);
   print(sqrt(l));
*/

   roots = polroots(Pres);
   nb = length(roots);


   sol = [];
 
   for (i=1, nb, 
     roots[i] = round(roots[i]);
     if (conj(roots[i])== roots[i], sol = concat(sol, [roots[i]]))
   );

   return (sol)
}



p=nextprime(random(2^128))
q=nextprime(random(2^128))
N=p*q

highp = 2^40*round(p/2^40)
sol = p-highp
P=x+highp


/*
substpol(P, x, sol) % p
for (i=1, length(set), t=substpol(set[i], x, sol) % p^m; print(t))
substpol(Pres, x, sol) % p^m
*/

X = 2^40; m=5; t=5
sol = Univariate_coppersmith(P, N, X, m, t)
for (i=1, length(sol), print(N/(highp+sol[i])))








p=nextprime(random(2^128))
q=nextprime(random(2^128))
N=p*q

e = 3; d = e^(-1) % ((p-1)*(q-1))
m = random (N)
x0 = random (2^40)
c = (m+x0)^e % N

P = (m+x)^e - c
X=2^40; m=5; t=0
sol = Univariate_coppersmith(P, N, X, m)