teomos

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ł?

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++.