Quanti e quali procedimenti ci vogliono per risolvere la (t^2+u*t+v) mod (B^2) = 0 ?

[P_1_6]

Sono andato a rivedere qualcosa di qualche anno fa e mi è venuto un dubbio.
Vi andrebbe di dare uno sguardo?
il documento è questo
https://www.academia.edu/66788027/Fattorizzazione_wg
in pratica si deve risolvere
$(t^2+u*t+v) mod (B^2) = 0$
dove $u$,$v$,$B$ sono conosciuti
ho trovato interessante la risoluzione che fa questo sito
https://www.alpertron.com.ar/QUAD.HTM
in pratica se $B$ (che possiamo scegliere noi) è primo è un vantaggio
poi l'ordine di grandezza di t lo conosciamo
quindi per $t$ di $2048$ bit e $B$ di $1024$ bit secondo voi è fattibile?
Quanti e quali procedimenti ci vogliono per risolvere
$(t^2+u*t+v) mod (B^2) = 0$
?

[P_1_6]

Ho scritto una sciocchezza ?
Non è di facile risposta?
O altro ?

[hydro]

Quando $B$ è primo basta risolvere quell'equazione quadratica modulo $B$, cosa che equivale semplicemente a trovare la radice quadrata di $v^2-4u$ (vedi algoritmo di Cipolla), e poi sollevarla ad una soluzione modulo $B^2$ (puoi sollevarla modulo $B^n$ per qualsiasi $n$). Questo è essenzialmente il lemma di Hensel, e nella pratica basta risolvere un'equazione lineare. Quando $B$ non è primo, fattorizzalo in potenze di primi, applica il procedimento di sopra per ognuno dei fattori e poi usa il teorema cinese del resto.

[P_1_6]

Quando $B$ è primo basta risolvere quell'equazione quadratica modulo $B$, cosa che equivale semplicemente a trovare la radice quadrata di $v^2-4u$ (vedi algoritmo di Cipolla), e poi sollevarla ad una soluzione modulo $B^2$ (puoi sollevarla modulo $B^n$ per qualsiasi $n$). Questo è essenzialmente il lemma di Hensel, e nella pratica basta risolvere un'equazione lineare. Quando $B$ non è primo, fattorizzalo in potenze di primi, applica il procedimento di sopra per ognuno dei fattori e poi usa il teorema cinese del resto.

Gentilmente mi potresti fare un esempio con $B$ numero primo?

$(t^2+9811*t+4813774) mod (67^2) = 0$

[hydro]

Quando $B$ è primo basta risolvere quell'equazione quadratica modulo $B$, cosa che equivale semplicemente a trovare la radice quadrata di $v^2-4u$ (vedi algoritmo di Cipolla), e poi sollevarla ad una soluzione modulo $B^2$ (puoi sollevarla modulo $B^n$ per qualsiasi $n$). Questo è essenzialmente il lemma di Hensel, e nella pratica basta risolvere un'equazione lineare. Quando $B$ non è primo, fattorizzalo in potenze di primi, applica il procedimento di sopra per ognuno dei fattori e poi usa il teorema cinese del resto.

Gentilmente mi potresti fare un esempio con $B$ numero primo?

$(t^2+9811*t+4813774) mod (67^2) = 0$

Poni $f(x)=x^2+9811x+4813774$. Il discriminante è $4$, le radici dell'equazione modulo $67$ sono $18$ e $20$. Fissane una, diciamo $18$. Adesso calcola $f(18+67*k)$. Ti verrà fuori $67^2k^2+f(18)+67k(2\cdot 18+9811)$. Ora $f(18)$ è divisibile per $67$ mentre $(2\cdot 18+9811)$ no perchè è la derivata di $f$ calcolata in $18$ che non è una radice doppia. Ne segue che $f(18)+67k(2\cdot 18+9811)\equiv 0\mod 67^2$ ha una soluzione in $k$. Chiamala $\overline{k}$; vedrai che $18+67\overline{k}$ è una soluzione alla tua equazione di partenza. L'altra la trovi uguale partendo da $20$.

[P_1_6]

Quando $B$ è primo basta risolvere quell'equazione quadratica modulo $B$, cosa che equivale semplicemente a trovare la radice quadrata di $v^2-4u$ (vedi algoritmo di Cipolla), e poi sollevarla ad una soluzione modulo $B^2$ (puoi sollevarla modulo $B^n$ per qualsiasi $n$). Questo è essenzialmente il lemma di Hensel, e nella pratica basta risolvere un'equazione lineare. Quando $B$ non è primo, fattorizzalo in potenze di primi, applica il procedimento di sopra per ognuno dei fattori e poi usa il teorema cinese del resto.

Gentilmente mi potresti fare un esempio con $B$ numero primo?

$(t^2+9811*t+4813774) mod (67^2) = 0$

Poni $f(x)=x^2+9811x+4813774$. Il discriminante è $4$, le radici dell'equazione modulo $67$ sono $18$ e $20$. Fissane una, diciamo $18$. Adesso calcola $f(18+67*k)$. Ti verrà fuori $67^2k^2+f(18)+67k(2\cdot 18+9811)$. Ora $f(18)$ è divisibile per $67$ mentre $(2\cdot 18+9811)$ no perchè è la derivata di $f$ calcolata in $18$ che non è una radice doppia. Ne segue che $f(18)+67k(2\cdot 18+9811)\equiv 0\mod 67^2$ ha una soluzione in $k$. Chiamala $\overline{k}$; vedrai che $18+67\overline{k}$ è una soluzione alla tua equazione di partenza. L'altra la trovi uguale partendo da $20$.

Mi servirebbe una soluzione $a+b*(B^2)$
Come si procede ?

[P_1_6]

Quando $B$ è primo basta risolvere quell'equazione quadratica modulo $B$, cosa che equivale semplicemente a trovare la radice quadrata di $v^2-4u$ (vedi algoritmo di Cipolla), e poi sollevarla ad una soluzione modulo $B^2$ (puoi sollevarla modulo $B^n$ per qualsiasi $n$). Questo è essenzialmente il lemma di Hensel, e nella pratica basta risolvere un'equazione lineare. Quando $B$ non è primo, fattorizzalo in potenze di primi, applica il procedimento di sopra per ognuno dei fattori e poi usa il teorema cinese del resto.

Gentilmente mi potresti fare un esempio con $B$ numero primo?

$(t^2+9811*t+4813774) mod (67^2) = 0$

Poni $f(x)=x^2+9811x+4813774$. Il discriminante è $4$, le radici dell'equazione modulo $67$ sono $18$ e $20$. Fissane una, diciamo $18$. Adesso calcola $f(18+67*k)$. Ti verrà fuori $67^2k^2+f(18)+67k(2\cdot 18+9811)$. Ora $f(18)$ è divisibile per $67$ mentre $(2\cdot 18+9811)$ no perchè è la derivata di $f$ calcolata in $18$ che non è una radice doppia. Ne segue che $f(18)+67k(2\cdot 18+9811)\equiv 0\mod 67^2$ ha una soluzione in $k$. Chiamala $\overline{k}$; vedrai che $18+67\overline{k}$ è una soluzione alla tua equazione di partenza. L'altra la trovi uguale partendo da $20$.

La soluzione da te proposta si può (nel mio approccio) calcolare facilmente

Riprendiamo l'esempio del documento

"

Codice:

PROOF OF FACTORIZAZION 3 digit in polynomial time

17*43=731

solve
609-(a*n+518)-[4-(a-7)*(a-5)/8]=a*(a+75-12)/8
,
126501-(a*m+126410)-[4-(a-7)*(a-5)/8]=a*(a+1011-12)/8
,
a,n

n=m+117

609-(a+518)-[4-(a/x-7)*(a/x-5)/8]=a/x*(a/x+75-12)/8
,
126501-(a-117*a/x+126410)-[4-(a/x-7)*(a/x-5)/8]=a/x*(a/x+1011-12)/8
,
(a+518)*(a-117*a/x+126410)=X

a^2+9811*a+4813774=75^2*x


sage: R.<Z> = ZZ[]
sage: gp.zncoppersmith( Z^2+9811*Z+4813774, 5625, 2^7 )

[-68, 7, 82]


"

in questo modo (dal reference del documento)

$91-P-[4-(75-7)*(75-5)/8]=75*X$

$->$

$P=75*n+7$

solve $P=p*(q-75)/8=75*n+7$ ,$p*q=731$

$->$

$p=9-8*n$


$a^2+9811*a+4813774=75^2*x$

$(75*n+7)^2+9811*(75*n+7)+4813774=75^2*x$

$->$

$x=n^2+131*n+868$

$->$

$x=(n+7)*(n+124)$

[hydro]

E quindi?

[P_1_6]

E quindi?

per $B$ di $1024$ bit per $t$ di $2048$ bit
se si trova una soluzione $t=g+d*Z^2$ con $Z>=B$ si troverebbe facilmente una soluzione per $t$ di $2048$ bit

sfruttando il fatto che B lo possiamo scegliere numero primo come si trova questa soluzione?

[hydro]

Te l’ho scritto sopra come si fa, e’ un procedimento totalmente elementare…