Discussione Addizione modulare

[Xenium]

Salve a tutti, supponendo di avere (5+9)%6 il risultato è 2. Ma se io conoscendo uno degli addendi, il risultato e il modulo come faccio a risalire al secondo addendo? Grazie

 

[St3ve]

Sapendo che vale questo:

x = a mod m
a = x + km   (per ogni k)

Ti basta sostituire a con a+b:

(a+b) = x + km
a = x + km - b

Questo vale per ogni k, ma visto che immagino che tu ti riferisca all'operatore modulo usato in programmazione, che nella maggior parte dei linguaggi calcola il resto della divisione, devi prendere un k sufficientemente alto per darti un valore di a positivo. Nel tuo esempio:

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, ...

 

[Xenium]

Grazie mille, sei stato molto chiaro, mentre se fosse stato (5*9) mod 6 allora a = (x + km) /b Giusto?

 

[Xenium]

Per risalire a k bisogna fare k = a // m oppure ci sono altri modi?

 

[St3ve]

Per risalire a k bisogna fare k = a // m oppure ci sono altri modi?

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).

Nuovo Grazie mille, sei stato molto chiaro, mentre se fosse stato (5*9) mod 6 allora a = (x + km) /b Giusto?

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.

 

[Xenium]

Grazie, ma facendo k=(b-x)/m e dopo a=(x+km-b) non ottengo il valore iniziale di a. Se io volessi ottenere esattamente il valore iniziale di a esistono altri modi per trovare k per tale fine? L'unico modo che ho trovato è k = (a+b) / m approssimando per difetto. Il problema è che io non conosco la somma di a+b ma conosco solamente b, m e x.

La formula dell'algoritmo di Euclide esteso è ax + by = MCD(a,b). Come hai detto MCD deve essere uguale a 1 quindi ax + by = 1. Questo mi permette di trovare il quoziente. Avendo (a*b) mod m e sostituendo a con il quoziente si avrà lo stesso risultato. Corretto? Ma è possibile trovare esattamente il valore di a anziché un'altro che però dà lo stesso risultato?

 

[St3ve]

Non 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:

• 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).

Se mi dai un esempio magari ti faccio anche i calcoli... ma non è difficile.

 

[Xenium]

Non 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:

• 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).

Se mi dai un esempio magari ti faccio anche i calcoli... ma non è difficile.

Ok, tutto chiaro. Se mi fai un esempio ti sarò molto grato. (7*15) mod 8

 

[St3ve]

(7*15) mod 8  =  105 mod 8  =  1 mod 8

Supponiamo non avere il 7 e di voler trovare l'inversa andando a tentativi:

(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:

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

 

[Xenium]

(7*15) mod 8  =  105 mod 8  =  1 mod 8

Supponiamo non avere il 7 e di voler trovare l'inversa andando a tentativi:

(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:

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.

 

[Xenium]

Un'altra domanda... Se invece ho (a << b) % m come si ricava a in questo caso? Per esempio se ho x = (20<<13) % 7 come ottengo 20 conoscendo x,7 e 13 ?

 

[Barbossa]

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

 

[Xenium]

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

Ok, grazie mille.

 

[Xenium]

Stavo provano con numeri a caso e facendo (542<<65345)%807 = 19 ; k = 82 ; k*(m-1)-b = 747 ; a = 19*2^747 % 807 = 491; (491<<65345)%807 = 382 Cosa c'è che non va?

 

[Barbossa]

807 non è primo, in quanto è un multiplo di 3, mentre il metodo che ho proposto vale solo per primi dispari.
Esiste un metodo valido per tutti gli m dispari, ma richiede conoscenze piuttosto avanzate di algebra