Follow along with the video below to see how to install our site as a web app on your home screen.
Nota: This feature may not be available in some browsers.
x = a mod m
a = x + km (per ogni k)
(a+b) = x + km
a = x + km - b
Supponendo di non avere il 9
a = 2 + k*6 - 5 = -3 + k*6 = 3, 9, 15, 21, ...
Supponendo di non avere il 5
a = 2 + k*6 - 9 = -7 + k*6 = 5, 11, 17, ...
Come valore di k va bene qualsiasi numero che ti dia un valore positivo. Per esempio potresti k=(b-x)/m parte intera superiore (aka, approssimato per eccesso) . Per esempio nel primo caso hai k=(5-2)/6=3/6=0.5 che approssimato per eccesso ti da k=1 (e ti porta ad avere a=3), mentre nel secondo caso hai k=(9-2)/6=7/6 che approssimato per eccesso ti da 2 (e ti porta ad avere k=5).Per risalire a k bisogna fare k = a // m oppure ci sono altri modi?
Con il prodotto è un'altra storia, qui devi calcolare prima l'inversa moltiplicativa modulo m. A tal proposito puoi usare l'algoritmo di Euclide esteso. Tieni presente che l'inversa moltiplicativa esiste (ed è unica) solo se MCD(a,m)=1.Nuovo Grazie mille, sei stato molto chiaro, mentre se fosse stato (5*9) mod 6 allora a = (x + km) /b Giusto?
Ok, tutto chiaro. Se mi fai un esempio ti sarò molto grato. (7*15) mod 8Non puoi ricavare un singolo valore perché hai infiniti valori validi, si dice che hai una classe di soluzioni.
Tutti i valori di a sono equivalenti, non hai modo di distinguerli, esattamente come guardando un orologio non hai modo di distinguere le 4:00 dalle 16:00. Se ti sposto l'orologio avanti di 12 ore (o 24, 36, 48, 60, ...) tu non hai modo di accorgertene. Sull'orologio le 4:00 e le 16:00 sono la stessa ora esattamente come modulo 6 il 3 e il 9 sono lo stesso numero.
Se vuoi risolvere ax = b mod m (conosci a,b,m e vuoi trovare x) devi:
Se mi dai un esempio magari ti faccio anche i calcoli... ma non è difficile.
- Verificare se esiste un inversa moltiplicativa di a mod m, se non esiste allora non ci sono soluzioni. Per verificarlo basta che guardi se b/MCD(a,m) è un intero, in caso MCD(a,m)=1 hai che esiste ed è anche unica tra i valori da 0 a m-1 (perché ovviamente valgono le stesse considerazioni fatte in precedenza, in realtà è una classe di soluzioni con infiniti possibili valori tra i numeri naturali).
- Calcolare l'inversa moltiplicativa andando a tentativi (for (i=1; i<m; i++) a*i=1 mod m ?) oppure usando l'algoritmo di Euclide esteso per trovare la coppia di interi x e y tale che ax+my=1. Nella pagina di wikipedia che ti ho linkato c'è anche lo pseudocodice.
- Calcoli x=b*(a^-1).
(7*15) mod 8 = 105 mod 8 = 1 mod 8
(x*15) = 1 mod 8
Esiste l'inversa moltiplicativa di 15 mod 8?
MCD(15,8) = 1 (Ok)
Inversa moltiplicativa di 15 mod 8:
suppongo sia 1: 1*15 mod 8 = 7 (no, io cerco 1)
suppongo sia 2: 2*15 mod 8 = 6 (no, io cerco 1)
suppongo sia 3: 3*15 mod 8 = 5 (no, io cerco 1)
suppongo sia 4: 4*15 mod 8 = 4 (no, io cerco 1)
suppongo sia 5: 5*15 mod 8 = 3 (no, io cerco 1)
suppongo sia 6: 6*15 mod 8 = 2 (no, io cerco 1)
suppongo sia 7: 7*15 mod 8 = 1 (Ok, l'inversa moltiplicativa è 7)
x0 = 7*1 = 7
x = 7 + k*8 = 7, 15, 22, 30, 38, ...
x*37 = 61 mod 70
Esiste l'inversa moltiplicativa di 37 mod 70?
MCD(37,70) = 1 (Ok)
Inversa moltiplicativa di 37 mod 70:
37*i = 1 mod 70 (voglio scrivere 70 come: 37*qualcosa + resto)
1) 70 = 37*1 + 33 (voglio scrivere 37 come: 33*qualcosa + resto)
2) 37 = 33*1 + 4 (voglio scrivere 33 come: 4*qualcosa + resto)
3) 33 = 4*8 + 1 (resto 1, finito)
Ora procedo alla rovescia, inizio a rimpiazzare il primo resto (ovvero 1):
3) 1 = 33 - 4*8 (ora voglio rimpiazzare il 4)
2) 1 = 33 - (37-33)*8 (ora voglio rimpiazzare il 33)
1) 1 = (70-37) - (37 - (70-37))*8 (finito, ho solo 73 e 70 come nella congruenza da cui siamo partiti)
Semplifico:
1 = 70 - 37 - (37 - 70 + 37)*8
1 = 70 - 37 - (2*37 - 70)*8
1 = 70 - 37 - (8*2*37 - 8*70)
1 = 70 - 37 - (16*37 - 8*70)
1 = 70 - 37 - 16*37 + 8*70 (visto che 70*qualcosa = 0 mod 70, posso eliminarli tutti)
1 = -17 * 37 mod 70 (-17 è l'inversa moltiplicativa di 37 mod 70, se vuoi un numero positivo somma 70)
1 = (-17+70)*37 mod 70
1 = 53*37 mod 70 (finito: 53 è l'inversa moltiplicativa di 37 mod 70)
Trovo la classe di soluzioni per x*37 = 61 mod 70
x0 = 53*61 mod 70 = 3233 mod 70 = 13
x = 13 + k*70
Infatti: 13*37 = 481 mod 70 = 61 mod 70
Grazie mille.Codice:(7*15) mod 8 = 105 mod 8 = 1 mod 8
Supponiamo non avere il 7 e di voler trovare l'inversa andando a tentativi:
Codice:(x*15) = 1 mod 8 Esiste l'inversa moltiplicativa di 15 mod 8? MCD(15,8) = 1 (Ok) Inversa moltiplicativa di 15 mod 8: suppongo sia 1: 1*15 mod 8 = 7 (no, io cerco 1) suppongo sia 2: 2*15 mod 8 = 6 (no, io cerco 1) suppongo sia 3: 3*15 mod 8 = 5 (no, io cerco 1) suppongo sia 4: 4*15 mod 8 = 4 (no, io cerco 1) suppongo sia 5: 5*15 mod 8 = 3 (no, io cerco 1) suppongo sia 6: 6*15 mod 8 = 2 (no, io cerco 1) suppongo sia 7: 7*15 mod 8 = 1 (Ok, l'inversa moltiplicativa è 7) x0 = 7*1 = 7 x = 7 + k*8 = 7, 15, 22, 30, 38, ...
Per farti vedere l'algoritmo di Euclide esteso ti faccio un esempio un attimino più complesso, altrimenti c'è talmente poco da fare che non si capisce niente:
Codice:x*37 = 61 mod 70 Esiste l'inversa moltiplicativa di 37 mod 70? MCD(37,70) = 1 (Ok) Inversa moltiplicativa di 37 mod 70: 37*i = 1 mod 70 (voglio scrivere 70 come: 37*qualcosa + resto) 1) 70 = 37*1 + 33 (voglio scrivere 37 come: 33*qualcosa + resto) 2) 37 = 33*1 + 4 (voglio scrivere 33 come: 4*qualcosa + resto) 3) 33 = 4*8 + 1 (resto 1, finito) Ora procedo alla rovescia, inizio a rimpiazzare il primo resto (ovvero 1): 3) 1 = 33 - 4*8 (ora voglio rimpiazzare il 4) 2) 1 = 33 - (37-33)*8 (ora voglio rimpiazzare il 33) 1) 1 = (70-37) - (37 - (70-37))*8 (finito, ho solo 73 e 70 come nella congruenza da cui siamo partiti) Semplifico: 1 = 70 - 37 - (37 - 70 + 37)*8 1 = 70 - 37 - (2*37 - 70)*8 1 = 70 - 37 - (8*2*37 - 8*70) 1 = 70 - 37 - (16*37 - 8*70) 1 = 70 - 37 - 16*37 + 8*70 (visto che 70*qualcosa = 0 mod 70, posso eliminarli tutti) 1 = -17 * 37 mod 70 (-17 è l'inversa moltiplicativa di 37 mod 70, se vuoi un numero positivo somma 70) 1 = (-17+70)*37 mod 70 1 = 53*37 mod 70 (finito: 53 è l'inversa moltiplicativa di 37 mod 70) Trovo la classe di soluzioni per x*37 = 61 mod 70 x0 = 53*61 mod 70 = 3233 mod 70 = 13 x = 13 + k*70 Infatti: 13*37 = 481 mod 70 = 61 mod 70
Ok, grazie mille.a << b è uguale ad a*2^b. Quindi il problema si riconduce a A=x*2^B % m. Inoltre se m è un PRIMO DISPARI, 'inverso di 2^B è 2^C con B+C % (m-1)=0, ovvero x=A*2^(k(m-1)-B)%m con k intero tale che k(m-1)-B>=0 (ovviamente x si può determinare solo modulo m)
Nel tuo caso sappiamo che x=5 e vogliamo determinare 20. 7 è primo dispari e ponendo k=3 si ha 3*6-13=5 e quindi 5*2^5 % 7= 160%7 = 6 =20%7