generowanie liczb pierwszych
-
- Użytkownik
- Posty: 37
- Rejestracja: 2 gru 2006, o 15:24
- Płeć: Mężczyzna
- Lokalizacja: Leeds
- Podziękował: 15 razy
generowanie liczb pierwszych
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.
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.
- yorgin
- 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
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}\)
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}\)
-
- Użytkownik
- Posty: 37
- Rejestracja: 2 gru 2006, o 15:24
- Płeć: Mężczyzna
- Lokalizacja: Leeds
- Podziękował: 15 razy
generowanie liczb pierwszych
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
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
-
- Użytkownik
- Posty: 37
- Rejestracja: 2 gru 2006, o 15:24
- Płeć: Mężczyzna
- Lokalizacja: Leeds
- Podziękował: 15 razy
generowanie liczb pierwszych
Jesli jest tam funkcje matematyczna mozesz ja tutaj podac, nie mam exela
- nuclear
- 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
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
trochę lamersko ale działa
- Sokół
- 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
tyle tam funkcji mat. ile sera na ksiezycu.greg.p pisze:esli jest tam funkcje matematyczna mozesz ja tutaj podac, nie mam exela
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.
-
- Użytkownik
- Posty: 37
- Rejestracja: 2 gru 2006, o 15:24
- Płeć: Mężczyzna
- Lokalizacja: Leeds
- Podziękował: 15 razy
generowanie liczb pierwszych
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.
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.
- kadiii
- 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
Jestem ciekawy jak to zrobisz, możesz zdradzić szczegóły.Lecz juz doszedlem do tego ze nia ma innej metody niz generwoanie liczb losowo i testowanie ich pierwszosci.
Szybki sposób.Narazie generuje losowe liczbe i jesli jest nieparzysta sprawdzam czy jest to pierwsza
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.
-
- Użytkownik
- Posty: 37
- Rejestracja: 2 gru 2006, o 15:24
- Płeć: Mężczyzna
- Lokalizacja: Leeds
- Podziękował: 15 razy
generowanie liczb pierwszych
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.kadiii pisze: Jestem ciekawy jak to zrobisz, możesz zdradzić szczegóły.
Osobiscie bede to robil na poziomie binarnym bo potrzebuje miec mozliwosc podania dlugosci w bitach pozadanej liczby jako parametr.
Co masz konkretnie na mysli piszac profesionalne rozwiazanie?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.
- kadiii
- 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
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
-
- Użytkownik
- Posty: 37
- Rejestracja: 2 gru 2006, o 15:24
- Płeć: Mężczyzna
- Lokalizacja: Leeds
- Podziękował: 15 razy
generowanie liczb pierwszych
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.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ć.