Beräkna inversen [c] till [b] sådant att [b][c] = 1
Fråga:
Jag funderar på om det går att, på ett smidigt sätt (utan att behöva använda Euklides algoritm) ,beräkna inversen [c] till [b] sådant att [b][c] = 1. Låt säga att jag har:
3x1 (mod 5) och vill beräkna så använder jag i nuläget följande metod:
Euklides:
5 = 1*3 + 2
3 = 1*2 + 1
1 = 3 - 1*2 = 3 - 1*(5-1*3) = 3 - 1*5 + 1*3 = 2*3 -1*5
=> = 2
Finns det möjligtvis en enklare och snabbare metod att beräkna inversen på?
Inte så vitt jag vet, men för cykliska grupper med väldigt få element så kan det gå snabbare att bara testa sig fram till inversen snarare än att använda den allmänna metoden.
Liksom vilken av 0,1,2,3,4 kan vara lösningar till ekvationen?
Bara att testa.
3*1 = 3 Nope.
3*2 = 6 = 1... jupp 2 var tydligen inversen.
De andra
3*3 = 9 = 4
3*4 = 12 = 2
Nope, de var inte inverser.
Gällande komplexitet så blir dock euklides algoritm effektivare när grupperna blir större.
SeriousCephalopod skrev:Inte så vitt jag vet, men för cykliska grupper med väldigt få element så kan det gå snabbare att bara testa sig fram till inversen snarare än att använda den allmänna metoden.
Liksom vilken av 0,1,2,3,4 kan vara lösningar till ekvationen?
Bara att testa.
3*1 = 3 Nope.
3*2 = 6 = 1... jupp 2 var tydligen inversen.
De andra
3*3 = 9 = 4
3*4 = 12 = 2
Nope, de var inte inverser.
Gällande komplexitet så blir dock euklides algoritm effektivare när grupperna blir större.
Tack för tipset! Då börjar jag med att testa med 0-4 och om inte det går så kör jag Euklides :)
