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