Laboratorio di Crittografia (lezione 1,parte 2) In Zn un numero si dice invertibile se esiste un altro numero intero in Zn che se moltiplicato al primo dà 1. Es. [2]7*[4]7:=[1]7 Che relazione c’è tra un elemento x in Zn e M.C.D. (x,n)? Se M.C.D. tra x e n è 1, allora esiste l’ inverso di x in Zn. In particolare, se n è un numero primo, allora tutti gli elementi di Zn sono invertibili, perché il massimo comune divisore tra un numero primo ed un altro qualsiasi purché minore è sempre 1. Invece in Zn con n non primo,non tutti i numeri sono invertibili. Es. [2]6*[x]6:=[1]6 x non esiste. Calcoliamo l’inverso di un numero x all’ intero di Zn. n=1245 x=56
Il M.C.D. è il resto della penultima operazione, cioè prima che il resto sia 0. Da qui, facciamo il percorso a ritroso: 1 = 13 – 4 * 3 = = 13 – (56 – 13* 4) * 3 = = 13 * 13 – 56 * 6 = = (1245 – 56 * 22) *13 – 56 * 3 = = 1245 * 13 – 56 * (22* 13 + 3) = = 1245 * 13 – 56 * 289 = = 1245 * 13 + 56 * (- 289) Alla fine si ottiene [1] = [1245] * [13] + [56] * [956] dove 956 è l’inverso di 56.
Identità di Bezout L’ ultima operazione della sequenza è un’ identità di Bezout: dati a, b appartenenti a Z M.C.D. (a,b) = d esistono α, β app. a Z tali che a * α + b * β = d
