09/12/2023, 14:36
11/12/2023, 09:02
11/12/2023, 11:09
11/12/2023, 11:44
hydro ha scritto: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.
11/12/2023, 12:27
P_1_6 ha scritto:hydro ha scritto: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$
11/12/2023, 12:38
hydro ha scritto:P_1_6 ha scritto:hydro ha scritto: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$.
13/12/2023, 08:41
hydro ha scritto:P_1_6 ha scritto:hydro ha scritto: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$.
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]
13/12/2023, 13:06
14/12/2023, 09:12
hydro ha scritto:E quindi?
14/12/2023, 13:08
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.