Test di primalità di Fermat
Salve a tutti.. c'è una cosa che dev'essere sicuramente molto semplice ma che proprio non riesco a fare: come da oggetto, vorrei verificare se un dato numero è primo (o meglio, se NON lo è) applicando il piccolo teorema di Fermat.
Solo che... ehm.. non saprei da dove iniziare.
So che per il "piccolo" (
), se $a$ e $p$ sono coprimi, allora $a^p-=a\ (mod\ p)$ (oppure che $a^(p-1)-=1\ (mod p)$), ma non riesco a trasferire questa nozione ad un caso pratico.. ad esempio, vorrei dimostrare che il numero $368413$ è composto.
Ora, io so che lo è e conosco anche la sua fattorizzazione, ma posto che non lo sapessi, non saprei nemmeno da dove iniziare a dimostrarlo!
Ad esempio.. dovrei trovare un $a$ tale che $a^368412$ non sia congruo ad $1\ (mod\ 368413)$??
Non so.. tutto questo mi pare un po' troppo macchinoso... e ad ogni modo non ne sarei capace!
Che cosa sto sbagliando?
Solo che... ehm.. non saprei da dove iniziare.
So che per il "piccolo" (
), se $a$ e $p$ sono coprimi, allora $a^p-=a\ (mod\ p)$ (oppure che $a^(p-1)-=1\ (mod p)$), ma non riesco a trasferire questa nozione ad un caso pratico.. ad esempio, vorrei dimostrare che il numero $368413$ è composto.Ora, io so che lo è e conosco anche la sua fattorizzazione, ma posto che non lo sapessi, non saprei nemmeno da dove iniziare a dimostrarlo!
Ad esempio.. dovrei trovare un $a$ tale che $a^368412$ non sia congruo ad $1\ (mod\ 368413)$??
Non so.. tutto questo mi pare un po' troppo macchinoso... e ad ogni modo non ne sarei capace!
Che cosa sto sbagliando?
Risposte
Stai sbagliando poichè il teorema di Fermat non si può ribaltare... voglio dire che esistono numeri composti denominati pseudo-primi tali che:
$a^(n-1)\equiv 1 (n)$
Quindi sicuramente non è un teorema di primalità. Covresti cercare qualcosa di più computazionale...
$a^(n-1)\equiv 1 (n)$
Quindi sicuramente non è un teorema di primalità. Covresti cercare qualcosa di più computazionale...
Forse ho sbagliato a formulare la mia richiesta allora..:
So che esistono pseudoprimi e numeri di Carmichael, e che quindi ci sono numeri per cui il test viene passato (per qualche $a$ nel caso degli pseudoprimi, per ogni $a$ nel caso dei numeri di Carmichael) anche se non sono primi.
Tuttavia la mia domanda è un'altra: posto che un numero non sia pseudoprimo né sia un numero di Carmichael, posto quindi che $ EE a$ t.c. $a^(n-1) -= 1 \ (mod \ n)$ sia falsa, come faccio a trovare questo $a$ e dimostrare quindi che $n$ non è primo?
Non so se sono stato chiaro adesso.. praticamente ciò che chiedo è di poter risolvere un esercizio specifico in cui venga chiesto di verificare la primalità di un numero senza ricorrere a null'altro che al piccolo teorema di Fermat!
Suppongo che si debba procedere per tentativi... ma se anche così fosse, non saprei bene come fare..
So che esistono pseudoprimi e numeri di Carmichael, e che quindi ci sono numeri per cui il test viene passato (per qualche $a$ nel caso degli pseudoprimi, per ogni $a$ nel caso dei numeri di Carmichael) anche se non sono primi.
Tuttavia la mia domanda è un'altra: posto che un numero non sia pseudoprimo né sia un numero di Carmichael, posto quindi che $ EE a$ t.c. $a^(n-1) -= 1 \ (mod \ n)$ sia falsa, come faccio a trovare questo $a$ e dimostrare quindi che $n$ non è primo?
Non so se sono stato chiaro adesso.. praticamente ciò che chiedo è di poter risolvere un esercizio specifico in cui venga chiesto di verificare la primalità di un numero senza ricorrere a null'altro che al piccolo teorema di Fermat!
Suppongo che si debba procedere per tentativi... ma se anche così fosse, non saprei bene come fare..
Secondo me si potrebbe partire dal fatto che non ci sia differenza tra cercare la primalità o la non primalità di un numero.
Poichè il solo piccolo Teorema di Fermat non è sufficiente, allora si usa il Test di Primalità di Miller-Rabin.
Da pag. 15 di questo file e da pag. 7 di quest'altro file.
Poichè il solo piccolo Teorema di Fermat non è sufficiente, allora si usa il Test di Primalità di Miller-Rabin.
Da pag. 15 di questo file e da pag. 7 di quest'altro file.
"The_Mad_Hatter":
So che per il "piccolo" (
Piccola precisazione: $a^p \equiv a (mod p)$ è vero per $p$ primo e $a$ intero QUALUNQUE (dopotutto si dimostra per induzione).
L'ipotesi che $MCD(a, p) = 1$ è necessaria soltanto per la seconda formula, $a^(p-1) \equiv 1 (mod p)$, che segue direttamente dalla precedente dividendo per $a$, che essendo $a$ e $p$ coprimi si può fare senza problemi.
Passo a naso:
Considera:
$lg_2(368413)=18,...$
$2^19 = 524288 \equiv 155875 (368413)$
Allora:
$2^368413=2^(19*19390+3) \equiv 155875^3*155875^19390 \equiv 328274*155875^19390 \equiv 328274*178275^9695 (368413)$
$\equiv 328274*178275*91354^4847 \equiv 273887*91354*91354^4846 \equiv 272516*262040^2423 (368413)$
dovresti aver capito il metodo immagino...
Considera:
$lg_2(368413)=18,...$
$2^19 = 524288 \equiv 155875 (368413)$
Allora:
$2^368413=2^(19*19390+3) \equiv 155875^3*155875^19390 \equiv 328274*155875^19390 \equiv 328274*178275^9695 (368413)$
$\equiv 328274*178275*91354^4847 \equiv 273887*91354*91354^4846 \equiv 272516*262040^2423 (368413)$
dovresti aver capito il metodo immagino...
"DavideV":
Secondo me si potrebbe partire dal fatto che non ci sia differenza tra cercare la primalità o la non primalità di un numero.
Poichè il solo piccolo Teorema di Fermat non è sufficiente, allora si usa il Test di Primalità di Miller-Rabin.
Da pag. 15 di questo file e da pag. 7 di quest'altro file.
Ovvio che non è l'unico! Ci sono molti algoritmi di primalità e purtroppo non ce ne è uno universale!
mi fido di voi! 
"Lord K":
Passo a naso:
Considera:
$lg_2(368413)=18,...$
$2^19 = 524288 \equiv 155875 (368413)$
Allora:
$2^368413=2^(19*19390+3) \equiv 155875^3*155875^19390 \equiv 328274*155875^19390 \equiv 328274*178275^9695 (368413)$
$\equiv 328274*178275*91354^4847 \equiv 273887*91354*91354^4846 \equiv 272516*262040^2423 (368413)$
dovresti aver capito il metodo immagino...
Azz.. ma sbaglio o ci vorrebbe un fottio di tempo?
Proverei un caso più semplice allora... cito un'altra traccia:
"Applicando il criterio di Fermat scomporre il numero 731 nel prodotto di fattori primi; determinare poi gli eventuali divisori dello zero dell'anello $(ZZ_731, +,* )$"
La seconda parte è ok, so determinare i divisori dello zero di $ZZ_n$, se conosco la scomposizione in fattori primi di $n$!
Per la prima invece dovrei fare..:
$log_2(731) = 9$
$2^10 = 1024 -=293\ (mod\ 731) $
$2^731 = 2^(9*81+2) -= ??? $
...e poi? mi son perso!
$293^81*4 = 293*293^80*4$
E poi continuare come sopra!
E poi continuare come sopra!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo