Witam.
Mam problem który potrzebuję rozwiązać. A mianowicie:
posiadam równanie typu:
23x mod26 =9.
Jaki jest najlepszy i najbardziej efektywny sposób obliczania tego typu równań?
Obliczanie równania modulo.
Obliczanie równania modulo.
Tzn jak dokładnie?może wypisac wszystkie mozliwosci w tabeli?
Wiem że 26=1*23+3
23=7*3+2
3=1*2+1
jakoś za pomocą tego da się obliczyć to równanie.
Możę ktoś dałby radę przedstawić całe rozwiązanie od początku do końca takiego równania?
-
msx100
- Użytkownik
- Posty: 261
- Rejestracja: 29 sie 2007, o 11:04
- Płeć: Mężczyzna
- Lokalizacja: RP
- Podziękował: 8 razy
- Pomógł: 51 razy
Obliczanie równania modulo.
ja pamietam, ze na zajeciach rozwiazywalismy to poprzez rysowanie tabelki i wpisywanie tam odpowiednich reszt, mamy do dyspozycji przestrzen reszt [1,22] teraz trzeba to jakos sensowanie zawezyc i poszukac odpowiedniego x. Tu jest wiecej zabawy niz liczenia
-
max
- Użytkownik
- Posty: 3306
- Rejestracja: 10 gru 2005, o 17:48
- Płeć: Mężczyzna
- Lokalizacja: Lebendigentanz
- Podziękował: 37 razy
- Pomógł: 778 razy
Obliczanie równania modulo.
W miarę efektywnym sposobem jest użycie rozszerzonego algorytmu euklidesa do obliczenia \(\displaystyle{ 23^{-1}}\) modulo 26. Tzn z tych równości co mamy wypisane powyżej jest:
\(\displaystyle{ 1 = 3 - 2 = 3 - (23 - 7\cdot 3) = 26 - 23 - (23 - 7\cdot (26-23))\equiv -23-23+7\cdot (-23)\equiv -9\cdot 23\equiv 17\cdot 23 od{26}}\)
Czyli mnożąc nasze równanie stronami przez 17 dostajemy \(\displaystyle{ x\equiv 9\cdot 17 od{26}}\) czyli \(\displaystyle{ x\equiv 23\pmod{26}}\)
\(\displaystyle{ 1 = 3 - 2 = 3 - (23 - 7\cdot 3) = 26 - 23 - (23 - 7\cdot (26-23))\equiv -23-23+7\cdot (-23)\equiv -9\cdot 23\equiv 17\cdot 23 od{26}}\)
Czyli mnożąc nasze równanie stronami przez 17 dostajemy \(\displaystyle{ x\equiv 9\cdot 17 od{26}}\) czyli \(\displaystyle{ x\equiv 23\pmod{26}}\)