Function: zncoppersmith
Section: number_theoretical
C-Name: zncoppersmith
Prototype: GGGDG
Help: zncoppersmith(P, N, X, {B=N}): finds all integers x
 with |x| <= X such that  gcd(N, P(x)) >= B. X should be smaller than
 exp((log B)^2 / (deg(P) log N)).
Doc: $N$ being an integer and $P\in \Z[X]$, finds all integers $x$ with
 $|x| \leq X$ such that
 $$\gcd(N, P(x)) \geq B,$$
 using \idx{Coppersmith}'s algorithm, a famous application of the \idx{LLL}
 algorithm. The parameter $X$ must be smaller than
 $\exp(\log^2 B / (\deg(P) \log N))$: for $B = N$, this means
 $X < N^{1/\deg(P)}$. Some $x$ larger than $X$ may be returned if you are
 very lucky. The smaller $B$ (or the larger $X$), the slower the routine will
 be. The strength of Coppersmith method is the ability to find roots modulo a
 general \emph{composite} $N$: if $N$ is a prime or a prime power,
 \tet{polrootsmod} or \tet{polrootspadic} will be much faster.

 We shall now present two simple applications. The first one is
 finding non-trivial factors of $N$, given some partial information on the
 factors; in that case $B$ must obviously be smaller than the largest
 non-trivial divisor of $N$.
 \bprog
 setrand(1); \\ to make the example reproducible
 [a,b] = [10^30, 10^31]; D = 20;
 p = randomprime([a,b]);
 q = randomprime([a,b]); N = p*q;
 \\ assume we know 0) p | N; 1) p in [a,b]; 2) the last D digits of p
 p0 = p % 10^D;

 ? L = zncoppersmith(10^D*x + p0, N, b \ 10^D, a)
 time = 1ms.
 %6 = [738281386540]
 ? gcd(L[1] * 10^D + p0, N) == p
 %7 = 1
 @eprog\noindent and we recovered $p$, faster than by trying all
 possibilities $ x < 10^{11}$.

 The second application is an attack on RSA with low exponent, when the
 message $x$ is short and the padding $P$ is known to the attacker. We use
 the same RSA modulus $N$ as in the first example:
 \bprog
 setrand(1);
 P = random(N);    \\ known padding
 e = 3;            \\ small public encryption exponent
 X = floor(N^0.3); \\ N^(1/e - epsilon)
 x0 = random(X);   \\ unknown short message
 C = lift( (Mod(x0,N) + P)^e ); \\ known ciphertext, with padding P
 zncoppersmith((P + x)^3 - C, N, X)

 \\ result in 244ms.
 %14 = [2679982004001230401]

 ? %[1] == x0
 %15 = 1
 @eprog\noindent
 We guessed an integer of the order of $10^{18}$, almost instantly.