Hot-News.it

il portale hot con notizie da tutto il mondo!

Scegli Lingua : Hot-News.it in italiano Hot-News.it in inglese Hot-News.it in spagnolo Hot-News.it in francese Hot-News.it in tedesco Hot-News.it in giapponese Hot-News.it in arabo
Login With Facebook
Giovedi
Apr 15
Messaggio
Hot-News.it Merlino's Science News CONGRUENZA QUADRATICA BINARIA X² ≡ A (MODULO P Numero primo)
15
Giu
2013

CONGRUENZA QUADRATICA BINARIA X² ≡ A (MODULO P Numero primo)




X² ≡ A  (MODULO P Numero primo)Risolvere questa congruenza significa trovare, se esiste, un quadrato esatto tale che il resto della sua divisione per il numero primo P, sia A.Ricordiamo

La Hot News

che, in Teoria dei Numeri, si definisce residuo quadratico di un numero primo P proprio il resto della divisione di un quadrato esatto per P.I numeri primi hanno la notevole proprietà di avere esattamente (P-1)/2 residui quadratici e (P-1)/2 non residui quadratici.Per quanto detto, questa congruenza avrà soluzioni solo se A è un residuo quadratico di P.Per stabilire se un intero A sia residuo quadratico di un numero primo P, si usa il criterio di Eulero (useremo il simbolo ” ^ ” per indicare “elevato a”):Se  A^[(P-1)2] ≡ 1 (modulo P), allora A è residuo quadratico di P.Se  A^[(P-1)2] ≡ -1 (modulo P), allora A è non residuo quadratico di P.Una volta accertato che A è un residuo quadratico di P, siamo certi che la congruenza ha soluzione.Fissiamo subito un punto fondamentale:Se A è un residuo quadratico del numero primo P, la congruenza quadratica binaria  X² ≡ A  ha sempre due soluzioni (ovviamente inferiori a P). Se chiamiamo queste due soluzioni M ed N, allora saranno tali che  M + N  =  P.Spesso queste soluzioni vengono chiamate radici quadrate di A modulo P.Dato che A deve essere un residuo quadratico di P, per quanto detto, dovrà essere:A^[(P-1)2] ≡ 1Moltiplichiamo primo e secondo membro per A:A*A^[(P-1)2] ≡ AA^[1 + (P-1)/2] ≡ AA^[(2 + P -1)/2] ≡ AA^[(P + 1)/2] ≡ AA questo punto basta trovare il numero X tale che:X² = A^(P + 1)/2Che è ovviamente:X = A^(P + 1)/4Potremmo pensare di aver così risolto la congruenza, ma purtroppo ciò è vero solo nel caso in cui (P + 1)/4 sia un numero intero.Ci può però consolare la considerazione che questo avviene per il 50% dei numeri primi.Ricordiamo che i numeri primi si dividono in due grandi famiglie: quelli che diviso 4 danno come resto 1 e quelli che diviso 4 danno per resto 3. Non esistono altre possibilità.I primi avranno forma P = 4k + 1 ed i secondi P = 4k + 3.Ebbene, per questa seconda famiglia, l’espressione (P + 1)/ 4 è un numero intero:(P + 1)/4 = (4k + 3 +1)/4 = (4k + 4)/4 = k +1TEOREMA:Se P è un numero primo della forma 4K + 3 ed A un suo residuo quadratico, la congruenza quadratica  X² ≡ A  (modulo P) ha due soluzioni:M = A^(k + 1) modulo P ed N = P – MRisolviamo ad esempio la congruenza:X² ≡ 2 (modulo 23)2 è residuo quadratico di 23, in quanto:2^11 = 2048 e 2048 modulo 23 = 123 è della forma 4k + 3, infatti 23 = 4*5 +3 e sarà k = 5M = A^(k+1) = 2^(5 + 1) = 2^6 = 64M = 64 modulo 23 = 18N = P – M = 23 – 18 = 5Dunque le due soluzioni della congruenza saranno 18 e 5Verifichiamo:18² = 324324 : 23 = 14 con resto 25² = 2525 : 23 = 1 con resto 2Si può però risolvere la congruenza anche nel caso di P = 4k + 1.I numeri primi della forma 4k + 1 si possono dividere in due grandi famiglie: quelli delle forme 8s + 1 ed 8s + 5.Per questi ultimi abbiamo la soluzione, però dobbiamo distinguere 2 casi:Se A^[(P-1)/4] ≡ 1 (modulo P), allora una soluzione è:M = A^(s + 1)Se A^[(P-1)/4] ≡ -1 (modulo P), allora una soluzione è:M = [2^(2s + 1)] * A^(s + 1)Facciamo un esempio:Si voglia risolvere la congruenza:X² ≡ 7 (modulo 29)7 è un residuo quadratico di 29 (fidatevi ….)29 è della forma (8s + 5), infatti 29 = 8*3 + 5 ed s sarà 3A^[(P-1)/4] = 7^(28/4) = 7^7 = 823543823543 modulo 29 = 1, quindi siamo nel primo caso.M = A^(s + 1) = 7^(3+1) = 7^4 = 2401M = 2401 modulo 29 = 23N = P – M = 29 – 23 = 6Dunque le due soluzioni della congruenza saranno 23 e 6Verifichiamo:23² = 529529 : 29 = 18 con resto 76² = 3636 : 29 = 1 con resto 7Se P è della forma 8s + 1, anche in questo caso esistono due famiglie per una delle quali esiste la soluzione e così via all’infinito …. About these ads div { margin-top: 1em; } ]]>Share this:Facebook

[...Leggi Tutto]

 
 

Novita'  Vuoi Commentare l'Articolo? Accedi al portale o se non hai il login Registrati


Ogni opinione espressa in questi commenti e' unicamente quella del suo autore, identificato tramite nickname collegato alla sua registrazione e di cui si assume ogni responsabilita' civile, penale e amministrativa derivante dalla pubblicazione del materiale inviato.L'utente, inviando un commento, dichiara e garantisce di tenere Hot-News.it manlevata e indenne da ogni eventuale effetto pregiudizievole e/o azione che dovesse essere promossa da terzi con riferimento al materiale divulgato e/o pubblicato.

Sconti e Offerte

Risparmi, Sconti, OfferteVuoi risparmiare sui tuoi acquisti? Offerte, Sconti, Codici Sconto, LastMinute e tanto altro ancora solo per te!

Ads

Le HOT News!

 

Vuoi Guadagnare e fare Affari!?

 Vuoi guadagnare e fare affari con internet?! Scopri come ogni giorno puoi, con soli 5 mi...

 

Dediche d'Amore

Dedica al tuo Lui o alla tua Lei parole d'amore...Hot-News.it pubblicherà la tua dedica ...

 

Dì la tua! Pubblica un tuo articolo!

Diventa reporter di Hot-News.it! E' facilissimo! 2 secondi e potrai veder i tuoi articoli ...

Chi è Online

Visitatori Online  7288 visitatori online

Statistiche Visitatori

mod_vvisit_counterOggi6093
mod_vvisit_counterQuesto mese114005
mod_vvisit_counterTotale19245928


forum, portale, soundtrack, hotnews, hot news, notizie, videogiochi, ps3, xbox, shop, compra, prezzi, gossip, donna, rss, calcio, mondo, lavoro, musica, calciomercato, voti fantacalcio, probabili formazioni, uomini e donne, amici, maria de filippi