Parallelizacja czynnikowa Pollard-Rho

Niedawno natknąłem się na a paper na równoległość Pollard's Rho algorithm, i biorąc pod uwagę moją konkretną aplikację, oprócz tego, że nie osiągnąłem wymaganego poziomu matematyki, zastanawiam się, czy ta konkretna paralelizacja Metoda pomaga mi w konkretnym przypadku.Parallelizacja czynnikowa Pollard-Rho

Próbuję znaleźć dwa czynniki-pół-liczby-bardzo dużej liczby. Moje założenie, oparte na tym, co mało mogę zrozumieć z tego artykułu, jest takie, że ta równoległość działa dobrze na liczbę z wieloma mniejszymi czynnikami, a nie na dwóch bardzo dużych czynnikach.

Czy to prawda? Czy powinienem użyć tej równoległości lub użyć czegoś innego? Czy powinienem nawet użyć Rho Pollarda, czy też istnieje lepsza równoległość innego algorytmu rozkładu?

Źródło

2011-09-24 skeggse

Jak duża jest twoja bardzo duża liczba? Ile cyfr dziesiętnych? – user448810

Wszędzie od '2^16' (5 cyfr dziesiętnych) do' 2^8192' (2467 cyfr dziesiętnych). Zgaduję, że prawdopodobnie użyłbym wielu różnych algorytmów, w zależności od wielkości liczby, chociaż nie jestem tego pewien. Wiem, że Pollard-rho jest wyspecjalizowanym algorytmem, ale nie znalazłem wielu paralelizacji innych algorytmów, więc trochę się zmagam. – skeggse

Należy zauważyć, że chociaż '2^8192' jest teoretyczną górną granicą, nie spodziewam się, że będę w stanie zliczyć coś tak dużego. – skeggse

Podstawową ideą faktoringu dużych liczb całkowitych jest użycie różnych metod, z których każda ma własne plusy i minusy. Zwykle planujemy rozpocząć od podziału próbnego przez liczby pierwsze do 1000 lub 10000, a następnie kilka milionów kroków ronda Pollarda; to powinno dostarczyć ci około dwunastu cyfr. W tym momencie kilka testów jest w porządku: czy liczba to moc pierwotna, czy moc doskonała (są proste testy dla tych właściwości). Jeśli nadal nie uwzględniłeś numeru, wiesz, że będzie to trudne, więc będziesz potrzebował wytrzymałych narzędzi. Kolejnym przydatnym krokiem jest metoda p-1 Pollarda, a następnie jej bliska kuzynka metoda krzywej eliptycznej. Po pewnym czasie, jeśli to nie zadziała, jedynymi pozostałymi metodami są kwadratowe sito lub numeryczne sito pola, które są z natury równoległe.

Metoda rho, o którą pytałeś, nie jest dziś powszechnie stosowana. Jak zasugerowałeś, Pollard rho lepiej nadaje się do znajdowania małych czynników niż dużych. Dla półpreparatu lepiej jest spędzać równoległe cykle na jednym z sit, niż na Pollard rho.

Polecam forum faktoringowe na stronie mersenneforum.org, aby uzyskać więcej informacji.

Źródło

2011-09-26 13:10:59 user448810

Jeden mały problem. Zalecane metody są dość złożone i nie mogę znaleźć żadnej specyfikacji algorytmu ani pseudokodu. Biorąc pod uwagę, że moje wykształcenie matematyczne jest nieco ograniczone, nie mogę po prostu pójść do źródła i spróbować wymyślić kod na własną rękę. – skeggse

Nie musisz robić tego sam. Przejdź do forum faktoringowego na stronie mersenneforum.org. Mają wskaźniki do programów takich jak gmp-ecm, msieve i inne, które są zarówno ogólnodostępne, jak i najlepsze dostępne programy faktoringowe. Jeśli musisz zrobić to sam, mój blog na http://programmingpraxis.com ma opisy i kod źródłowy większości algorytmów faktoringowych, choć jeszcze nie oba sita. – user448810

artykułu z Wikipedii stwierdza dwa konkretne przykłady:

Number    Original code  Brent's modification 
18446744073709551617 26 ms    5 ms 
10023859281455311421 109 ms    31 ms

przede wszystkim uruchomić te dwa z programu i spojrzeć na swoje czasy. Jeśli są do tego podobne ("twarde" liczby obliczają 4-6 razy dłużej), zadaj sobie pytanie, czy możesz z tym żyć. Albo jeszcze lepiej, użyj innych algorytmów, takich jak prosta klasyczna "brutalna" faktoryzacja i spójrz na czasy, które dają. Sądzę, że mogą mieć trudny do przewidzenia współczynnik bliższy 1, ale gorszy czas bezwzględny, więc jest to prosty kompromis.

Notka poboczna: Oczywiście, równoległość jest sposobem, aby tu dotrzeć, myślę, że wiesz o tym, ale myślę, że to ważne, aby podkreślić. Pomoże to również w przypadku, gdy inne podejście będzie polegało na ustaleniu przedziałów czasowych Pollard-rho (np. Pollard-Rho 5-31 ms, inne podejście 15-17 ms) - w takim przypadku rozważ użycie dwóch algorytmów w oddzielnych wątkach zrobić "wyścig czynnikowy".

Jeśli jeszcze nie masz rzeczywistej implementacji algorytmu, oto Python implementations.

Źródło

2011-09-26 10:00:48 schnaader

Wielkie dzięki, nie mogłem uzyskać dostępu do oryginalnego dokumentu, więc ta implementacja okazała się najbardziej przydatna. – skeggse

Parallelizacja czynnikowa Pollard-Rho

Odpowiedz

Powiązane problemy