quale è il modo più veloce x trovare un inverso modulo m?
io di solito faccio:
MCD(a,m)=1
a^phi(m)=1(mod m)
a^(phi(m)-1)=1/a(mod m)
con un po di calcoli e riduzioni trovo il rappresentante privilegiato di a^(phi(m)-1) modulo m.
xò kiaramente questo metodo può risultare molto lungo x certi valori di a e m, qualcuno conosce un metodo più veloce??
inversi modulo m
Si usa il teorema di Bézout e l'algoritmo di Euclide con un'aggiunta.
Dati m, n interi coprimi esistono x, y interi tali che 1 = xm + yn (Bézout). In particolare $ x = m^{-1} \pmod{n} $ e $ y = n^{-1} \pmod{m} $. Per calcolare x e y vedere qua http://posso.dm.unipi.it/~traverso/Arit ... -print.pdf , dove dice appunto "come si calcolano x e y"
Dati m, n interi coprimi esistono x, y interi tali che 1 = xm + yn (Bézout). In particolare $ x = m^{-1} \pmod{n} $ e $ y = n^{-1} \pmod{m} $. Per calcolare x e y vedere qua http://posso.dm.unipi.it/~traverso/Arit ... -print.pdf , dove dice appunto "come si calcolano x e y"
Presidente della commissione EATO per le IGO
