  |
|
| ° Forum ° Odpowiedz ° Rejestracja ° Szukaj ° | |
| samochody ciężarowe ° Auto giełda ° Sprzedam motocykle ° |
|
|
| ° Forum ° Odpowiedz ° Rejestracja ° Szukaj ° | |
| samochody ciężarowe ° Auto giełda ° Sprzedam motocykle ° |
 |
Matma / liczby pierwsze |
| << . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10 . >> |
| Autor | Wiadomość |
| Eugeniusz Jakubas
|
Posted: 27 Mar 2001 10:55:38 [ ... ] Jesli ktos zna dobrze od strony praktycznej działanie sita
Pozdrowienia. Optymista Na stronie http://www.szkoly.edu.pl/~ejakubas/pr-pascal/teksty.htm znajduje się tekst źródłowy w Pascalu sita Eratostenesa. Pozdrawiam Eugeniusz J. |
| Michal Misiurewicz
|
Posted: 27 Mar 2001 15:20:06 Jesli ktos zna dobrze od strony praktycznej działanie sita Eratostenesa
oraz inne sita stosowane w teorii liczb to będę wdzięczny za szczegolowy opis tych algorytmów. Praktycznie sprawdzone: za pomoca kartki papieru i dlugopisu mozna kazda liczbe 6-cyfrowa rozlozyc na czynniki pierwsze w ciagu godziny, jesli robia to 2 osoby. Jedna osoba stosuje sito do znajdywania kolejnych liczb pierwszych, druga sprawdza podzielnosc. Pozdrowienia, Michal ***************************** Michal Misiurewicz http://www.math.iupui.edu/~mmisiure/ |
| Marek Szyjewski
|
Posted: 3 Kwi 2001 14:22:59 On Mon, 26 Mar 2001 22:36:50 +0200, "Kaczor" [ciach] Czołem grupie liczby pierwsze
W Dictionary of matematics Collinsa pod redakcjš E.J Borowski & J.M Borwein znalazlem następujaca informacje o sicie Eratostenesa: Algorytm ktory uzyskuje wszystkie liczby pierwsze, mniejsze niz dowolna liczba całkowita (integer) przez usuwanie ( by deleting) ze zbioru wszystkich liczb mniejszych od n, bedacych wielokrotnosciami liczb pierwszych kolejno az do pierwiastka z n. Dla przykładu ,aby okreslic ze liczba 1987 jest pierwsza ,potrzeba jedynie sprawdzic ( check) ze jest ona niepodzielna przez 3,5,7,11,13,17,19,23,29,31,37,41,i 43. Sito Eratostenesa m. in. podaje te liczby pierwsze, ktore trzeba by sprawdzic (to te, ktore pozostaja po "deleting"). Jesli 1987 jest pierwsza, to zostaje "undeleted" po 13 krokach, w ktorych kolejno wyznacza sie liczby pierwsze nie przekraczajace [sqrt(1987)] = 44 krokach; jesli jest zlozona, to bedzie "deleted" nie pozniej, niz w 13 krokach. Wiele innych wyrafinowanych
(sophisticated ) sit jest uzywane w teorii liczb. Tyle w slowniku. Jeli w algorytmie sita Eratostenesa, deleting = check, jak w podanym przykladzie, to istnieje mozliwosc istotnego usprawnienia algorytmu. ???? Czy chcesz powiedziec: "jesli to, co co udalo mi sie zrozumiec z lakonicznego opisu jest prawda, to znam lepszy sposob"? Do wykreslania wielokrotnosci danej liczby p (o ktorej z poprzednich krokow wiadomo, ze jest liczba pierwsza) nie jest potrzebne zadne check, tylko odlicznie do p. Zdanie o sprawdzaniu, ze 1987 jest niepodzielna przez 2,3,...,43 nie okresla kroku algorytmu, a wyjasnia jego punkt zatrzymania: gdy widac, ze nastepna liczba pierwsza bedzie wieksza od sqrt(1987), czyli po 13 krokach, nie trzeba dalej sprawdzac, jesli intersuje nas tylko liczba 1987. Być
moze jest to juz zrobione w bardziej wyrafinowanych sitach o których wspomina poradnik, ale ich nie przedstawia. Metody sita: malego sita, wielkiego sita, sita Selberga nie sa algorytmami sprawdzania pierwszosci, a metodami przyblizonego zliczania liczby liczb pierwszych (czy innych liczb o okreslonych wlasnosciach multyplikatywnych) w pewnych zbiorach (np. przedzialach (1,n), (n,2n) jako funkcja n, itd.). Minimum informacji o tych metodach mozna znalezc w podreczniku Wl. Narkiewicza "Teoria liczb" (wyd. 2 - PWN, Warszawa 1990) na stronach 152-180. Do powazniejszego startu w metodach sita obowiazkowa byla monografia Richerta i Halberstama "Sieve methods" (Ac. Press 1974). Z metod badania pierwszosci/znajdowania rozkladu na czynniki slowo "sito" - poza sitem Eratostenesa, wystepuje w nazwie metody sita kwadratowego (sita cial liczb algebraicznych stopnia 2), uzytej w hucznie opisywanym przez prase Wielkim Zlamaniu z 1994 i metoda sitra cial liczb algebraicznych (bez ograniczenia stopnia) - uzyta w Wielkim Zlamaniu z 1996. Jesli ktos zna dobrze od strony praktycznej działanie sita Eratostenesa
oraz inne sita stosowane w teorii liczb to będę wdzięczny za szczegolowy opis tych algorytmów. Dzalanie sita Eratostenesa opisane jest szczegolowo w co drugiej z ksiazek popularno-naukowych z matematyki dla uczniow szkol podstawowych. Mam opory z ujawnieniem juz w tej chwili koncepcji algorytmu z dwóch powodów
: - po pierwsze jesli jest znany to po co pchac sie na afisz. - jesli nie jest znany w tej wersji na ktora mam pomysl ,to powstaje problem odpowiedzialnoci za tych zdolnych, ktorym przyjdzie ochota wykorzystac go do lamania szyfrow i wchodzenia tam gdzie nie powinni. Tak wiec poczekajmy. Dostęp do algorytmu uzyskaja ci, ktorzy pomoga ustalic stan istniejacy, przekonajš mnie o poczuciu odpowiedzialnoci, i włacza sie w oprogramowanie i testowanie algorytmu. Pozdrowienia. Optymista To bardzo optymistyczne: zwiezly opis to dla Ciebie za malo, zeby odtworzyc algorytm znany powszechnie i od stuleci, ale to, co przy takiej znajomosci zagadnienia wymyslisz, mogloby posluzyc do lamania szyfrow... Z powazaniem Marek Szyjewski My, samotnicy, powinnismy trzymac sie razem! |
| Marek Szyjewski
|
Posted: 3 Kwi 2001 14:24:45 On Wed, 21 Mar 2001 20:45:42 +0100, "Eugeniusz Jakubas" [ciach] Chyba nie o to chodziło "Kaczorowi". Jeśli to wszystko takie proste i jawne to podaj jakąś liczbę pierwszą większą od największej znanej obecnie liczby pierwszej 2^6972593-1. Pozdrawiam Eugeniusz J. Jak tylko podasz mi spis wszystkich liczb pierwszych do 2^6972593-1 - wystarczy je wstawic do wzoru. Z powazaniem Marek Szyjewski My, samotnicy, powinnismy trzymac sie razem! |
| Mariusz Kruk
|
Posted: 3 Kwi 2001 14:27:39 W dniu Tue, 03 Apr 2001 14:24:45 GMT, osoba określana zwykle jako Marek Szyjewski pozwoliła sobie popełnić co następuje: Chyba nie o to chodziło "Kaczorowi". Jeśli to wszystko takie proste i jawne
to podaj jakąś liczbę pierwszą większą od największej znanej obecnie liczby pierwszej 2^6972593-1. Jak tylko podasz mi spis wszystkich liczb pierwszych do 2^6972593-1 - wystarczy je wstawic do wzoru. Ależ cóż za problem (poza czasem) wygenerować je ? Pozdrawiam |
| Marek Szyjewski
|
Posted: 3 Kwi 2001 14:38:03 On Thu, 22 Mar 2001 22:03:10 +0100, "Eugeniusz Jakubas" [ciach] Owszem, nie szuka się dowolnie wielkich liczb pierwszych do szyfrowania RSA, wystarczą około 100 cyfrowe, ale przepis (wzór, algorytm), który dawałby natychmiast liczby pierwsze dowolnej wielkości bardzo by się przydał. Taki algorytm ma w zanadrzu "Kaczor", ale jeszcze go nie ogłasza tylko sonduje co wiadomo na ten temat. Pozdrawiam Eugeniusz J. Nie. System RSA z iloczynem dwoch liczb pierwszych, majacym 130 cyfr, zostal zlamany w ciagu okolo roku - od wrzesnia 1995 do 10 kwietnia 1996. Wobec tego zaczeto (poczatkowo) uzywac 300-cyfrowych iloczynow dwoch liczb pierwszych. Problem polegal na przeszacowaniu stalych, wystepujacych w ocenach czasu pracy metod rozkladu. Reklamujac swoj system z kluczem publicznym Rivest, Shamir i Adlemann oceniali czas, potrzebny na zlamanie systemu ze 130-cyfrowym kluczem na setki miliardow lat. Pomylili sie w ten sposob o 11 rzedow wielkosci, z czego tylko kilka przypadalo na wydajne metody znajdowania rozkladu, reszta - na arbitralnie oceny stalych. I stad ten szum wpkol wielkich liczb pierwszych - aby przekonac potencjalnych nabywcow do bezpieczenstwa systemu, trzeba im powiedziec o kilkusetcyfrowych czy majacych kilka tysiecy cyfr liczbach pierwszych. Z powazaniem Marek Szyjewski My, samotnicy, powinnismy trzymac sie razem! |
| J.F.
|
Posted: 4 Kwi 2001 02:11:32 On Wed, 21 Mar 2001 20:45:42 +0100, "Eugeniusz Jakubas"
Chyba nie o to chodziło "Kaczorowi". Jeśli to wszystko takie proste i jawne
to podaj jakąś liczbę pierwszą większą od największej znanej obecnie liczby pierwszej 2^6972593-1. Jak tylko podasz mi spis wszystkich liczb pierwszych do 2^6972593-1 - wystarczy je wstawic do wzoru. Eee, Marku - jakiego wzoru ? Przeciez to juz bylo: 2*3*5*7*11*13+1 = 30031 = 59*509 :-) J. |
| << . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10 . >> |