Algorytm RSA - generowanie dużych liczb pierwszych

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:

1. Generuję losową nieparzystą liczbę o określonej długości(1000 bitów)
2. 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).
3. Jeśli liczba przejdzie pozytywnie test (czyli nie jest podzielna przez żadną z nich) to dalej sprawdzam pierwszość za pomocą testu Fermata.
4. 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).
5. 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++.

Skorzystaj z dedykowanej biblioteki, dla C/C++ będzie to np. MIRACL (komercyjna, ale darmowa do darmowych projektów) lub darmowa biblioteka znana z Linuxa GMP (GNU Multi Precision) lub np. darmowa LibTomMath.

1. Dla MIRACL - używa się funkcji nxprime()
2. Dla GMP - będzie to mpz_nextprime()
3. LibTomMath - mp_prime_random_ex()

Algorytmy generowania liczb pierwszych masz w tych bibliotekach z kodem źródłowym, więc możesz także spojrzeć jak robią to inni, jednak polecam dedykowane biblioteki do bigintów, bo zaoszczędza to czas i po prostu są one już przetestowane przez wielu ludzi.

Właśnie użycie GMP itp. programów nie wchodzi w grę, kod ma być kompliowany i musi działać bez instalowania dodatkowych bibliotek. Przeglądałem kod OpenSSLa ale strasznie ciężko dokopać się do takich podstaw jak generacja liczb pierwszych :/ ( i prawdopodobnie korzysta on z którejś wyżej wymienionej biblioteki). Głównie chodzi o ulepszenie algorytmu. Czy dałoby sie coś zrobić innego aby ten czas się zmniejszył?

Naprawdę polecam zajrzeć w źródła jednej z wymienionych przeze mnie bibliotek, strzelanie na chybił trafił nie ma szans z solidnymi rozwiązaniami, stosujesz 3 metody sprawdzania liczb pierwszych, z czego sprawdzanie przez pierwsze 78000 wydaje się jakimś nieporozumieniem i chyba nigdzie nie widziałem, aby tak sprawdzane były liczby pierwsze, dzielenie i jeszcze przez 78k liczb = spore obciążenie dla procesora.

Polecałbym też, abyś w kodzie wrzucił badanie prędkości poszczególnych fragmentów kodu, na Windows np. przez QueryPerformanceCounter:

http://msdn.microsoft.com/en-us/library/windows/desktop/dn553408(v=vs.85).aspx