Congruenze e test di primalità
Ciao a tutti,
volevo chiedervi aiuto per il calcolo di una congruenza. Probabilmente è una cosa facile ma io non ho per nulla dimestichezza con l'aritmetica modulare. Il problema dice:
Verificare se 341 è primo con il test di Fermat.
Dunque, io so che dal teorema di Fermat discende una condizione necessaria affinchè un numero p sia primo. Quindi basta trovare un controesempio che viola questa condizione per affermare che p non lo sia. In particolare:
se $n$ è primo e se $MCD(n,a)=1$, allora $a^(n-1) (mod n) \equiv 1$.
Quindi basta trovare un $a$ che soddisfi l'ipotesi ma non la tesi, per dire che n non è primo.
Parto con $a=2$ e voglio calcolare $2^430 mod 431$. Io questo lo saprei calcolare se potessi scomporre 431 in primi, perchè c'ho un paio di altri teoremini che mi permettono di semplificare le cose. Però, visto che lo spirito dell'esercizio è: verifica se 431 è primo, credo che per calcolare quella congruenza ci debba essere un altro modo, a prescindere dal sapere o meno la fattorizzazione di 431.
Come si fa?
Grazie in anticipo
volevo chiedervi aiuto per il calcolo di una congruenza. Probabilmente è una cosa facile ma io non ho per nulla dimestichezza con l'aritmetica modulare. Il problema dice:
Verificare se 341 è primo con il test di Fermat.
Dunque, io so che dal teorema di Fermat discende una condizione necessaria affinchè un numero p sia primo. Quindi basta trovare un controesempio che viola questa condizione per affermare che p non lo sia. In particolare:
se $n$ è primo e se $MCD(n,a)=1$, allora $a^(n-1) (mod n) \equiv 1$.
Quindi basta trovare un $a$ che soddisfi l'ipotesi ma non la tesi, per dire che n non è primo.
Parto con $a=2$ e voglio calcolare $2^430 mod 431$. Io questo lo saprei calcolare se potessi scomporre 431 in primi, perchè c'ho un paio di altri teoremini che mi permettono di semplificare le cose. Però, visto che lo spirito dell'esercizio è: verifica se 431 è primo, credo che per calcolare quella congruenza ci debba essere un altro modo, a prescindere dal sapere o meno la fattorizzazione di 431.
Come si fa?
Grazie in anticipo
Risposte
C'è un metodo dovuto a Legendre - se non ricordo male - che consisteva nel "quadrare" in presenza di esponente pari e moltiplicare in presenza di uno dispari.
Detto così non ci si capisce nulla, però, ad es., se devo calcolare $2^11$
- $11= 10+1$
- $10=5 \cdot 2$
- $5=4+1$
- $4=2 \cdot 2$
- 2 è il quadrato e basta.
Dunque $2^11= 2^10 \cdot 2= (2^5)^2 \cdot 2= (2^4 \cdot 2 )^2 \cdot 2 = ((2^2)^2 \cdot 2)^2 \cdot 2$.
Detto così non ci si capisce nulla, però, ad es., se devo calcolare $2^11$
- $11= 10+1$
- $10=5 \cdot 2$
- $5=4+1$
- $4=2 \cdot 2$
- 2 è il quadrato e basta.
Dunque $2^11= 2^10 \cdot 2= (2^5)^2 \cdot 2= (2^4 \cdot 2 )^2 \cdot 2 = ((2^2)^2 \cdot 2)^2 \cdot 2$.
Ciao Zero.. intanto grazie 1000 per la risposta.
Però ancora non mi è chiaro come col tuo metodo giungo a una soluzione. Veramente io di aritmetica modulare sono ignorantissimo e non vedo neanche le cose più banali..
Comunque sono andato un po' avanti. dunque ero rimasto che non sapevo calcolare $2^340 (mod 341)$. (nel testo sopra ho detto due alla 430 mod 431, ma era un errore di battitura). Ora, in maniera abbastanza fortuita, ossia andando alla cieca e facendo calcoli a caso, ho notato che $341*3 = 1023$ e che quindi $2^10 \equiv 1 mod 341$. A questo punto quindi dovrebbe essere facile perchè $2^340 (mod 341) = (2^10)^34 (mod 341) \equiv 1^34 (mod 341) = 1 (mod 341)$. Giusto?
Però appunto il test di fermat serve per dire quando un numero NON è primo, quindi si va avanti con altre basi prime finchè non si trova una congruenza diversa da 1. Quindi vado avanti e provo con il 3. Devo calcolare quindi ora $3^340 (mod 341)$. Facendo calcoli random tipo prima non ho trovato nessun escamotage tipo quello di prima con la base $2$. Ho calcolato un po' di potenze di 3 e un po' di multipli di 341, ma niente. E in effetti poi guardando la soluzione del libro, $3^340 (mod 341) = 56$, non $1$. Come facevo a calcolarlo??
AGGIUNTA
ok, con un po' di lavoro di becero reverse engineering (e con la calcolatrice del cellulare), ho trovato che $3^10 = 59049 = 173*341 + 56$ quindi $3^10 (mod 341)$ effettivamente è $\equiv 56 (mod 341)$. Ma a questo punto quindi $3^340 (mod 341) = (3^10)^34 (mod 341) \equiv 56^34 (mod 341)$. E quindi? devo andare avanti, scomporre 56, elevare a 34 i fattori e provare di nuovo a caso finchè non trovo qualche trick per proseguire? E poi rimane il fatto che se non avessi letto nella soluzione "56", mai avrei trovato che $3^10 \equiv 56 (mod341)$... Heeeelp!!!!
Però ancora non mi è chiaro come col tuo metodo giungo a una soluzione. Veramente io di aritmetica modulare sono ignorantissimo e non vedo neanche le cose più banali..
Comunque sono andato un po' avanti. dunque ero rimasto che non sapevo calcolare $2^340 (mod 341)$. (nel testo sopra ho detto due alla 430 mod 431, ma era un errore di battitura). Ora, in maniera abbastanza fortuita, ossia andando alla cieca e facendo calcoli a caso, ho notato che $341*3 = 1023$ e che quindi $2^10 \equiv 1 mod 341$. A questo punto quindi dovrebbe essere facile perchè $2^340 (mod 341) = (2^10)^34 (mod 341) \equiv 1^34 (mod 341) = 1 (mod 341)$. Giusto?
Però appunto il test di fermat serve per dire quando un numero NON è primo, quindi si va avanti con altre basi prime finchè non si trova una congruenza diversa da 1. Quindi vado avanti e provo con il 3. Devo calcolare quindi ora $3^340 (mod 341)$. Facendo calcoli random tipo prima non ho trovato nessun escamotage tipo quello di prima con la base $2$. Ho calcolato un po' di potenze di 3 e un po' di multipli di 341, ma niente. E in effetti poi guardando la soluzione del libro, $3^340 (mod 341) = 56$, non $1$. Come facevo a calcolarlo??
AGGIUNTA
ok, con un po' di lavoro di becero reverse engineering (e con la calcolatrice del cellulare), ho trovato che $3^10 = 59049 = 173*341 + 56$ quindi $3^10 (mod 341)$ effettivamente è $\equiv 56 (mod 341)$. Ma a questo punto quindi $3^340 (mod 341) = (3^10)^34 (mod 341) \equiv 56^34 (mod 341)$. E quindi? devo andare avanti, scomporre 56, elevare a 34 i fattori e provare di nuovo a caso finchè non trovo qualche trick per proseguire? E poi rimane il fatto che se non avessi letto nella soluzione "56", mai avrei trovato che $3^10 \equiv 56 (mod341)$... Heeeelp!!!!
Ho ricontrollato sull'unica fonte che in questo momento ho a portata di mano (la mia tesi, §5.2.3, che sta pure da qualche parte su matematicamente 
).
Il metodo è di Legendre, non Lagrange e consiste nel "quadrare e moltiplicare" sfruttando le proprietà di potenza di potenza.
Nel tuo caso, $340=170 \cdot 2= 85 \cdot 2 \cdot 2 = (42\cdot 2 +1) \cdot 2 \cdot 2$ ecc... e così via.
Quindi $3^340= (((3^42)^2 \cdot 3 )^2)^2$: c'è comunque da scomporre anche il 42 (mi sono fermato prima tanto per visualizzare). Il punto è che questo è un metodo difficile solo da spiegare ma in realtà è una vera cavolata: la cosa facile è che la potenza di potenza è semplice sotto le congruenze perché il risultato si può sostituire con il resto della divisione per $n$.
Chiedo scusa per la spiegazione che fa davvero pena, ma ultimamente ho pochissimo tempo di passare al forum!
).Il metodo è di Legendre, non Lagrange e consiste nel "quadrare e moltiplicare" sfruttando le proprietà di potenza di potenza.
Nel tuo caso, $340=170 \cdot 2= 85 \cdot 2 \cdot 2 = (42\cdot 2 +1) \cdot 2 \cdot 2$ ecc... e così via.
Quindi $3^340= (((3^42)^2 \cdot 3 )^2)^2$: c'è comunque da scomporre anche il 42 (mi sono fermato prima tanto per visualizzare). Il punto è che questo è un metodo difficile solo da spiegare ma in realtà è una vera cavolata: la cosa facile è che la potenza di potenza è semplice sotto le congruenze perché il risultato si può sostituire con il resto della divisione per $n$.
Chiedo scusa per la spiegazione che fa davvero pena, ma ultimamente ho pochissimo tempo di passare al forum!
Dunque.. ho scaricato la tesi.. complimenti!!
Ho dato un'occhiata al paragrafo incriminato.. non mi è stato chiarissimo.. può essere che ci fosse un errore di battitura? (dove dici mod m intendi mod n ?)..
comunque credo di aver capito come usare il tuo metodo, provo a dire come ho fatto.. non so se è ortodossissimo perchè cmq un po' di conti bruti con la cacolatrice li devo fare.. diciamo che se voglio calcolare $a^m mod n$ posso arrivare a trovare numeri grandi fino a $n^2$ per poi ridurli a "mano", cioè con la calcolatrice facendo ans-m, per un po' di volte (o -10*m per andare un po' + veloci xDDD)..
$3^340 mod 341 = (((((((3^2)^2*3)^2)^2*3)^2)^2*3)^2)^2 mod 341$
visto che $3$, $3^2$, $(3^2)^2$ e $3*(3^2)^2$ sono tutti minori di $341$, parto da $(3*(3^2)^2)^2 = 59049 \equiv 56 mod 341$ (calcolato a mano con la calcolatrice). A questo punto ogni volta elevo al quadrato e moltiplico per 3, finchè non arrivo a un numero maggiore di 341, quindi lo riduco modulo 341 e vado avanti così. In questo modo non ho mai numeri più grandi di 341^2. e la riduzione bruta con la calcolatrice non è troppo sbatti. Alla fine trovo 56. Il metodo è ok?
Grazie
Ho dato un'occhiata al paragrafo incriminato.. non mi è stato chiarissimo.. può essere che ci fosse un errore di battitura? (dove dici mod m intendi mod n ?)..
comunque credo di aver capito come usare il tuo metodo, provo a dire come ho fatto.. non so se è ortodossissimo perchè cmq un po' di conti bruti con la cacolatrice li devo fare.. diciamo che se voglio calcolare $a^m mod n$ posso arrivare a trovare numeri grandi fino a $n^2$ per poi ridurli a "mano", cioè con la calcolatrice facendo ans-m, per un po' di volte (o -10*m per andare un po' + veloci xDDD)..
$3^340 mod 341 = (((((((3^2)^2*3)^2)^2*3)^2)^2*3)^2)^2 mod 341$
visto che $3$, $3^2$, $(3^2)^2$ e $3*(3^2)^2$ sono tutti minori di $341$, parto da $(3*(3^2)^2)^2 = 59049 \equiv 56 mod 341$ (calcolato a mano con la calcolatrice). A questo punto ogni volta elevo al quadrato e moltiplico per 3, finchè non arrivo a un numero maggiore di 341, quindi lo riduco modulo 341 e vado avanti così. In questo modo non ho mai numeri più grandi di 341^2. e la riduzione bruta con la calcolatrice non è troppo sbatti. Alla fine trovo 56. Il metodo è ok?
Grazie
"giacor86":
Dunque.. ho scaricato la tesi.. complimenti!!
Ho dato un'occhiata al paragrafo incriminato.. non mi è stato chiarissimo.. può essere che ci fosse un errore di battitura? (dove dici mod m intendi mod n ?)..
Grazie. Comunque non credo sia esente da errori di battitura... però era l'unica cosa che mi veniva in mente come riferimento.
"giacor86":
comunque credo di aver capito come usare il tuo metodo
Se era mio credo sarei diventato famoso come matematico, eheh
"giacor86":
$3^340 mod 341 = (((((((3^2)^2*3)^2)^2*3)^2)^2*3)^2)^2 mod 341$
visto che $3$, $3^2$, $(3^2)^2$ e $3*(3^2)^2$ sono tutti minori di $341$, parto da $(3*(3^2)^2)^2 = 59049 \equiv 56 mod 341$ (calcolato a mano con la calcolatrice). A questo punto ogni volta elevo al quadrato e moltiplico per 3, finchè non arrivo a un numero maggiore di 341, quindi lo riduco modulo 341 e vado avanti così. In questo modo non ho mai numeri più grandi di 341^2.
Ottimo, è proprio questo il succo del metodo. In questo modo riduci le operazioni da fare e non hai mai numeri troppo grossi.
Anche a me e a wolframalpha (ho ricontrollato per sicurezza!) viene uguale. Comunque se ti interessa - trattasi di svista! - hai fatto solo un piccolo errore scrivendo "mod 431" invece di "mod 341" (io nel quotare ho corretto).
Ok grazie 1000 per l'aiuto!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo