[Aritmetica MOD] Inverso moltiplicativo e Crittografia

[Rhawk]

Spero di non aver sbagliato sezione ma non sapevo proprio dove aprire questo thread.

Sto studiando l'algoritmo di crittografia Knapsack (Zaino)

Ho capito tutto tranne un passaggio che mi sta facendo uscire pazzo e la cosa assurda è che probabilmente è una stupidaggine galattica.
-----------
A deve inviare il carattere "a" a B

Prima della cifratura creo la sequenza di superincreasing con la proprietà che ogni numero sia superiore della somma dei suoi precedenti. ad esempio: (2, 3, 6, 13, 27, 52)
Calcolo W come sommatoria di tutti i valori della sequenza ed ottengo: 103
Scelgo M > W ad esempio 105
Calcolo N tale che appartenga al range [1, M) e sia coprimo con M ad esempio 31.

Ricavo la chiave pubblica:
2 * 31 mod 105 = 62
3 * 31 mod 105 = 93
6 * 31 mod 105 = 81
13 * 31 mod 105 = 88
27 * 31 mod 105 = 102
52 * 31 mod 105 = 37

Chiave pubblica = (62, 93, 81, 88, 102, 37)

Adesso A riceve la chiave pubblica di B con la quale cifrare il carattere "a" che supponiamo essere 011000
Determina il sacco da inviare a B prendendo i valori corrispondenti: 93 e 81 e li somma = 174
Quindi invia 174 a B

Adesso B riceve 174 da A

Calcola l'inverso moltiplicativo di 31 ed ottiene 61

Non capisco da dove esce fuori 61.
L'inverso moltiplicativo di 31 è semplicemente 1/31, il mod utilizzato fino ad ora è 105 e non capisco da dove salti fuori questo 61.

Qualcuno saprebbe aiutarmi a capire quale passaggio viene effettuato ?

Grazie!

[@melia]

Nelle classi resto l'inverso moltiplicativo non è il reciproco.
Ad esempio nella classe resto modulo 7, l'inverso moltiplicativo di 2 è 4, infatti $2*4 (mod7)=1$

Nella classe resto modulo 105, l'inverso moltiplicativo di 31 è 61 perché
$31*61=1891=18*105+1$ quindi $31*61 (mod105)=1$

[Rhawk]

Scusa ma continuo a non capire,
se io ho 31 mod 105 come faccio a sapere che il suo inverso moltiplicativo è 61

Io non conoscendolo avrei una cosa del tipo:
31 * x = y dove x scoprirò sarà essere il mio 61


Ad esempio:

52 * 31 mod 105 = 37 perchè: 1612 / 105 = 15... quindi 1612 - (105*15) = 37

Ma nel mio caso non ho nè 52 e nè 37, ho solo 31 mod 105 e non so come ricavare il primo numero.

Cioè appunto 31 mod 105 e capire che l'inverso moltiplicativo è 61

[Rhawk]

In pratica per trovare l'inverso moltiplicativo di 31 mod 105
devo trovare quel numero che moltiplicato 31 mod 105 mi dia come risultato 1

quindi mi viene da pensare di provarli tutti finchè non trovo che x * 31 mod 105 = 1
dove x abbiamo trovato essere 61 infatti 1891-1890 = 1

mi chiedevo solo se ci fosse una formula matematica in grado di trovarmelo subito senza provarli tutti prima di capire che è 61.

[Cantor99]

Penso che possa essere utile l'algoritmo delle successione successive di Euclide per trovare il massimo comune divisore. Ad esempio
$105=31*3+12$
$31=12*2+7$
$12=7*1+5$
$7=5*1+2$
$5=2*2+1$
Da cui
$1=5-2*2=5-2*(7-5*1)=3*5-2*7=3*(12-7*1)-2*7=3*12-7*5=3*12-5*(31-12*2)=13*12-5*31=13*(105-31*3)-5*31=13*105-44*31$
Quindi l'intero cercato è $-44$ che modulo $105$ vale precisamente $61$