/* 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)