Algorytm RSA - generowanie dużych liczb pierwszych

Witam!

Mam problem z generowaniem losowych liczb pierwszych o określonej długości(512 bitowe i większe). Np. chce sobie wygenerować dużą liczbę pierwszą powiedzmy składającą się z 300 cyfr. I teraz losuje taką liczbę(nieparzystą), sprawdzam algorytmem Rabina-Millera czy jest pierwsza. Jeśli nie, losuje kolejną liczbę itd... Czas wykonania takiego programu jest bardzo długi. Co robię źle? ;/

Albo inaczej: z czego korzystają popularne programy jak openssl itp. ? Tam generowanie kluczy(bo liczby pierwsze są właśnie potrzebne do tego) następuje bardzo szybko(max. kilka sekund)

Rozwiązanie znalezione :)

http://crypto.stackexchange.com/questions/71/how-can-i-generate-large-prime-numbers-for-rsa

Odświeżam temat!

Mam dalej problem z wydajnością. 1000 bitowa losowa liczba pierwsza generuje mi się w ciągu 5-10 sek. Wciąż za wolno.

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

Ja też ostatnio bawię się kryptografią i ja sprawdzam po prostu testem millera rabina i wynik dostaje natychmiast, a nie po 5 czy 10 sek. Nie wiem po co robisz te wstępne sprawdzania, wystarczy, że dasz odpowiednią liczbę testów millera-rabina i prawdopodobieństwo będzie równe 0,999999... a no i pytanie czy test millera rabina zrobiles zgodnie ze sztuka

bimbarabam napisał(a):

Ja też ostatnio bawię się kryptografią i ja sprawdzam po prostu testem millera rabina i wynik dostaje natychmiast, a nie po 5 czy 10 sek. Nie wiem po co robisz te wstępne sprawdzania, wystarczy, że dasz odpowiednią liczbę testów millera-rabina i prawdopodobieństwo będzie równe 0,999999... a no i pytanie czy test millera rabina zrobiles zgodnie ze sztuka

Jak długie liczby pierwsze sprawdzasz? :)
Zauważ że te 5,10 sek trwa cały proces generowania losowej liczby pierwszej. Czyli średnio, dopiero po sprawdzeniu około 100-200 liczb 300-cyfrowych.
Jeśli robisz dokładnie co opisałem wyżej to czy mógłbyś się podzielić szczegółami? :) Będę wdzięczny za każdą wskazówkę :)

Tutaj mój algorytm w C++

 
bool testMillerRabin(const BigInt &liczba, size_t iloscCyfr, int k = 3)
	{

		BigInt s, d, a, x;
		d = liczba - 1;
		s.SetZero();

		//zalaczamy maszyne losujaca - zwolnienie blokady :)
		std::random_device rd;
		std::mt19937 gen(rd());
		std::uniform_int_distribution<> distro_short(2, iloscCyfr);
		int randomNumber = 0;

		while ((d % 2).IsZero())
		{
			s.AddOne();
			d.Div(two);
		}
		for (int i = 1; i <= k; i++)
		{
			randomNumber = distro_short(gen);
			losujLiczbe(a, (iloscCyfr - 1));

			GetPowerMod(a, d, liczba,x);
			if (x.CmpEqual(1) || x.CmpEqual(liczba - 1)) continue;
			for (BigInt j = 1; (j.CmpSmaller(s) && (x != (liczba - 1))); j++)
			{
				GetPowerMod(x, two, liczba,x);
				if (x.CmpEqual(1)) return false;
			}
			if (x != (liczba - 1)) return false;

		}
		return true;
	}