Algebra, zadanie nr 5152
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
vbnmk987 post贸w: 5 |  2017-01-13 11:33:14Witam 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