Chciałbym szybko wygenerować losową liczbę pierwszą. Mam problem z wydajnością. 1000 bitowa losowa liczba pierwsza generuje mi się w ciągu 5-10 sek. Za wolno :D
Mój algorytm jest następujący:
Generuję losową nieparzystą liczbę o określonej długości(1000 bitów)
Wykonuje wstępne testy: sprawdzam "brute-forcem" podzielność tej liczby przez kilka początkowych liczba pierwszych (mniej więcej 78000 liczb). Listę tych liczb mam wcześniej wygenerowaną i zapisaną w tablicy (stosuje sito Atkina).
Jeśli liczba przejdzie pozytywnie test (czyli nie jest podzielna przez żadną z nich) to dalej sprawdzam pierwszość za pomocą testu Fermata.
Jeśli liczba przejdzie pozytywnie ten test to na koniec sprawdzam testem Millera-Rabina(w 80% przypadków jeśli przejdzie Fermata to przechodzi Millera-Rabina).
Jeśli liczba nie przejdzie testów dodaje do niej 2 i sprawdzam od początku.
Jak to można ulepszyć? Byłbym bardzo wdzięczny za jakieś wskazówki
Do operacji na dużych liczbach wykorzystuję ttmath, kod piszę w C++.