[s.....2]

#programowanie

Potrzebny mi jest generator dużych liczb pierwszych, powiedzmy 1024bitowych. Na razie rozwiązuje to przez generowanie po prostu dużej liczby, a później sprawdzam czy jest pierwszą. Tylko to zajmuje(sprawdzanie) w cholerę czasu i strasznie ciężko na nią trafić. Rozwiązał może ktoś kiedyś coś podobnego? Z góry mówię że raczej nie interesują mnie gotowe biblioteki. I tak, przewaliłem pół googla ale może ktoś ma jakieś praktyczne, swoje rozwiązanie

[p.....i]

@szycho1992: prime95 nie wyrzuca liczb?

[koob]

@szycho1992: http://pl.wikipedia.org/wiki/Sito_Eratostenesa

[s.....2]

@koob: osobom które będą rzucać linkami do wikipedii albo opisów algorytmów, wyjaśnienia co to liczba pierwsza z góry dziękuję.

Mam test Miller-Rabin'a, ale chodzi mi może o coś szybszego? Albo gotowy generator który losuje mi od razu liczbę pierwszą, jeśli coś takiego da się napisać. #csharp

[koob]

Albo gotowy generator który losuje mi od razu liczbę pierwszą

@szycho1992: daj sobie spokój z programowaniem.

[wicikumoza]

@szycho1992: Miałem podobny problem rok temu, też użyłem testu millera-rabina w BigIntegerExtension (open source) masz to

[s.....2]

@koob: daj sobie spokój z odpowiadaniem tutaj :x

[s.....2]

@wicikumoza: teraz dokładnie tego używam. w System.Security.Cryptography jest to gotowe, ale potrzebny mi właśnie inny sposób.

Jeśli istnieje to szybszy od mojego i bez tej gotowej biblioteki

[koob]

@szycho1992:

1. podałem Ci sposób "generowania" liczb pierwszych sitem erastotenesa (jest jeszcze sito Atkina-Bernsteina) a Ty wyskakujesz, że nie chcesz żadnych linków z wikipedii.

2. Losowanie dużej liczby i sprawdzanie czy jest pierwsza (zwłaszcza dla wielkich liczb) jest chyba najgłupszym pomysłem z możliwych - poczytaj o gęstości liczb

[stefanf]

@szycho1992:

w javie jest takie coś:

BigInteger.probablePrime(160, new Random()); //160 - bit

[s.....2]

@stefanf: tak, wiem że SĄ :) Chodzi o wygenerowanie losowej.

@koob: wytłumacz mi w takim razie że sito przy wielkich liczbach jest mniej głupim pomysłem :) i nobel za gotowy generator który losuje liczbę pierwszą dla @stefanf, nie stworzył ale pokazuje Ci na niego namiar

[o-o_i]

@szycho1992: Może liczby Fermata?

[s.....2]

@o-o_i: obawiam się, że nie sprawdzi się przy dużych liczbach :c ale dzięki :)