Metodo Coppersmith

[P_1_6]

A questo polinomio conoscendo che $|n0|<(7*81)^(1/3)$

$-(7*16)*n^3+(7*4920)*n^2-(7*504282)*n+(7*17228405)=X*(7*81)$

è applicabile il metodo Coppersmith?

[P_1_6]

mentre aspettavo la risposta ho pensato questo dividere per $7$ e moltiplicare per $32$
ed imporre $8*n=m$ e si avrà
$-m^3+2460*m^2-2017128*m+551308960=X*2592$
così è applicabile il metodo Coppersmith?

[P_1_6]

Per correttezza vi spiego a cosa serve.

Le soluzioni $h$ e $k$ di
$[(h+1)^2]*[(2*h+2)^2/2-1]=X*M$
ed
$[(k+1)^2]*[(2*k+2)^2/2-1]=Y*M$
sono tali che ogni numero M divisibile per 9 ha queste caratteristiche $(h+1)/3=(k+1)/6$ ,$k+h+2=M$ ed è divisore di una somma di cubi dispari da $1$ ad $n=2*h+1$

quindi ci andremo a cercare i numeri divisibili per 9 in questo modo

sia $N=a*b$ un numero da fattorizzare $N-(2*s)^2-2*s*n=M$ dove $n=b-a$ ed $s$ va da $1$ ad $8$

quindi avremo se $N != 9*c$ avremo $8$ formule

quindi risolviamo il sistema nella variabile $n$

solve
$[(h+1)^2]*[(2*h+2)^2/2-1]=X*(N-(2*s)^2-2*s*n)$
,
$[(k+1)^2]*[(2*k+2)^2/2-1]=Y*(N-(2*s)^2-2*s*n)$
,
$(h+1)/3=(k+1)/6$
,
$k+h+2=(N-(2*s)^2-2*s*n)$


Esempio $N=209$

per $s=1$

solve
$[(h+1)^2]*[(2*h+2)^2/2-1]=X*(209-4-2*n)$
,
$[(k+1)^2]*[(2*k+2)^2/2-1]=Y*(209-4-2*n)$
,
$(h+1)/3=(k+1)/6$
,
$k+h+2=(209-4-2*n)$

si avrà

$-16*n^3+4920*n^2-504282*n+17228405=X*81$

Ora viene la parte che non conosco ed ho pensato di usare il metodo Coppersmith (se si può usare)

Siccome la $n$ massima in un generico numero da fattorizzare è |_$N/3-3$_| quindi nel nostro caso |_$209/3-3$_|=66

$[66^3/81]=3549,...$ quindi prenderemo il numero primo $P$ più piccolo maggiore di $3549$ che è $P=3557$


$-(3557*16)*n^3+(3557*4920)*n^2-(3557*504282)*n+(3557*17228405)=X*(3557*81)$

Ora sappiamo che esiste $n0$ tale che $|n0|<(3557*81)^(1/3)$ e che $-(3557*16)*n0^3+(3557*4920)*n0^2-(3557*504282)*n0+(3557*17228405)=0 mod (3557*81)$

Ora per usare il metodo Coppersmith i miei dubbi sono $2$ :

-il coefficiente di $n^3$ deve essere $1$?
-il $GCD$ di tutti i coefficienti di $n$ e di $3557*81$ deve essere $1$?

ho letto quì https://amslaurea.unibo.it/5910/1/palmi ... o_tesi.pdf ad inizio pag $22$

"
Sia $N$ un numero composto intero la cui fattorizzazione non è conosciuta,
sia
$p(x)$
un polinomio intero di grado $δ$ nella singola variabile $x$. Supponiamo esista
una soluzione intera $x0$ a
$p(x0) = 0 (mod N)$
che soddisfa
$|x0| < N^(1/δ)$
Coppersmith `e riuscito a trovare la soluzione $x0$ in tempo polinomiale in
$(log N, 2^δ)$
"

allora le altre due domande che mi pongo se il metodo Coppersmith è utilizzabile sono:
-Se conosciamo la fattorizzazione di $N$ ne possiamo trarre benefici?
-Qual'è il problema se c'è nell'usare il metodo Coppersmith?

grazie per eventuali risposte.