Urgente domani ho l'esame
ciao come faccio a calcolare a^b mod n se a e n non sono primi tra loro? Mi potreste mostare il procedimento generale grazie ciao
Risposte
Nessuno sa come si fa? Mi serve veramente per l'esame.. So calcolarlo quando a e n sono primi tra loro ma non mi ricordo al procedura quando non sono primi tra loro. Non c'è nessuno che lo sa? grazie ciao
potresti spiegare meglio il tuo dubbio? cosa vuol dire "calcolare" $a^b (mod n)$..non sembra avere molto senso..
intendi a congruo a b modulo n?
Forse ho sbagliato a scrivere ma non so come scriverlo. Intendo sia a il rappresentante significativo della classe di resto modulo n, se lo elevo alla b che numero ottengo sempre in modulo di quella classe di resto? Mi sono spiegato bene ora. Grazie ciao
dipende da b!! Esempio, in $ZZ/5z$ prendi l'elemento $bar2$ e elevalo alla $0,1,2,3,4$, vedi che ottieni, in modulo $5$, i valori $bar1,bar2,bar4,bar3,bar1$, e osservi quindi che l'ordine moltiplicativo della classe di $2$ in $ZZ/5z$ è $4$ (come d'altronde doveva essere, essendo $5$ primo....) Forse non capisco la tua richiesta...
Si risolvono con il teorema di eulero. Il problema è che il teorema di eulero vale solo quando a e n sono primi tra loro. Ma esiste un modo per usarlo facendo un po' di passaggi. Il problema è che non me li ricordo esattamente. Qualcuno lo sa? grazie ciao
Ma si risolvono COSA? manca il soggetto alla tua domanda!! $a^b (mod n)$ non vuol dire niente...come si fa ad aiutarti se non si capisce di cosa hai bisogno? Fai un esempio di quelli che sai fare, magari riesco a capire cosa intendi e cerco di aiutarti...
"alvinlee88":
Ma si risolvono COSA? manca il soggetto alla tua domanda!! $a^b (mod n)$ non vuol dire niente...come si fa ad aiutarti se non si capisce di cosa hai bisogno? Fai un esempio di quelli che sai fare, magari riesco a capire cosa intendi e cerco di aiutarti...
forse intende a^b congruo modulo n a 1???
in quel caso b sarebbe l'ordine di a
Se è come dice JazzLover, tu stai dicendo che quando $a$ e $n$ sono coprimi, ti è facile trovare il $b$ tale che $a^b equiv 1 (mod n)$, perchè è semplicemente $phi(n)$. Se non sono primi fra loro, devi andare a tentativi con i vari divisori di $phi(n)$, finchè non becchi il $b$ giusto...intendevi questo?
"marco1988":
ciao come faccio a calcolare a^b mod n se a e n non sono primi tra loro? Mi potreste mostare il procedimento generale grazie ciao
Avevo cominciato a risponderti poi ci ho rinunciato...
$a^b modn$ se $(a,n)!=1$ non sarà mai congruente a 1 ma è comunque ciclico.
Se consideri $t = n/((a, n))$ allora $(a/((a, n)))^(varphi(t)) -= 1 modt$
Quindi se consideri $u = (a, b)$ e per semplicità pongo $(u, t)=1$ hai che $a^b modn = u*(u^(b-1) modt)*((a/u)^b modt) modn -= u*(u^(b-1 modvarphi(t))*(a/u)^(b modvarphi(t)) modt) modn$
Se $(u, t)!=1$ si prosegue ricorsivamente.
P.S: potrei sbagliarmi quindi controlla...
Allora faccio un esempio. Calolare la cifra delle unita del numero 546^3221. In questo caso a=546, b=3221 n=10. Come si risolve????
"marco1988":
Allora faccio un esempio. Calolare la cifra delle unita del numero 546^3221. In questo caso a=546, b=3221 n=10. Come si risolve????
allora...$u = (546, 10) = 2$
$t = 5$
$(u, t) = 1
$Quindi
$546/2 = 273$
$varphi(5) = 4$ perché 5 è primo...
$273^(3221)\ modt -= (273^4)^(805)*273\ modt -= 273\ modt -= 3\ modt$
$2^(3220)\ modt -= (273^4)^(805)\ modt -= 1 modt$
$546^(3221)\ modn -= 2*3\ modn -= 6 modn$
P.S: la calcolatrice di windows mi dà ragione...
Anche PARI/GP quindi devo aver ragione...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo