generowanie liczb pierwszych

greg.p
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 2 gru 2006, o 15:24
Płeć: Mężczyzna
Lokalizacja: Leeds
Podziękował: 15 razy

generowanie liczb pierwszych

Post autor: greg.p »

Witam,

Czy jest inny sposob na generowanie liczb pierwszych niz:

- generowanie liczby losowo
- sprawdzanie czy jest parzysta
- jesli nie to testowanie jej czy jest pierwsza

Jesli nie to jaki jest najszybszy algorytm do testowania liczby czy jest pierwsza?


Z gory dziekuje i pozdrawiam.
Awatar użytkownika
yorgin
Użytkownik
Użytkownik
Posty: 12762
Rejestracja: 14 paź 2006, o 12:09
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 17 razy
Pomógł: 3440 razy

generowanie liczb pierwszych

Post autor: yorgin »

Jeżeli generowanie ma się odbywać na zasadzie wyznaczania liczb pierwszych w zbiorze {1,..,n}, to najlepszą metodą będzie tu Sito Eratostenesa (z tego co sam wiem).
A jeżeli chodzi o sprawdzanie, to wydaje mi się że krócej jak dla danej liczby n sprawdzać wszyskie liczby a spełniające warunek: \(\displaystyle{ a}\)
greg.p
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 2 gru 2006, o 15:24
Płeć: Mężczyzna
Lokalizacja: Leeds
Podziękował: 15 razy

generowanie liczb pierwszych

Post autor: greg.p »

Sito odpada, bo mi chodzi o wygenerowanie dwoch bardzo duzych liczb pierwszych, w jak najkrotszym czasie.

Narazie generuje losowe liczbe i jesli jest nieparzysta sprawdzam czy jest to pierwsza. W javie jest do tego metoda BigInteger.isProbablePrime(). Lecz w PHP tego juz nie ma i szukam wyjscia jak to przeskoczyc.

Jest pare algorytmow na testowanie pierwszosci lecz niektore podaja tylko prawdopodobienstwo pierwszosci i nie neguja ze liczba moze byc pseudo pierwsza Zreszta tak samo jak ta funkcja w Javie i zastanawia mnie jak generuje sie liczby pierwsze w programach kryptograficznych.



Jak ktos by mial jakis patent na generowanie duzych liczb pierwszych prosze o informacje.


Pozdrawiam
Awatar użytkownika
nuclear
Użytkownik
Użytkownik
Posty: 1501
Rejestracja: 22 paź 2006, o 12:01
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 16 razy
Pomógł: 264 razy

generowanie liczb pierwszych

Post autor: nuclear »

dam Ci arkusz w excelu do sprawdzania czy dana liczba jest pierwsza



mysle ze chodz troche Ci sie to przyda
greg.p
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 2 gru 2006, o 15:24
Płeć: Mężczyzna
Lokalizacja: Leeds
Podziękował: 15 razy

generowanie liczb pierwszych

Post autor: greg.p »

Jesli jest tam funkcje matematyczna mozesz ja tutaj podac, nie mam exela
Awatar użytkownika
nuclear
Użytkownik
Użytkownik
Posty: 1501
Rejestracja: 22 paź 2006, o 12:01
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 16 razy
Pomógł: 264 razy

generowanie liczb pierwszych

Post autor: nuclear »

najpierw wypisałem po kolei liczby (0-5000) następnie użyłem funkcji =MOD(F$3;X)-czyli reszta z dzielenia po czym =JEŻELI(X=0;1;0) gdzie X to numer komórki


trochę lamersko ale działa
Awatar użytkownika
Sokół
Użytkownik
Użytkownik
Posty: 451
Rejestracja: 17 wrz 2006, o 19:22
Płeć: Mężczyzna
Lokalizacja: Zielona Góra
Podziękował: 15 razy
Pomógł: 55 razy

generowanie liczb pierwszych

Post autor: Sokół »

greg.p pisze:esli jest tam funkcje matematyczna mozesz ja tutaj podac, nie mam exela
tyle tam funkcji mat. ile sera na ksiezycu.

przykladowe teksty w komorkach

B8: 1
C8: =MOD(F$3;B8)
D9: =JEŻELI(C8=0;1;0)
E4: =JEŻELI(D5007=2;"Ta liczba jest liczba pierwsza";"Ta liczba nie jest liczba pierwsza")

arkusz obsluguje liczby niewieksze niz 5000.
greg.p
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 2 gru 2006, o 15:24
Płeć: Mężczyzna
Lokalizacja: Leeds
Podziękował: 15 razy

generowanie liczb pierwszych

Post autor: greg.p »

Panowie 5000 to nie sa duze liczby.

Lecz juz doszedlem do tego ze nia ma innej metody niz generwoanie liczb losowo i testowanie ich pierwszosci.

Ciekawe ile czasu zaimie testowanie liczb 64bitowych w PHP , ktore i tak juz sa uznawane za male do generowania bezpiecznych kluczy.
Awatar użytkownika
kadiii
Użytkownik
Użytkownik
Posty: 642
Rejestracja: 20 gru 2005, o 21:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 130 razy

generowanie liczb pierwszych

Post autor: kadiii »

Lecz juz doszedlem do tego ze nia ma innej metody niz generwoanie liczb losowo i testowanie ich pierwszosci.
Jestem ciekawy jak to zrobisz, możesz zdradzić szczegóły.
Narazie generuje losowe liczbe i jesli jest nieparzysta sprawdzam czy jest to pierwsza
Szybki sposób.
A tak na poważnie jeśli musisz tego użyć do jakegoś szyfrowania danych to: jeśli nie jest to coś strasznie ważnego to użyj algorytmów probabilistycznych, które choć jak sam stwierdzasz czasem podają liczby pseudopierwsze to jednak mylą się bardzo rzadko(np.popularny w prostych zastosowaniach a. Millera-Rabina), a jeśli musisz użyć tego w sposób profesionalny, to musisz chyba skorzystać z profesionalnych rozwiązań, bo chyba raczej sam, ani nikt na forum, nie wymyśli ci lepszego algorytmu.
greg.p
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 2 gru 2006, o 15:24
Płeć: Mężczyzna
Lokalizacja: Leeds
Podziękował: 15 razy

generowanie liczb pierwszych

Post autor: greg.p »

kadiii pisze: Jestem ciekawy jak to zrobisz, możesz zdradzić szczegóły.
Tak jak to sam opisales Testem pierwszosci. np. Millera-Rabina lub teoria Fremata,a jesli pytasz o generowanie losowao liczb to w zaleznosci od jezyka sa rozne metody na ich generowanie.

Osobiscie bede to robil na poziomie binarnym bo potrzebuje miec mozliwosc podania dlugosci w bitach pozadanej liczby jako parametr.


kadiii pisze: [...]a jeśli musisz użyć tego w sposób profesionalny, to musisz chyba skorzystać z profesionalnych rozwiązań, bo chyba raczej sam, ani nikt na forum, nie wymyśli ci lepszego algorytmu.
Co masz konkretnie na mysli piszac profesionalne rozwiazanie?
Awatar użytkownika
kadiii
Użytkownik
Użytkownik
Posty: 642
Rejestracja: 20 gru 2005, o 21:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 130 razy

generowanie liczb pierwszych

Post autor: kadiii »

Jakoś opacznie zrozumiałem twoje słowa-mój błąd. Myśląłem, że odrzucasz opcję użycia a.probabilistycznych i masz algorytm na sprawdzanie pierwszości ze 100% pewnością wyniku. A co do profesjonalnych rozwiązań to chodzi mi o pełne algorytmy kryptograficzne, które są jednak często objęte patentami i trzeba za nie zapłacić. Jest jednak trochę publikacji uczelnianych, szczególnie w języku angielskim, traktujących o tym problemie, może znajdzeiesz coś ciekawego. Ogólnie problem pierwszości jest trudnym problemem i nad wymyślaniem algorytmów siedzą rzesze matematyków, więc chyba "zabawa" samemu w wymyślanie takich rzeczy jest trochę nielogiczna(chyba, że ktoś to robi z ciekawości) Pozdrawiam i powodzenia w szukaniu optymalnego rozwiązania
greg.p
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 2 gru 2006, o 15:24
Płeć: Mężczyzna
Lokalizacja: Leeds
Podziękował: 15 razy

generowanie liczb pierwszych

Post autor: greg.p »

kadiii pisze:A co do profesjonalnych rozwiązań to chodzi mi o pełne algorytmy kryptograficzne, które są jednak często objęte patentami i trzeba za nie zapłacić.
Z tym sie jakos nie moge zgodzic bo RSA czy DES itp. to otwarte algorytmy matematyczne ,ktore sa wszystkim znane i implementujac je nie trzeba nikomu za nic placic. Tak samo jak implementujac funkcje, ktora testuje pierwszosc liczb.
ODPOWIEDZ