Algebra, zadanie nr 5152

Autor	Zadanie / Rozwiązanie
vbnmk987 postów: 5	2017-01-13 11:33:14 Witam mam problem z zadaniem. Za pomocą testu Millera-Rabina udowodnić z prawdopodobieństwem 5/16 udowodnić, że liczba 11 jest liczbą pierwszą.

tumor postów: 8070	2017-01-13 12:03:29 $n=11$ $n-1=10=2^1*5$ przyjmijmy s=1, d=5 Wybieramy losowe a ze zbioru $\{1,2,..,n-1\}$, moja zielona rpgowa kostka pokazała a=4. Sprawdzamy czy $a^d \equiv 1 (mod n)$ (odpowiedź brzmi tak) Zatem 11 jest prawdopodobnie pierwsza (z prawdopodobieństwem $\frac{3}{4}$) Dla zwiększenia prawdopodobieństwa losujemy nowe a. Kostka mówi a=6, no to mam więcej liczenia. Sprawdzamy $6^5mod11=1$ (nie) wobec tego musimy sprawdzić $a^{2^rd}\equiv -1 (mod n)$ dla $r\in Z_s=\{0,...,s-1\}$, Dla r=0 odpowiedź brzmi tak, wobec tego 11 prawdopodobnie pierwsza (teraz już z p-em $\frac{15}{16}$) Wiadomość była modyfikowana 2017-01-15 16:10:40 przez tumor

vbnmk987 postów: 5	2017-01-14 13:24:59 Ciągle mam problem ze zrozumieniem tego zadania. 1. Skąd się bierze 3/4 jako wartość prawdopodobieństwa? 2. Co to jest r?(i w ogóle nie rozumiem tego algorytmu?)

tumor postów: 8070	2017-01-14 14:46:11 Jakbym miał taki przycisk, że nacisnę, a ludzie rozumieją, to bym go naciskał. Algorytm został zapewne podany na wykładzie wraz z oszacowaniem, jakie daje prawdopodobieństwo sukcesu (błąd polega tu na uznaniu za pierwszą liczby złożonej). a,n,r,d,s to literki alfabetu, których użyłem. Mogłem użyć innych. Nie wiem, jakich użyliście na wykładzie. Algorytm polega na sprawdzeniu pewnych warunków. W niektórych przypadkach odpowiedź dostajemy szybciej, w innych przypadkach później. Taki los.

vbnmk987 postów: 5	2017-01-15 13:02:35 Ok, słuchaj gdybym umiał to zadanie zrobić i gdyby wykłady mi wystarczały, żeby to zadanie zrozumieć, to bym nie wystawiał postów na forum matematycznym ale sytuacja jest taka, że jestem na studiach zaocznych. Mamy w planie raptem 12 godzin zajęć z kryptologii z czego pierwsze 3 upłynęły na szyfrach klasycznych(szyfr cezara,playfair'a itp)a ostatnie trzy to mają być zaliczenia. W dodatku wykładowca jest pochodzenia ukraińskiego więc czasem trudno się z nim porozumieć. Zatem proszę wytłumacz mi to jakoś łopatologicznie, bo tego nie rozumiem, no czegoś mi brakuje???

tumor postów: 8070	2017-01-15 16:10:05 Słucham. Ja Ci to zadanie zrobiłem. Między mną i forum wszystko gra. Problem pojawia się między Tobą i zrozumieniem tekstu i naprawdę, jeśli masz problem jakiś z tymi studiami zaocznymi, to je rzuć, bo nie jest sensownym wyjaśnieniem, że skoro jesteś na zaocznych, to internet ma Cię za darmo nauczyć i jeszcze Ci kupić rower. Algorytm polega na sprawdzeniu paru warunków. Czy $a^d=1(mod n)$ oraz czy dla jakiegoś r jest $a^{2^rd}=-1(mod n)$. Zależnie od wyników sprawdzania można w którymś momencie przestać sprawdzać albo idziemy ze sprawdzaniem do końca. Algorytm masz opisany w notatkach, masz opisany w internecie i naprawdę to, że z jednej strony internetowej skopiuję Ci go na inną stronę internetową nie poprawi sytuacji. Natomiast jeśli wykażesz się jakąś pracowitością i chęcią czytania tego algorytmu i wykonywania krok po kroku, to wtedy są szanse na sukces. Zadałeś dwa pytania. Pierwsze jest o wartość prawdopodobieństwa. Nie znam dowodu tego oszacowania, ale bierze się z własności liczb naturalnych. Pytanie, co to jest r albo co to jest u zawsze prowadzi do odpowiedzi, że to literki. Począwszy od gimnazjum zapisujemy liczby za pomocą literek i jest zupełnie nieistotne, jakiej literki użyjemy, byle się nie pomyliło. W algorytmie r ma przyjmować wartości z $Z_s$.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj