Tw Fermata

pcmaniak89 · Post autor: **pcmaniak89** » 13 cze 2011, o 17:34

Mam problem z zadankiem:

Za pomocą testu Fermata z prawdopodobieństwem 7/8 udowodnić, że liczba 11 jest liczbą pierwszą.

Nie do końca rozumiem jak mam udowodnić z prawdopodobieństwem 7/8.
Korzystam z równania z wiki:

i jak ma wyglądać dowód, mam sobie wybrać 8 liczb "losowo" i sprawdzić czy jest spełnione to równanie z wiki i jeśli w 7 przypadkach jest ok, to znaczy że jest pierwsza z prawdopodobieństwem 7/8?
A nie jest tak, że jak znajdzie się przypadek, że jakaś liczba nie spełnia równania to nie jest pierwsza?

prosiłbym o jakieś podpowiedzi:)-- 13 cze 2011, o 17:35 --

adek05 · Post autor: **adek05** » 13 cze 2011, o 17:45

Test Fermata działa z prawdopodobieństem \(\displaystyle{ \frac{1}{2}}\). Jeżeli odpalisz go 3 razy z różnymi losowymi liczbami pierwszymi i weźmiesz koniunkcje wyników, to błąd dostaniesz z prawdopodobieństwem \(\displaystyle{ \frac{1}{8}}\).

pcmaniak89 · Post autor: **pcmaniak89** » 13 cze 2011, o 19:52

czyli jeśli chce sprawdzić czy dana liczba jest pierwsza, losuję jedną liczbę podstawiam do wzoru z tw
i wtedy mogę stwierdzić, że na 50% jest to liczba NIE pierwsza?

losując dwie liczby mogę stwierdzić w 75%, że jest to liczba pierwsza itd.?

czy raczej to się tyczy dowolnej liczby liczb?
bo nie jestem pewien czy to prawdopodobieństwo jest zawsze takie same w zależności czy w jednym uruchomieniu tw fermata wybiorę jedną czy więcej liczb.

adek05 · Post autor: **adek05** » 13 cze 2011, o 20:16

Testy są niezależne, więc prawdopodobieństwa się mnoży. W jakiejś sensownej książce(Cormen?) powinieneś znaleźć dowód tego faktu, że to tak działa

pcmaniak89 · Post autor: **pcmaniak89** » 13 cze 2011, o 21:05

tak jak parze na treść zadania to chyba ten test może mieć różne prawdopodobieństwa, uzależnione od liczby wybieranych liczb i podstawionych do równania z testu fermata.

Ja mam w zadanie test z prawdopodobieństwem 7/8 czyli ja mnożę przez siebie nie 1/2 a 7/8
ale nadal nie wiem jak mam udowodnić że 11 jest liczbą pierwszą bo jeśli po 2 testach fermata będę miał prawdopodobieństwo 63/64 że jest to liczba pierwsza ale nigdy nie osiągnę pełnej pewności przecież..

Zordon · Post autor: **Zordon** » 13 cze 2011, o 21:06

Test Fermata dla wiekszosci liczb działa rzeczywiście z pr \(\displaystyle{ 0.5}\). No ale są złośliwe przypadki, dla których nie działa w ogóle.

adek05 · Post autor: **adek05** » 13 cze 2011, o 21:26

pcmaniak89, istotnie, ale zauważ, że w ten sposób możesz dojść do dowolnie małego prawdopodobieństwa, że Twój algorytm się pomylił, ale jeżeli tak, to możesz dojść do mniejszego niż to, że w Ziemię za sekundę uderzy meteoryt ewentualne, że w czasie odpalania algorytmu na komputerze jakaś cząstka zmieni Ci bit pamięci, na którym operuje Twój algorytm, trzeba Ci więcej?
EDIT: albo że trafisz szóstke w totka

pcmaniak89 · Post autor: **pcmaniak89** » 13 cze 2011, o 21:39

Zordon pisze:Test Fermata dla wiekszosci liczb działa rzeczywiście z pr \(\displaystyle{ 0.5}\). No ale są złośliwe przypadki, dla których nie działa w ogóle.

czytałem o tym, że oczywiście są takie liczby nie neguje,
nie przeczę również, że dla większości liczb prawdopodobieństwo jest 0.5
ale tu chodzi bardziej o to, że to prawdopodobieństwo jest 7/8 i dla takiego prawdopodobieństwa muszę udowodnić to co jest w zadaniu
chodzi bardziej o dowód

adek05 pisze:pcmaniak89, istotnie, ale zauważ, że w ten sposób możesz dojść do dowolnie małego prawdopodobieństwa, że Twój algorytm się pomylił, ale jeżeli tak, to możesz dojść do mniejszego niż to, że w Ziemię za sekundę uderzy meteoryt ewentualne, że w czasie odpalania algorytmu na komputerze jakaś cząstka zmieni Ci bit pamięci, na którym operuje Twój algorytm, trzeba Ci więcej?
EDIT: albo że trafisz szóstke w totka

no dobra, dowód rozpocznę, od wybrania dostatecznie małego \(\displaystyle{ \epsilon}\) które będzie oznaczać błąd.
bardziej chce się upewnić, że nie da się udowodnić w 100% że coś jest lub nie jest liczbą pierwszą stosując tw fermata, dobrze rozumiem?

adek05 · Post autor: **adek05** » 13 cze 2011, o 21:56

Tak, 100% pewności ten test nie daje. Jak chcesz z pr. \(\displaystyle{ \frac{7}{8}}\) to wystarczy wypróbować dla \(\displaystyle{ 3}\) losowych liczb pierwszych. Wtedy prawdopodobieństwo tego, że się pomyli za każdym razem będzie \(\displaystyle{ \frac{1}{8}}\)

pcmaniak89 · Post autor: **pcmaniak89** » 13 cze 2011, o 22:15

dzięki za pomoc

norwimaj · Post autor: **norwimaj** » 13 cze 2011, o 22:43

pcmaniak89 pisze: bardziej chce się upewnić, że nie da się udowodnić w 100% że coś jest lub nie jest liczbą pierwszą stosując tw fermata, dobrze rozumiem?

Często da się udowodnić za pomocą testu Fermata, że coś nie jest liczbą pierwszą, natomiast nie da się za pomocą tego testu udowodnić, że coś jest liczbą pierwszą.

Z tymi prawdopodobieństwami, to nie wyrażacie się zbyt precyzyjnie. Liczba \(\displaystyle{ 11}\) albo jest pierwsza, albo nie jest. Nie ma tu żadnej losowości. Pewnie chcecie powiedzieć coś bardziej skomplikowanego, np. jeśli losujemy liczbę \(\displaystyle{ n}\) (z jakimś rozkładem prawdopodobieństwa), to prawdopodobieństwo że liczba jest pierwsza pod warunkiem, że test Fermata da wynik pozytywny, jest równe \(\displaystyle{ \frac{1}{2}}\).

Natomiast jeśli mamy już ustaloną liczbę \(\displaystyle{ n}\), to sytuacja jest trochę inna. W szczególności dla \(\displaystyle{ n=11}\) prawdopodobieństwo że test Fermata się pomyli, jest zerowe.

adek05 · Post autor: **adek05** » 13 cze 2011, o 23:08

No tak, ale jak już wziąć liczbę \(\displaystyle{ 2}\)-pseudopierwszą to prawdopodobieństwo jest niezerowe i te szczególne liczby Carmichaela, że wynosi \(\displaystyle{ 1}\).

pcmaniak89 · Post autor: **pcmaniak89** » 14 cze 2011, o 08:44

norwimaj pisze: Natomiast jeśli mamy już ustaloną liczbę \(\displaystyle{ n}\), to sytuacja jest trochę inna. W szczególności dla \(\displaystyle{ n=11}\) prawdopodobieństwo że test Fermata się pomyli, jest zerowe.

Ty wiesz, że 11 jest liczbę pierwszą i ja wiem, ale stosując test fermata zakładamy, że tego nie wiemy.
Tak jak ktoś tu napisał to jest test z pewnym prawdopodobieństwem i pewności chyba nie będzie nigdy.

Jeżeli da się udowodnić z P=1 że 11 jest liczbą pierwszą za pomocą tego tw to chętnie zobaczę taki dowód, wtedy padnę na kolana i będę przepraszał:P

PS. Z tym padaniem to oczywiście żart

norwimaj · Post autor: **norwimaj** » 14 cze 2011, o 16:05

pcmaniak89 pisze: Ty wiesz, że 11 jest liczbę pierwszą i ja wiem, ale stosując test fermata zakładamy, że tego nie wiemy.

Nie rozumiem. Mamy liczbę \(\displaystyle{ 11}\). I co dalej? Jaką masz tu przestrzeń probabilistyczną?

Czy końcowy wniosek jest taki, że liczba \(\displaystyle{ 11}\) z prawdopodobieństwem \(\displaystyle{ \frac{7}{8}}\) jest pierwsza, z prawdopodobieństwem \(\displaystyle{ \frac{1}{20}}\) jest złożona, z prawdopodobieństwem \(\displaystyle{ \frac{1}{30}}\) jest równa \(\displaystyle{ 1}\) itd.? W moim odczuciu nie brzmi to sensownie, ale przyznaję że RP nie jest moim ulubionym działem matematyki.

pcmaniak89 pisze: Tak jak ktoś tu napisał to jest test z pewnym prawdopodobieństwem i pewności chyba nie będzie nigdy.

Pewność masz wtedy, gdy test daje wynik negatywny.

adek05 · Post autor: **adek05** » 14 cze 2011, o 16:12

norwimaj pisze:
pcmaniak89 pisze: Czy końcowy wniosek jest taki, że liczba \(\displaystyle{ 11}\) z prawdopodobieństwem \(\displaystyle{ \frac{7}{8}}\) jest pierwsza, z prawdopodobieństwem \(\displaystyle{ \frac{1}{20}}\) jest złożona, z prawdopodobieństwem \(\displaystyle{ \frac{1}{30}}\) jest równa \(\displaystyle{ 1}\) itd.? W moim odczuciu nie brzmi to sensownie, ale przyznaję że RP nie jest moim ulubionym działem matematyki..

Stosownie to nie brzmi, bo jest pierwszą albo nie. Bo tak na prawdę, to to prawdopodobieństwo jest charakterystyką wiarygodności wyniku testu w ogólnym przypadku, a nie samej liczby.