Quanti e quali procedimenti ci vogliono per risolvere la (t^2+u*t+v) mod (B^2) = 0 ?
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$
?
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$
?
Risposte
Ho scritto una sciocchezza ?
Non è di facile risposta?
O altro ?
Non è di facile risposta?
O altro ?
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.
"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$
"P_1_6":
[quote="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$[/quote]
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$.
"hydro":
[quote="P_1_6"][quote="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$[/quote]
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$.[/quote]
Mi servirebbe una soluzione $a+b*(B^2)$
Come si procede ?
"hydro":
[quote="P_1_6"][quote="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$[/quote]
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$.[/quote]
La soluzione da te proposta si può (nel mio approccio) calcolare facilmente
Riprendiamo l'esempio del documento
"
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)$
E quindi?
"hydro":
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?
Te l’ho scritto sopra come si fa, e’ un procedimento totalmente elementare…
"hydro":
Te l’ho scritto sopra come si fa, e’ un procedimento totalmente elementare…
Ho trovato questo documento
https://www.mat.uniroma2.it/~geo2/radici.pdf
va bene per capire come risolvere il mio problema ?
prendiamo
$x^2+8410*x+978456=67^2*X$
ed $x=67*h+16$
la derivata prima modulo $67$ uguale $0$ quindi non si può sollevare ?
$x^2+8410*x+978456=67^2*X$
ed $x=67*h+16$
la derivata prima modulo $67$ uguale $0$ quindi non si può sollevare ?
La costruzione
di $(t^2+u*t+v) mod (B^2) = 0$
dove $u$,$v$,$B$ sono conosciuti e con $B$ numero primo
che fa questo documento
https://www.academia.edu/66788027/Fattorizzazione_wg
comporta sempre che la derivata prima
di $(t^2+u*t+v)$ in $t=B*b+a$ modulo $B$
dove $B$ ed $a$ sono costruite dal refence del documento
sia uguale a $0$ ?
di $(t^2+u*t+v) mod (B^2) = 0$
dove $u$,$v$,$B$ sono conosciuti e con $B$ numero primo
che fa questo documento
https://www.academia.edu/66788027/Fattorizzazione_wg
comporta sempre che la derivata prima
di $(t^2+u*t+v)$ in $t=B*b+a$ modulo $B$
dove $B$ ed $a$ sono costruite dal refence del documento
sia uguale a $0$ ?
Si possono cambiare i coefficienti di $(t^2+u*t+v)$ modulo $B^2$ tale che la derivata prima del polinomio risultante modulo $B$ sia diversa da $0$ ?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo