Calcolare le radici quadrate modulo n
Come faccio a calcolare le radici quadrate di [2]_244093247 ?
Il numero n=244093247 non e' primo, ma non e' neache della forma n=p*q con p,q due numeri primi. La scomposizione in fattori risulta - 19 * 829 * 15497
Grazie.
Il numero n=244093247 non e' primo, ma non e' neache della forma n=p*q con p,q due numeri primi. La scomposizione in fattori risulta - 19 * 829 * 15497
Grazie.
Risposte
Potresti scriverlo in un formato comprensibile, così non comprendo cosa cerchi...
L'equazione e' del tipo x^2 = [a] mod n. Quando n non e' un primo, per risolvere l'equazione devo trovare due primi p e q tale che p*q = n. In questo caso di primi ce ne sono tre.
Nel mio esempio il primo numero primo era 19. Ha radici quadrate se 2^(19-1)/2 congruo 1 mod 19. Quindi 512 - 1 mod 19 deve risultare 0 (oppure 512-1 deve essere un multiplo del mio primo 19) che non esiste, quindi [2]_244093247 non ha radici quadrate. Ho provato per curiosita' trovare le radici quadrate di [2]_829 e' non esistono.
E' giusto quello che ho fatto e la mia conclusione ?
Puo' esistere che un numero non primo che si scompone in piu' di due primi (tre ad esempio) ed ha radici quadrate?
Nel mio esempio il primo numero primo era 19. Ha radici quadrate se 2^(19-1)/2 congruo 1 mod 19. Quindi 512 - 1 mod 19 deve risultare 0 (oppure 512-1 deve essere un multiplo del mio primo 19) che non esiste, quindi [2]_244093247 non ha radici quadrate. Ho provato per curiosita' trovare le radici quadrate di [2]_829 e' non esistono.
E' giusto quello che ho fatto e la mia conclusione ?
Puo' esistere che un numero non primo che si scompone in piu' di due primi (tre ad esempio) ed ha radici quadrate?
Il modo che userei io per risolvere problemi del genere è l'uso del simbolo di Jacobi. Prova a darci un occhio! Inoltre il problema è strettamente connesso alla ricerca di residui quadratici...
"adriano001":
Quando n non e' un primo, per risolvere l'equazione devo trovare due primi p e q tale che p*q = n. In questo caso di primi ce ne sono tre.
... non mi è chiaro, perché dovrei trovarli?
Dovrei trovarli per poter risolvere l'equazione, cioe' per poter trovare le radici quadrate di [a]_n. (della forma x^2 = [a]_n). Faccio cosi' perche cosi mi e' stato insegnato (magari ci sono altri metodi per trovare le radici quadrate di un intero modulo n con n primo o non primo).
Premetto che non ho fatto una verifica diretta completa e forse non c'entra nulla, comunque sappiamo che [tex]\mathbb{Z}_{244093247} \cong \mathbb{Z}_{19} \times \mathbb{Z}_{829} \times \mathbb{Z}_{15497}[/tex].
Ora calcolare gli elementi di [tex][x]_{19} \in \mathbb{Z}_{19}[/tex] tali che [tex][x]^2 _{19} = [2]_{19}[/tex] è sicuramente più agevole che non farlo per l'anello intero, e si trova che in effetti non ce ne sono in [tex]\mathbb{Z}_{19}[/tex]. Quindi posso supporre che (è solo una mia supposizione non verificata), data la presenza dell'isomorfismo questa proprietà si rifletta anche su [tex]\mathbb{Z}_{244093247}[/tex].
Ora calcolare gli elementi di [tex][x]_{19} \in \mathbb{Z}_{19}[/tex] tali che [tex][x]^2 _{19} = [2]_{19}[/tex] è sicuramente più agevole che non farlo per l'anello intero, e si trova che in effetti non ce ne sono in [tex]\mathbb{Z}_{19}[/tex]. Quindi posso supporre che (è solo una mia supposizione non verificata), data la presenza dell'isomorfismo questa proprietà si rifletta anche su [tex]\mathbb{Z}_{244093247}[/tex].
Perche' puoi solo supporre? Per esistere le radici quadrate in Z_244093247 tutti i suoi primi devono avere radici quadrate (prima verifico se i primo hanno radici quadrata in Z_n); in questo caso visto che il suoi primo primo (che e' 19) non ne ha radici quadrate, allora deduco che non esistono radici quadrate in Z_244093247. O no?
Suppongo perchè non ne sono sicuro 
PS. Cerca di usare le formule, così risulta più facile leggere quello che scrivi
PS. Cerca di usare le formule, così risulta più facile leggere quello che scrivi
Calcolo di radici quadrate in $ Z_p $ con p primo, e calcolo di radici quadrate in $ Z_n $ con $ n = pq $.
Una regola dice: se p e un primo dispari e se $ [a]_p != [0]_p $ ha due radici quadrate se e solo se $ a^((p-1)/2) -= 1 $ $ mod $ $ p $.
Se ha radici quadrate allora:
Se $ p $ $ -=_4 $ $ 3 $ ed $ [a]_p $ ha radici quadrate (sopra) allora tali radici sono $ \pm [a]_p^((p+1)/4) $.
Se $ p $ $ -=_4 $ $ 1 $ ed $ [a]_p $ ha radici quadrate allora il calcolo delle radici e' piu' complicato: l'algoritmo (del quale non conosco il nome) mette di calcolare $ r_i $ dove $ i = 0,1,2 ... $ e $ w_i $.
Per quanto riguarda quando $ n $ e numero non primo e $ n = pq $, con $ p $ e $ q $ primi dispari. Sia $ a $ tale che $ MCD(a, n) = 1 $. Le classe $ [a]_n $ ha radici quadrate in $ Z_n $ se e solo se $ [a]_p $ ha radici quadrate in $ Z_p $ e $ [a]_q $ ha radici quadrate in $ Z_q $.
Esempio:
Calcolare se esistono le radici quadrate di $ [271]_943 $.
Calcolanda la fattorizzazione di $ 943 $ risulta essere $ 943 = 23 * 41 $. Essendo $ 271 % 23 = 18 $ e $ 271 % 41 = 25 $ le radici quadrate di $ [271]_943 $ essistono solo se esistono le radici quadrate di $ [18]_23 $ e $ [25]_41 $.
Quindi per calcolare le radici quadrate di $ [271]_943 $ bisogna svolgere il sistema (l'ho fatto come una matrice perche non c'e' il simbolo per il sistema, comunque e' un sistema ):
$ ( (x -=_23 8), (x -=_41 5)) $ e $ ( (y -=_23 8), (y -=_41 -5)) $
Le mie domande sono:
Mi puo capirate un numero $ [a]_n $ come nel mio esempio nel quale $ n $ si scompone in piu di due fattori primi ? Si risolve esattamente nello stesso modo come se fosse $ n = pq $ ? Se si, quanti sistemi risultano ?
Una regola dice: se p e un primo dispari e se $ [a]_p != [0]_p $ ha due radici quadrate se e solo se $ a^((p-1)/2) -= 1 $ $ mod $ $ p $.
Se ha radici quadrate allora:
Se $ p $ $ -=_4 $ $ 3 $ ed $ [a]_p $ ha radici quadrate (sopra) allora tali radici sono $ \pm [a]_p^((p+1)/4) $.
Se $ p $ $ -=_4 $ $ 1 $ ed $ [a]_p $ ha radici quadrate allora il calcolo delle radici e' piu' complicato: l'algoritmo (del quale non conosco il nome) mette di calcolare $ r_i $ dove $ i = 0,1,2 ... $ e $ w_i $.
Per quanto riguarda quando $ n $ e numero non primo e $ n = pq $, con $ p $ e $ q $ primi dispari. Sia $ a $ tale che $ MCD(a, n) = 1 $. Le classe $ [a]_n $ ha radici quadrate in $ Z_n $ se e solo se $ [a]_p $ ha radici quadrate in $ Z_p $ e $ [a]_q $ ha radici quadrate in $ Z_q $.
Esempio:
Calcolare se esistono le radici quadrate di $ [271]_943 $.
Calcolanda la fattorizzazione di $ 943 $ risulta essere $ 943 = 23 * 41 $. Essendo $ 271 % 23 = 18 $ e $ 271 % 41 = 25 $ le radici quadrate di $ [271]_943 $ essistono solo se esistono le radici quadrate di $ [18]_23 $ e $ [25]_41 $.
Quindi per calcolare le radici quadrate di $ [271]_943 $ bisogna svolgere il sistema (l'ho fatto come una matrice perche non c'e' il simbolo per il sistema, comunque e' un sistema ):
$ ( (x -=_23 8), (x -=_41 5)) $ e $ ( (y -=_23 8), (y -=_41 -5)) $
Le mie domande sono:
Mi puo capirate un numero $ [a]_n $ come nel mio esempio nel quale $ n $ si scompone in piu di due fattori primi ? Si risolve esattamente nello stesso modo come se fosse $ n = pq $ ? Se si, quanti sistemi risultano ?
No! Il problema di origine non ha soluzione, per il semplice fatto che:
[tex]x^2 \equiv 2 \mod pqs[/tex]
implica necessariamente:
[tex]x^2 \equiv 2 \mod p[/tex]
[tex]x^2 \equiv 2 \mod q[/tex]
[tex]x^2 \equiv 2 \mod s[/tex]
Ed allora necessariamente nel nostro caso avendo:
[tex]x^2 \equiv 2 \mod 19[/tex]
[tex]x^2 \equiv 2 \mod 829[/tex]
non risolubili, mentre:
[tex]9670^2 \equiv 2 \mod 15497[/tex]
Allora non ci possono essere soluzioni globali.
[tex]x^2 \equiv 2 \mod pqs[/tex]
implica necessariamente:
[tex]x^2 \equiv 2 \mod p[/tex]
[tex]x^2 \equiv 2 \mod q[/tex]
[tex]x^2 \equiv 2 \mod s[/tex]
Ed allora necessariamente nel nostro caso avendo:
[tex]x^2 \equiv 2 \mod 19[/tex]
[tex]x^2 \equiv 2 \mod 829[/tex]
non risolubili, mentre:
[tex]9670^2 \equiv 2 \mod 15497[/tex]
Allora non ci possono essere soluzioni globali.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo