konto usunięte

Temat: Praca magisterska - potrzebna pomoc :)

Zacheusz Siedlecki:
Należy również zwrócić uwagę, że algorytmy wykorzystywane chociażby przez podany przez Ciebie PrimeGrid niewiele mają wspólnego z sitem Eratostenesa, które jest raczej licealnym przykładem testu pierwszości.

Dlaczego odnoszę wrażenie, że wypowiadasz się tylko po to żeby udowodnić że Twoja racja jest ważniejsza? (polecam "Dzień Świra" i fragment z trybuny sejmowej).

1. Nie wiem dlaczego uczepiłeś się tego sita. To algorytm z książek szkolnych i chyba to oczywiste, że jego stosowanie ma sens tylko przy małych liczbach, a mój przykład podany był w celu ułatwienia a nie utrudnienia (bo wybacz, ale rozpoczynanie od Javy w kontekście matematyki to po prostu rzucanie kłód pod nogi).
Powinno się raczej zaczynać od Matlaba, jeśli już.

2. Zakładam że autorka wątku nie ma w domu superkomputera. Dlatego napisałem o jednym komputerze. Moja wina, że nie wypowiedziałem się ściśle - największe liczby pierwsze można sprawdzić na pojedynczym komputerze PC w miarę krótkim czasie, obliczeniowo pracochłonne jest tylko ich szukanie.

3. Protokoły sieciowe nie powinny wprowadzać znaczących opóźnień. Dlatego wygenerowanie dwóch liczb pierwszych nie powinno trwać więcej niż mrugnięcie oka. Rozsądnym założeniem jest więc stosowanie heurystyk. Nikt tutaj temu nie zaprzecza.
Zacheusz Siedlecki

Zacheusz Siedlecki Senior Java
Architect, Working
Manager

Temat: Praca magisterska - potrzebna pomoc :)

Piotr Likus:
Zacheusz Siedlecki:
Należy również zwrócić uwagę, że algorytmy wykorzystywane chociażby przez podany przez Ciebie PrimeGrid niewiele mają wspólnego z sitem Eratostenesa, które jest raczej licealnym przykładem testu pierwszości.

Dlaczego odnoszę wrażenie, że wypowiadasz się tylko po to żeby udowodnić że Twoja racja jest ważniejsza? (polecam "Dzień Świra" i fragment z trybuny sejmowej).
Zgadza się - to tylko wrażenie. Mowa była o teście pierwszości dla dużych liczb. Sito Eratostenesa w żadnym przypadku nie może być użyte dla dużych liczb. Choćby w przypadku liczb jakie testuje się na co dzień na komputerach osobistych jest zupełnie nieprzydatne.
1. Nie wiem dlaczego uczepiłeś się tego sita. To algorytm z książek szkolnych i chyba to oczywiste, że jego stosowanie ma sens tylko przy małych liczbach, a mój przykład podany był w celu ułatwienia a nie utrudnienia (bo
Właśnie dlatego prostuję Twoją wypowiedź bo zamiast ułatwiać i naprowadzać na właściwy trop po prostu utrudnia ;) Mowa o dużych liczbach (takie było pytanie) - nie używamy sita - proste :)
wybacz, ale rozpoczynanie od Javy w kontekście matematyki to po prostu rzucanie kłód pod nogi).
Powinno się raczej zaczynać od Matlaba, jeśli już.
Jeśli chodzi o Javę to z tego co wiem autorka pytania miała z nią styczność i myślę, że moja odpowiedź mogła jej się na coś przydać.

największe liczby pierwsze można sprawdzić na pojedynczym komputerze PC w miarę krótkim czasie, obliczeniowo pracochłonne jest tylko ich szukanie.
Właśnie nie - jest dokładnie na odwrót - sprawdzanie jest czasochłonne :) Szukanie to w przypadku algorytmów używanych na co dzień w kryptografii codziennego użytku to po prostu losowanie. Po wylosowaniu liczby (czasem nie jest to zupełnie 'losowanie' ale z reguły nie jest zasobożerne) sprawdzamy ją czy jest liczbą pierwszą i to właśnie jest trudne. W przypadku algorytmów heurystycznych wiemy to tylko z pewnym prawdopodobieństwem błędu.

Wiele na ten temat może powiedzieć Marcin Stefaniak, który wypowiadał się w tym wątku i na testach pierwszości zna się bardzo dobrze ;)

Temat: Praca magisterska - potrzebna pomoc :)

Są różnice między szukaniem liczb pierwszych na potrzeby praktycznej kryptografii (gdzie szuka się liczb pierwszych rzędu wielkości, powiedzmy, 2^2000) a szukaniem rekordowo wielkich liczb pierwszych (gdzie najwygodniej badać liczby specjalnej postaci i odkryto, że 2^43112609-1 jest pierwsza).
Zacheusz Siedlecki

Zacheusz Siedlecki Senior Java
Architect, Working
Manager

Temat: Praca magisterska - potrzebna pomoc :)

Marcin Stefaniak:
Są różnice między szukaniem liczb pierwszych na potrzeby praktycznej kryptografii (gdzie szuka się liczb pierwszych rzędu wielkości, powiedzmy, 2^2000) a szukaniem rekordowo wielkich liczb pierwszych (gdzie najwygodniej badać liczby specjalnej postaci i odkryto, że 2^43112609-1 jest pierwsza).
Zwłaszcza, że w przypadku tych pierwszych zwykle starczy sprawdzenie pierwszości z pewnym prawdopodobieństwem a w przypadku drugich już częściej chodzi o dowiedzenie tego :)

Temat: Praca magisterska - potrzebna pomoc :)

Tak, na przykład EFF przyznaje nagrody tylko za udowodnione rekordowe liczby pierwsze. Ale i tak namierzanie kandydatów na takie rekordy jest całkiem obliczeniochłonne.

konto usunięte

Temat: Praca magisterska - potrzebna pomoc :)

Zacheusz Siedlecki:
największe liczby pierwsze można sprawdzić na pojedynczym komputerze PC w miarę krótkim czasie, obliczeniowo pracochłonne jest tylko ich szukanie.
Właśnie nie - jest dokładnie na odwrót - sprawdzanie jest czasochłonne :) Szukanie to w przypadku algorytmów używanych na co dzień w kryptografii codziennego użytku to po prostu losowanie. Po wylosowaniu liczby (czasem nie jest to zupełnie 'losowanie' ale z reguły nie jest zasobożerne) sprawdzamy ją czy jest liczbą pierwszą i to właśnie jest trudne. W przypadku algorytmów heurystycznych wiemy to tylko z pewnym prawdopodobieństwem błędu.

Mieszasz pojęcia, z tego co piszesz wnioskuje że masz jakieś pojęcie o tym co piszesz, dlatego zakładam, że specjalnie...

Są tu cztery różne tematy:
1. Test pierwszości - dowodzeniowy - o którym od początku piszę.
2. Test pierwszości - heurystyczny. Dla mnie bezużyteczny, bo na codzień nie analizuję protokołów sieciowych a test z prawdopodobieństwem 50% wykonuję w pamięci... ;)
3. Wyszukiwanie liczb pierwszych na potrzeby około-EFF - o którym pisałem. PrimeGrid jest przykładem takich wyszukiwań. Wyszukiwanie to zawiera nr 1.
4. Wyszukiwanie liczb pierwszych na potrzeby protokołów sieciowych - o którym tylko -Ty- ciągle wspominasz.
Marcin Stefaniak:
Są różnice między szukaniem liczb pierwszych na potrzeby praktycznej kryptografii (gdzie szuka się liczb pierwszych rzędu wielkości, powiedzmy, 2^2000) a szukaniem rekordowo wielkich liczb pierwszych (gdzie najwygodniej badać liczby specjalnej postaci i odkryto, że 2^43112609-1 jest pierwsza).

Z tego co mi wiadomo weryfikacja tej największej zajęła jakieś 18h przeciętnemu pecetowi. Dla jednej liczby można poczekać, ale już szukanie w tym tempie tych największych na jednym pececie to syzyfowa praca.Piotr Likus edytował(a) ten post dnia 17.03.09 o godzinie 17:10
Zacheusz Siedlecki

Zacheusz Siedlecki Senior Java
Architect, Working
Manager

Temat: Praca magisterska - potrzebna pomoc :)

Piotr Likus:
1. Test pierwszości - dowodzeniowy - o którym od początku piszę.
...
Z tego co mi wiadomo weryfikacja tej największej zajęła jakieś 18h przeciętnemu pecetowi. Dla jednej liczby można poczekać, ale już szukanie w tym tempie tych największych na jednym pececie to syzyfowa praca.

Od początku piszesz o sicie - sitem takich dużych nie 'poweryfikujesz'. Nie mam siły tłumaczyć w kółko tego samego tematu.

Jak jest z dowodzeniem pierwszości tych największych znanych liczb pierwszych na zwykłych PC może niech się Marcin wypowie.
Dla mnie EOT bo po prostu brak mi sił :)Zacheusz Siedlecki edytował(a) ten post dnia 17.03.09 o godzinie 21:17

Temat: Praca magisterska - potrzebna pomoc :)

Oj jak się tak kłócicie z niezrozumieniem, to nie wciągajcie w to innych.

Chcesz wiedzieć ile zajmie test Lucasa-Lehmera dla 2^43112609-1 na jednym PC? Strzelałbym że 180h, ale mogę się mylić. W kontekście tej dyskusji to nieistotne.
Zacheusz Siedlecki

Zacheusz Siedlecki Senior Java
Architect, Working
Manager

Temat: Praca magisterska - potrzebna pomoc :)

wow szczerze mówiąc myślałem, że znacznie dłużej
thx za odpowiedź :)

konto usunięte

Temat: Praca magisterska - potrzebna pomoc :)

Zacheusz Siedlecki:

Sito Eratostenesa w żadnym przypadku nie może być użyte dla dużych liczb. Choćby w przypadku liczb jakie testuje się na co dzień na komputerach osobistych jest zupełnie nieprzydatne.
Kiedyś z nudów, a trochę dla przypomnienia sobie Pascala popełniłem program sprawdzający - metodą sita Eratostenesa (w ulepszonej wersji jako metoda eliminacji liniowej) - wszystkie liczby z zakresu dostępnego na 64 bitach, czyli 2^63 -1. Inicjalizacja mapy bitowej trwa ok. 3-6 min., ale potem nawet szybko sprawdza. Najdłuższy czas na moim notebooku, to 40 s. No i jest to test deterministyczny.

Jeśli ktoś chce się tym pobawić, to tutaj:
http://chomikuj.pl/Mruuum/Dokumenty

Oczywiście, z punktu widzenia prawdziwej kryptografii, jest to piaskownica, bo tam używa się liczb znacznie większych, np. 100-cyfrowych.
Ale morał z tej bajki jest taki, że jak się troszkę popracuje nad algorytmem, to i ze zwykłego PC można coś tam wykrzesać.
Pozdrawiam
Zacheusz Siedlecki

Zacheusz Siedlecki Senior Java
Architect, Working
Manager

Temat: Praca magisterska - potrzebna pomoc :)

64 bity to tak jak mówisz piaskowinca, ale jeśli chodzi o PC to zaskoczyło mnie oszacowanie Marcina w związku z testem Lucasa-Lehmera. Niestety jest to tylko test pierwszości dla liczb Mersenne'a.Zacheusz Siedlecki edytował(a) ten post dnia 24.03.09 o godzinie 14:07
Małgorzata Cygańska

Małgorzata Cygańska Mobile Specialist,
MicroStrategy

Temat: Praca magisterska - potrzebna pomoc :)

Cześć.
Chciałam się zapytać, czy moglibyście mi doradzić w wyborze tematu pracy magisterskiej z kryptografii. Mój promotor również nie narzucił mi z góry konkretnego tematu.
Jestem studentką matematyki i nie chciałabym nic programować.
Z góry dziękuję.
Piotr Sus

Piotr Sus IS Senior Manager,
Desktop Engineering

Temat: Praca magisterska - potrzebna pomoc :)

Ja bym na Twoim miejscu raczej poprosił promotora o kilka propozycji. JAk wybierzesz coś na czym się zna Twój promotor to będziesz miała łatwiej napisać.
Dorota P.

Dorota P. Koordynator Analiz
Marketingowych

Temat: Praca magisterska - potrzebna pomoc :)

Cześć Magda,

Ja pisalam prace z metod kryptoanalizy algebraicznej(bazy Grobnera). Jest malo materiałów na te tematy ale są one dość przyjemne do opisania - dużo się teraz tam dzieje.
Piszesz u prof. Wittlina? :) Jeśli się zdecydujesz to mam jeszcze skrypty i kilka przydatnych linkow.

Magda Kowalska:
Cześć.
Chciałam się zapytać, czy moglibyście mi doradzić w wyborze tematu pracy magisterskiej z kryptografii. Mój promotor również nie narzucił mi z góry konkretnego tematu.
Jestem studentką matematyki i nie chciałabym nic programować.
Z góry dziękuję.
Małgorzata Cygańska

Małgorzata Cygańska Mobile Specialist,
MicroStrategy

Temat: Praca magisterska - potrzebna pomoc :)

Cześć,
Tak, piszę pracę u profesora Wittlina. Byłabym Ci wdzięczna gdybyś przesłała mi te skrypty. Na ich podstawie zdecydowałabym czy odpowiada mi ten temat.
A czy Ty również pisałaś u prof. Wittlina, i czy obrona była trudna, kto był recenzentem?
P.S. Zadaję tak dużo pytań, bo niewiele osób pisze pracę z kryptologii.

konto usunięte

Temat: Praca magisterska - potrzebna pomoc :)

Mamy kilkuletnie doświadczenie w pisaniu wzorów prac naukowych na zamówienie. Gwarantujemy ich wysoki poziom merytoryczny i metodologiczny. Zajmujemy się także profesjonalną redakcją oraz korektą gotowych tekstów.

Kontakt do nas:

e-mail: centrumredakcjiprac@gmail.com

http://centrumredakcjiprac.pl

Następna dyskusja:

Konwers relacji i inne-potr...




Wyślij zaproszenie do