Skocz do zawartości

Algorytm RSA - generowanie dużych liczb pierwszych


teomos

Recommended Posts

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

Link do komentarza
Udostępnij na innych stronach

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.

Link do komentarza
Udostępnij na innych stronach

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ł?
Link do komentarza
Udostępnij na innych stronach

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

Link do komentarza
Udostępnij na innych stronach

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Gość
Odpowiedz...

×   Wkleiłeś zawartość bez formatowania.   Usuń formatowanie

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Utwórz nowe...