Factorization of large numbers

Question

W klasie znaleźliśmy ten problem programistyczny, a obecnie nie mamy pojęcia, jak go rozwiązać.

Podano dodatnią liczbę całkowitą n. Wiadomo, że n = p * q, gdzie p i q są liczbami pierwszymi, p<=q i |q-k*p|<10^5 dla pewnej danej liczby całkowitej dodatniej k. Musisz znaleźć p i q.

Wejście:

35 1 
121 1 
1000730021 9 

wyjściowa:

5 * 7 
11 * 11 
10007 * 100003 

To nie jest praca, my po prostu staramy się rozwiązać kilka ciekawych problemów. Jeśli masz jakieś pomysły, opublikuj je tutaj, abyśmy mogli spróbować czegoś, dzięki.

Answer 1

W przypadku liczb o rozmiarze, o którym tu mowa, najszybszą metodą faktoringu jest (prawdopodobnie) użycie Sita Eratostenesa do wygenerowania liczb pierwszych do około pierwiastka kwadratowego liczby, a następnie skorzystanie z próbnego podziału przez tych, którzy znajdą który (e) są dzielnikami.

Sporo metod faktoringowych wymyślono dla większych liczb. Możesz chcieć Google za "metodę faktoringową Fermata", "Pollard Rho", "metodę Brenta", "eliptyczną krzywą Lenstry", "wielomianowe kwadratowe sito" i "ogólne sito pola liczbowego". Wymieniłem je w (z grubsza) rosnącej kolejności złożoności i zdolności do liczenia większych liczb. Otwarte jest pytanie, czy powinienem wspomnieć o ogólnym sicie pola liczbowego, czy nie - podczas gdy jest to najbardziej efektywna metoda, znana obecnie z faktoringu bardzo dużych liczb, jest ona przydatna tylko na naprawdę dużych maszynach - poniżej około 110 cyfr, czyli MPQS jest szybszy, ale do liczenia dużych liczb, gdzie GNFS jest szybszy, potrzebujesz dużo więcej pamięci niż typowy komputer lub serwer może obsłużyć (pomyśl o terabajtach RAM jako minimalnym punkcie startowym, ale prawdopodobnie o więcej).

Answer 2

Użyłem metody ECM do obliczenia dużej liczby całkowitej. Jest to jeden z najbardziej wydajnych algorytmów znanych. Jeśli chcesz dowiedzieć się, jak działa algorytm, to masz dużo do zrobienia, ale jeśli chcesz go wykorzystać do wykonania swoich badań, niektórzy je zaimplementowali. Na przykład możesz pobrać te pakiety open source: GMP-ECM dla C/C++ lub Pyecm dla Pythona.

$ python 
>>> import math 
>>> import pyecm 
>>> n = 1000730021 
>>> list(pyecm.factors(n, False, False, 2 * math.log(math.log(n)), 1.0)) 
[10007, 100003] 

Answer 3

n = p * q 
|q-k*p|<10^5 

z n i k podaje się jako dane wejściowe.Dlatego

q-k*p=a 

z

-10^5<=a<=10^5 

Mnożąc q-k*p=a przez q i zastępując p*q przez n daje

q^2-a*q-k*n=0 

rozwiązać równanie kwadratowe każdego a z

-10^5<=a<=10^5` 

i sprawdź, czy q dzieli . Rozwiązywanie równania kwadratowego można wykonać w czasie wielomianowym, co jest prawdą dla rozwiązania równania 2*10^5+1. Istnieją lepsze algorytmy dla małych wartości n i k, a także dla dużych wartości n i k oczywiście.

Jak ypercube wspomniano, trzeba tylko sprawdzić równania gdzie

a^2+4*k*n 

jest kwadratem.

Answer 4

n = p * qi | q-k * p | < 10^5 z n i k podanymi jako dane wejściowe. Dlatego qk * p = a, z -10^5 < = a < = 10^5 Mnożenie qk * p = a przez q ans podstawianie p * q przez n daje q^2-a * qk * n = 0 . Rozwiąż to równanie kwadratowe dla każdego a za pomocą -10^5 < = a < = 10^5 i sprawdź, czy q dzieli n. Rozwiązanie równania kwadratowego można wykonać w czasie wielomianowym, a dotyczy to rozwiązania równania 2 * 10^5 + 1. Są lepsze algorytmy dla małych wartości n i k

p jest w Intervall

[(sqrt(k*n+2500000000)-50000)/k,(sqrt(k*n+2500000000)+50000)/k] 

dlatego trzeba tylko sprawdzić wartości 10^5/K dla p. q wynosi w INTERVALL

[sqrt(k*n+2500000000)-50000,sqrt(k*n+2500000000)+50000] 

która zawsze zawiera około 10^5 inegers