Potenze di congruenze
ciao a tutti,
mi scuso fin da ora per la domanda, ma non potendo seguire le lezioni spesso mi blocco in cose per molti ovvie.
Da quello che ho capito, esistono metodi furbi per poter calcolare le potenze delle congruenze.
Studiano ho visto che ogni numero può essere espresso come potenza di due:
$a=2^{k_1}+2^{k_2}+2^{k_3}....$, giusto?
a questo punto però le cose cominciano a non essermi chiare.
In particolare dovrei risolvere il seguente esercizio:
calcolare $271^{321} (mod 481)$.
Nell'esercizio si fa notare che $321=2^0+2^6+2^8$.
Io questo passaggio non lo ho capito, mi è chiaro che $2^0=1$, ma poi nel resto mi fermo.
Vi ringrazio tutti fin da ora
mi scuso fin da ora per la domanda, ma non potendo seguire le lezioni spesso mi blocco in cose per molti ovvie.
Da quello che ho capito, esistono metodi furbi per poter calcolare le potenze delle congruenze.
Studiano ho visto che ogni numero può essere espresso come potenza di due:
$a=2^{k_1}+2^{k_2}+2^{k_3}....$, giusto?
a questo punto però le cose cominciano a non essermi chiare.
In particolare dovrei risolvere il seguente esercizio:
calcolare $271^{321} (mod 481)$.
Nell'esercizio si fa notare che $321=2^0+2^6+2^8$.
Io questo passaggio non lo ho capito, mi è chiaro che $2^0=1$, ma poi nel resto mi fermo.
Vi ringrazio tutti fin da ora
Risposte
Penso che con quel suggerimento intenda dire che un modo per non uscire pazzi da un conto del genere è ricondursi a degli elevamenti al quadrato: nel tuo caso si avrebbe $271^{321}=271^{1+2^6+2^8}=271*271^{2^6}*271^{2^8}$, ma elevare alla $2^n$ significa elevare al quadrato $n$ volte, il che è "fattibile" perché a ogni passo puoi sostituire il risultato con il suo resto modulo $481$, quindi ad esempio si parte da $271^2=73441=152*481+329$, poi si eleva al quadrato $329$, e così via.
L'unica cosa che mi lascia perplesso è: probabilmente questo sarebbe il metodo migliore se $481$ fosse un numero primo, ma in realtà è $13*37$, e allora sarebbe molto (ma davvero molto) più semplice calcolare quella potenza modulo $13$ e modulo $37$, per poi risalire al resto modulo $481$...
L'unica cosa che mi lascia perplesso è: probabilmente questo sarebbe il metodo migliore se $481$ fosse un numero primo, ma in realtà è $13*37$, e allora sarebbe molto (ma davvero molto) più semplice calcolare quella potenza modulo $13$ e modulo $37$, per poi risalire al resto modulo $481$...
ciao,
ti ringrazio subito per la risposta. Io mi ero bloccato molto prima, ma rivedendo meglio alcune cose ora la prima parte mi è chiara:
Parto da $321$ e lo scrivo in base binaria: $321=(10100001)_2$, quindi $321=2^0+2^6+2^8$.
A questo punto $271^{321}mod(481)$ equivale a $271^{2^0+2^6+2^8}$.
Quindi $271^{2^0}=73441\equiv 329 (mod 481)$, proprio per il discorso che facevi tu sui resti, e questo mi è chiaro.
In fatti poi calcola anche $271^{2^2} \equiv 329^2 (mod 481)$ e sempre per il discorso sui resti $271^{2^2} \equiv 16 (mod 481)$
Ora, l'esercizio prosegue e dice che usando le proprietà delle congruenze e delle potenze delle congruenze. In fatti dice che
$271^{2^8} \equiv 16 (mod 481)$ e che $271^{2^6} \equiv 419 (mod 481)$.
Sapresti spiegarmi gentilmente il perché degli ultimi due passaggi?
Le cose che mi dicevi credo che le vedrò a breve, perché intuisco usino alcuni teoremi per i numeri primi.
Ti\Vi ringrazio fin da ora.
ancora grazie
ti ringrazio subito per la risposta. Io mi ero bloccato molto prima, ma rivedendo meglio alcune cose ora la prima parte mi è chiara:
Parto da $321$ e lo scrivo in base binaria: $321=(10100001)_2$, quindi $321=2^0+2^6+2^8$.
A questo punto $271^{321}mod(481)$ equivale a $271^{2^0+2^6+2^8}$.
Quindi $271^{2^0}=73441\equiv 329 (mod 481)$, proprio per il discorso che facevi tu sui resti, e questo mi è chiaro.
In fatti poi calcola anche $271^{2^2} \equiv 329^2 (mod 481)$ e sempre per il discorso sui resti $271^{2^2} \equiv 16 (mod 481)$
Ora, l'esercizio prosegue e dice che usando le proprietà delle congruenze e delle potenze delle congruenze. In fatti dice che
$271^{2^8} \equiv 16 (mod 481)$ e che $271^{2^6} \equiv 419 (mod 481)$.
Sapresti spiegarmi gentilmente il perché degli ultimi due passaggi?
Le cose che mi dicevi credo che le vedrò a breve, perché intuisco usino alcuni teoremi per i numeri primi.
Ti\Vi ringrazio fin da ora.
ancora grazie
"diedro":
$271^{2^8} \equiv 16 (mod 481)$ e che $271^{2^6} \equiv 419 (mod 481)$.
Sapresti spiegarmi gentilmente il perché degli ultimi due passaggi?
ancora grazie
Non ho capito qual è il tuo dubbio: se ti riferisci a come si arriva a quelle due uguaglianze, si tratta semplicemente di fare qualche conto; in particolare, come già detto, devi elevare al quadrato un certo numero di volte, partendo da $271$: al primo passo ottieni $329$, al secondo $16$, al terzo $256$, e così via fino al sesto passo, che ti dà $419$ (e questo è $271^{2^6}$), e se elevi al quadrato altre due volte ottieni $16$ (che è $271^{2^8}$). Volendo scrivere tutto in una riga, avresti:
$271^{2^8}=(271^2)^{2^7}=329^{2^7}=(329^2)^{2^6}=16^{2^6}=(16^2)^{2^5}=...=419^{2^2}=(419^2)^2=(-4)^2=16$
(dove le uguaglianze sono in realtà congruenze modulo $481$)
ciao,
Grazie. Era proprio questo che volevo sapere.
Ora mi è tutto più chiaro.
Veramente grazie.
Grazie. Era proprio questo che volevo sapere.
Ora mi è tutto più chiaro.
Veramente grazie.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo