Mam problem.
Poszukujemy określonego \(\displaystyle{ k}\) dla którego równanie:
\(\displaystyle{ (a \cdot k) \% z = y}\)
ma określoną wartość (tj. \(\displaystyle{ y}\)).
\(\displaystyle{ a}\), \(\displaystyle{ y}\) i \(\displaystyle{ z}\) jest dane. Szukamy \(\displaystyle{ k}\).
Dla przykładu niech
\(\displaystyle{ a = 3}\), \(\displaystyle{ y = 2}\) i \(\displaystyle{ z = 11}\)
Prawidłowy wynik otrzymamy dla \(\displaystyle{ k = 8}\):
\(\displaystyle{ (3 \cdot 8) \% 11 = 2}\)
Czy istnieje jakiś sposób aby szybko obliczyć \(\displaystyle{ k}\) mając komplet pozostałych danych?
Mi przychodzi do głowy tylko sposób trywlalny gdzie obliczamy wszystkie możliwości modulo i po drodze szukamy potrzebnego rezultatu. Niestety w tym przypadku musimy obliczyć dla powyższego przypadku sporo równań (k od 1 do 10). Dla liczb wielkości \(\displaystyle{ z = 10^{100}}\) jest to już niewykonalne na komputerze.
Może ma ktoś jakiś pomysł?
Nietypowe równanie modulo i jego poszukiwany parametr
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Nietypowe równanie modulo i jego poszukiwany parametr
Jeżeli \(\displaystyle{ \NWD(a,z)=1}\), to za pomocą rozszerzonego algorytmu Euklidesa możesz znaleźć
element odwrotny do \(\displaystyle{ a}\) względem mnożenia modulo \(\displaystyle{ z}\) (tj. takie działanie: normalnie mnożymy liczby, a potem bierzemy resztę z dzielenia tego iloczynu przez \(\displaystyle{ z}\)).
Jeżeli \(\displaystyle{ \NWD(a,z)=r>1}\), to:
-jeśli \(\displaystyle{ r}\) dzieli \(\displaystyle{ y}\), to dzielimy kongruencję stronami;
w przeciwnym przypadku kongruencja nie ma rozwiązań.
Przedstawię przykład na podstawie tamtego konkretnego zadanka:
\(\displaystyle{ (3\cdot k)\%11=2}\)
Mamy (alogrytm Euklidesa):
\(\displaystyle{ 11=3\cdot 3+2\\3=1\cdot 2+1}\)
zatem \(\displaystyle{ 1=3-1\cdot 2=3-1\cdot(11-3\cdot 3)=4\cdot 3-1\cdot 11}\), więc
\(\displaystyle{ 11+1={\red 4}\cdot 3 \equiv 1_pmod{11}}\).
Zaczerwienione to jest nasz element odwrotny. Mnożymy stronami kongruencję przez tenże element
i redukujemy wielokrotności \(\displaystyle{ 11}\) (bo nie mają one znaczenia dla reszty z dzielenia przez 11):
\(\displaystyle{ (4\cdot 3\cdot k)\%11=8\\ (11k+k)\%11=8\\k\%11=8}\),
czyli na przykład \(\displaystyle{ k=8}\) jest rozwiązaniem (rozwiązań jest nieskończenie wiele i każde jest postaci \(\displaystyle{ 11l+8}\) dla pewnego l całkowitego).
Aha, jeszcze problem może być w implementacji tego, bo informatyczne \(\displaystyle{ \%}\) to nie dokładnie to samo, co normalne działanie na resztach, bo jeszcze mogą być dopuszczone reszty ujemne. Dlatego pewnie lepiej użyć np. funkcji fmod z biblioteki cmath.-- 22 cze 2016, o 18:07 --lol, to sobie od razu założyłem, że jeśli ktoś programuje, to na pewno w C++. Dobra, lepiej pominąć tę moją uwagę, bo nie znam się na programowaniu i mogła ona być bardzo głupia...
element odwrotny do \(\displaystyle{ a}\) względem mnożenia modulo \(\displaystyle{ z}\) (tj. takie działanie: normalnie mnożymy liczby, a potem bierzemy resztę z dzielenia tego iloczynu przez \(\displaystyle{ z}\)).
Jeżeli \(\displaystyle{ \NWD(a,z)=r>1}\), to:
-jeśli \(\displaystyle{ r}\) dzieli \(\displaystyle{ y}\), to dzielimy kongruencję stronami;
w przeciwnym przypadku kongruencja nie ma rozwiązań.
Przedstawię przykład na podstawie tamtego konkretnego zadanka:
\(\displaystyle{ (3\cdot k)\%11=2}\)
Mamy (alogrytm Euklidesa):
\(\displaystyle{ 11=3\cdot 3+2\\3=1\cdot 2+1}\)
zatem \(\displaystyle{ 1=3-1\cdot 2=3-1\cdot(11-3\cdot 3)=4\cdot 3-1\cdot 11}\), więc
\(\displaystyle{ 11+1={\red 4}\cdot 3 \equiv 1_pmod{11}}\).
Zaczerwienione to jest nasz element odwrotny. Mnożymy stronami kongruencję przez tenże element
i redukujemy wielokrotności \(\displaystyle{ 11}\) (bo nie mają one znaczenia dla reszty z dzielenia przez 11):
\(\displaystyle{ (4\cdot 3\cdot k)\%11=8\\ (11k+k)\%11=8\\k\%11=8}\),
czyli na przykład \(\displaystyle{ k=8}\) jest rozwiązaniem (rozwiązań jest nieskończenie wiele i każde jest postaci \(\displaystyle{ 11l+8}\) dla pewnego l całkowitego).
Aha, jeszcze problem może być w implementacji tego, bo informatyczne \(\displaystyle{ \%}\) to nie dokładnie to samo, co normalne działanie na resztach, bo jeszcze mogą być dopuszczone reszty ujemne. Dlatego pewnie lepiej użyć np. funkcji fmod z biblioteki cmath.-- 22 cze 2016, o 18:07 --lol, to sobie od razu założyłem, że jeśli ktoś programuje, to na pewno w C++. Dobra, lepiej pominąć tę moją uwagę, bo nie znam się na programowaniu i mogła ona być bardzo głupia...
-
Morfeo
- Użytkownik
- Posty: 32
- Rejestracja: 8 wrz 2015, o 19:21
- Płeć: Mężczyzna
- Lokalizacja: z daleka
- Podziękował: 1 raz
Nietypowe równanie modulo i jego poszukiwany parametr
Nie szkodzi W sumie to dość słusznie założyłeśPremislav pisze:lol, to sobie od razu założyłem, że jeśli ktoś programuje, to na pewno w C++. Dobra, lepiej pominąć tę moją uwagę, bo nie znam się na programowaniu i mogła ona być bardzo głupia...
Mam jeszcze jedno pytanie.
Mamy hipotetyczne równanie: \(\displaystyle{ 2^{b} \% b == z}\).
Przyjmijmy, że znamy \(\displaystyle{ z}\) oraz \(\displaystyle{ b}\). Czyli wszystko! Chcemy wiedzieć tylko i wyłącznie czy powyższe równanie jest prawdziwe.
Nie chcę stosować potęgowania modulo - szukam jakiejś szybszej metody. Nie muszę znać dokładnej wartości \(\displaystyle{ 2^{b} \% k}\). Chcę tylko wiedzieć czy wynosi ona \(\displaystyle{ z}\).
Da się to zrobić bez trywialnego potęgowania modulo?