Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie

Równanie kongruencyjne


  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
14 odpowiedzi w tym temacie

#1 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 04.05.2009 - 18:20

Rozwiązywałem takie zadanko, gdzie musiałem obliczyć resztę z dzielenia jednej liczby przez drugą, i doszedłem do czegoś takiego: wiem, że 2^{32} przez 111.

A więc, 2^{36}=2^{32}\cdot 16\equiv1(mod\ 111)

2^{32}\equiv x(mod\ 111)\qquad\Rightarrow\qquad 2^{32}\cdot 16\equiv 16x(mod\ 111)

Z przechodniości mamy:

16x\equiv1(mod\ 111)

Moje pytanie jest raczej oczywiste - jak obliczyć x? Czytałem trochę w internecie ... podobno trzeba skorzystać z algorytmu Euklidesa? Jeżeli tak, to w jaki sposób? No i, oczywiście ... czy jest to jedyny sposób na obliczanie tego typu równań, tzn. z zastosowaniem algorytmu Euklidesa? :)

Tomalla
  • 0
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2104 postów
1008
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 04.05.2009 - 19:01

akurat mieliśmy to niedawno na kółku kryptologicznym więc mogę ładnie rozpisać :)

chcemy znaleźć takie całkowite a, żeby zachodziła kongruencja 111 przez 16

1, a potem z pierwszej 15 czyli:

a=7 oraz k=1

:)
  • 0

#3 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 04.05.2009 - 20:02

Coś nie mogę tego załapać ... skąd się wzięły te dwie linijki:

<br />\\111=6 \cdot 16 + 15
16=15 + 1

Po pierwsze, dlaczego dzielimy 111 przez 16? Po drugie, co oznacza druga linijka, tzn. 16=15+1? Co akurat tutaj robimy?

PS. "Kółko kryptologiczne"? Brzmi poważnie :)
  • 0
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#4 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2104 postów
1008
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 04.05.2009 - 20:12

te dwie linijki to algorytm Euklidesa, o tym znajdziesz dużo w internecie :)

a Kółko Kryptologiczne jest super, rok temu Enigmę złamaliśmy, w tym roku szyfry afiniczne robimy :)
  • 0

#5 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 04.05.2009 - 20:15

Z tego, co znalazłem w Internecie, to algorytm Euklidesa służy do obliczania NWD dwóch liczb. Gdzie tutaj jest taka potrzeba?

To kółko to super sprawa :)
  • 0
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#6 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2104 postów
1008
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 04.05.2009 - 20:47

Taka liczba istnieje (dlaczego?).

nie wiem czy odpowiedziałeś sobie na pytanie w nawiasie :)

a i zapomniałem wspomnieć że korzystam ze znanego twierdzenia (ono jest samo w sobie ciekawe), że dla danych liczb całkowitych x,y istnieją liczby całkowite a,b takie że a i b służy algorytm Euklidesa jak się go weźmie od końca

to z tego co pamiętam jest też w "Teorii Liczb" Sierpińskiego szerzej omówione :)
  • 0

#7 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 04.05.2009 - 21:20

Aha, już jestem na dobrej drodze do zrozumienia tematu :)

Mam 16a-111k=1. Czyli NWD(16,111)|1 . Rozpisując to za pomocą algorytmu Euklidesa otrzymuję kolejno:

19=\dots

... eee, i co dalej? :) Za wcześnie się kurcze cieszyłem :) ... czy może zły przykład dałem?
  • 0
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#8 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2104 postów
1008
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 04.05.2009 - 21:41

nie no dobrze było, umknęło Ci tylko, że

19=19 \cdot 1 = 19 \cdot (3-2)=19 \cdot(14 \cdot 3 - 41)= -19 \cdot 41 + 266 \cdot 3

:)

[edit] poprawka po poniższej uwadze kolegi :)
  • 0

#9 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 05.05.2009 - 19:27

Nie umknęło, ja po prostu nie wiedziałem że tak trzeba zrobić :)

Czy tam nie powinno być 14*3-41?

Czyli reasumując, jaka jest mniej więcej zasada działania pod koniec? Próbujemy jakoś wsadzić te liczby, które wyliczyliśmy za pomocą algorytmu Euklidesa? Jeszcze nie potrafię wychwycić podobieństwa między poprzednim, a tym przykładem ... Wytłumaczysz?

... a może trzeba tą liczbę po prostu jakoś rozłożyć na czynniki czy coś takiego?
  • 0
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#10 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2104 postów
1008
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 05.05.2009 - 19:44

Przy danych liczbach całkowitych NWD(a,m)=1 rozwiązanie dowolnej kongruencji a oraz m i potem wyznaczasz y tym sposobem który opisalem powyżej (tzn idąc w algorytmie euklidesa od końca). Dam może kolejny przykład. Chcemy rozwiązać 32=17+15
17=15+2
17 czyli 17 jeśli wolimy dodatnie) :)

A i udowodnij to co napisałem w pierwszym zdaniu posta bo to wcale nie jest takie oczywiste a znacznie ułatwia sprawę :)
  • 0

#11 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 05.05.2009 - 21:36

To, że nie jest to oczywiste, to się zgadzam ... ale żeby to udowodnić ... jak? Nawet nie wiem od czego zacząć -.-' Może jakaś wskazówka na początek?

Czyli jak by wyglądało to przekształcenie dla mojego wcześniejszego przykładu: 3x\equiv19(mod\ 41)?
  • 0
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#12 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2104 postów
1008
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 05.05.2009 - 21:57

wyglądałoby tak że najpierw chcemy rozwiązać y=14 (możemy łatwo sprawdzić: 14 (możemy, bo...) i mamy y to potem możemy kongruencję y i dostajemy y będzie względnie pierwszy z m, ale wydaje mi się że tak... :)
  • 0

#13 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 06.05.2009 - 19:14

Wszystko teraz jasne :D Mam natomiast dwa zasadnicze pytania:

1. Zastanawia mnie, dlaczego przy mnożeniu kongruencji przez jakąś stałą musi być względnie pierwsza z modulo. Proszę, podaj jakiś przykład, gdzie trzeba koniecznie to uwzględnić bo wychodzą wtedy błędne wyniki:

3x-9k=1

1=?

Z drugiej strony pojawia się pytanie - czy każde równanie kongruencyjne ma rozwiązanie? Następny przykład:

5x\equiv 3(mod\ 10)

Kolejne wartości, tzn. 5, 10, 15, 20 ... mogą mieć resztę jedynie 0 lub 5 - nie natomiast 3. Taki przykład chyba nie jest do rozwiązania ... tak jak każdy, gdzie liczby a i m nie są względnie pierwsze ... czy może coś źle interpretuję?
  • 0
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=

#14 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2104 postów
1008
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 06.05.2009 - 19:40

1. Zastanawia mnie, dlaczego przy mnożeniu kongruencji przez jakąś stałą musi być względnie pierwsza z modulo. Proszę, podaj jakiś przykład, gdzie trzeba koniecznie to uwzględnić bo wychodzą wtedy błędne wyniki:

jak napiszesz sobie kongruencję typu 8 i otrzymamy:

3 czyli zonk :D

Przykład:

3x\equiv1(mod\ 9)
(...)

Taki przykład chyba nie jest do rozwiązania ... tak jak każdy, gdzie liczby a i m nie są względnie pierwsze ... czy może coś źle interpretuję?


Gdy NWD(a,m) \neq 1 wtedy albo w ogóle kongruencja nie ma rozwiązań (np jak w Twoim przykładzie) albo rozwiązań jest kilka np
4x \equiv 0 (mod \ 8) :D
  • 0

#15 Tomalla

Tomalla

    =-.-= Spatter Guy =-.-=

  • $Jr Admin
  • Redaktor
  • 3211 postów
1037
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 07.05.2009 - 20:46

Czyli, kiedy liczby a i m nie są względnie pierwsze, mamy trochę nieporęczną sytuację :D Jak będę miał kłopot z takim równaniem, to dam znać :rolleyes:

I ponownie, naprawdę dzięki za wytłumaczenie tego ... i owego ... i anielską cierpliwość do mojej osoby :D
  • 0
________
Nie rozwiązuję zadań poprzez PMy!
Nie zaśmiecać mi skrzynki odbiorczej wiadomościami typu "pomóż mi w następnym zadaniu" etc.
Tego typu wiadomości będę po prostu ignorował i od razu usuwał.


=-.-= ToMaLlA - General Modder in games with QuaKe 3 and DooM III EnGiNes =-.-=