Dodawanie liczb całkowitych reprezentowanych przez ich faktoryzację jest tak trudne, jak faktoring? Wniosek o referencję

Szukam odwołania do następującego wyniku:

Dodanie dwóch liczb całkowitych do reprezentacji faktoryzowanej jest tak trudne, jak dodanie dwóch liczb całkowitych do zwykłej reprezentacji binarnej.

(Jestem prawie pewien, że tam jest, ponieważ zastanawiałem się nad tym, a potem byłem podekscytowany, gdy w końcu zobaczyłem to w druku).

Problemem jest „dodanie dwóch liczb całkowitych do reprezentacji faktoryzowanej”: biorąc pod uwagę faktoryzacje pierwsze dwóch liczb i y , wyprowadza pierwszą faktoryzację x + y . Zauważ, że naiwny algorytm tego problemu wykorzystuje faktoryzację w standardowej reprezentacji binarnej jako podprogram.$x$$y$$x+y$

Aktualizacja : dziękuję Kavehowi i Sadeqowi za dowody. Oczywiście im więcej dowodów, tym lepiej, ale chciałbym również zachęcić do większej pomocy w znalezieniu referencji , co, jak powiedziałem, jestem całkiem pewien, że istnieje. Pamiętam, że czytałem go w artykule z innymi interesującymi i nierzadko dyskutowanymi pomysłami, ale nie pamiętam, jakie były te inne pomysły ani w ogóle o czym był ten artykuł.

Zakładamy, że możemy rozwiązać ten problem (nazwijmy go FactSum) w klasie złożoność i C jest zamknięty pod dziennika -iteration (aka zalogować -bounded rekurencji) (na przykład, jeśli możemy obliczyć x * y , gdzie * jest funkcją binarną, możemy obliczone x 1 ∗ … ∗ x log n ) i zawiera P (ten ostatni warunek można osłabić). Pokażemy, że faktoring jest również w C .$C$$C$$\log$$\log$$x*y$$*$$x_1*\ldots*x_{\log{n}}$$\mathsf{P}$$C$

Zauważ, że każda liczba może być zapisana jako suma potęgi 2 . Każdy z nich jest łatwy do uwzględnienia.$\log n$$2$

Teraz, biorąc pod uwagę liczbę, napisz ją jako sumę jej mocy, a następnie napisz każde podsumowanie w reprezentacji faktoringowej, a następnie użyj algorytmu, aby zsumować je w reprezentacji faktoringowej. Wynikiem będzie faktoring numeru wejściowego.

To pokazuje, że faktoring można zredukować do interpretacji problemu FactSum. Dlatego faktoring jest w P FactSum (i myślę, że P można zastąpić tutaj N C 1 ).$\log$$\mathsf{P}^{\text{FactSum}}$$\mathsf{P}$$\mathsf{NC^1}$

Nie znam referencji, ale wydaje mi się, że wymyśliłem dowód:

Załóżmy, że masz wyrocznię która po wprowadzeniu dwóch liczb faktorowanych$\mathcal{O}$

$x = \prod_{i=1}^n p_i^{\alpha_i}$

i

$y = \prod_{i=1}^m q_i^{\beta_i} \enspace$,

wyprowadza faktoryzację .$x+y$

Mając dostęp do , możemy uwzględnić dowolną liczbę N w czasie wielomianowym, stosując następującą procedurę rekurencyjną.$\mathcal{O}$$N$

Współczynnik PROCEDURY ( )$N$

1. Znajdź liczbę pierwszą taką, że N / 2 ≤ x ≤ N - 1 , i niech y = N - x .$x$$N/2 \le x \le N-1$$y = N - x$
2. Jeśli nie jest liczbą pierwszą, uzyskaj faktoryzację y przez rekursywny współczynnik wywołania ( y ) i wyślij O ( x , f a c t o r ( y ) ) .$y$$y$$y$$\mathcal{O}(x, factor(y))$
3. W przeciwnym razie wyjście .$\mathcal{O}(x,y)$

Analiza:

Według twierdzenia o liczbie pierwszej dla wystarczająco dużego istnieje wiele liczb pierwszych pomiędzy N / 2 i N - 1 . Jeśli N jest tak mała, że nie prime spadnie w tym przedziale można czynnik N łatwo. Dlatego krok 1 mija.$N$$N/2$$N-1$$N$$N$

W kroku 2 możesz użyć AKS lub dowolnego innego testu pierwotności w czasie wielomianowym.

Liczba rekurencji to po prostu , ponieważ na każdym etapie N jest przecinany na pół (przynajmniej)$O(\lg(N)) = O(|N|)$$N$

PS-1: Przyjmując hipotezę Goldbacha może pomóc w przyspieszeniu procedury nawet (i ewentualnie nieparzyste) liczb całkowitych.

PS-2: Zastosowana redukcja to redukcja Cooka. Ktoś może być zainteresowany przeprowadzeniem dowodu przy użyciu redukcji Karp.

Ta odpowiedź jest niezależna od mojej poprzedniej odpowiedzi . Jego celem jest uwzględnienie obaw @ Kaveha w komentarzach:

Jest to łatwe do zrobienia, jeśli chcieliśmy liczb, ale nie widzę jak to zrobić nawet z log log n liczb.$\log n$$\log \log n$

Miałem podobny problem:

Zastosowana redukcja to redukcja Cooka. Ktoś może być zainteresowany przeprowadzeniem dowodu przy użyciu redukcji Karp.

(Redukcje Karp dotyczą problemów decyzyjnych. Tutaj, poprzez redukcję Karp, mam na myśli redukcję Cooka w jednym zapytaniu. Przepraszamy za niestandardową terminologię!)

Poniższa odpowiedź opiera się na dyskusjach tutaj: /math/54580/factoring-some-integer-in-the-given-interval .

W tej odpowiedzi przedstawię deterministyczną redukcję Karpa w czasie wielomianowym od faktoringu do faktorowania sumy dwóch liczb całkowitych reprezentowanych przez ich faktoryzacje . Jest jednak jeden haczyk: w trakcie dowodu zastosuję następujące założenie teoretyczne:

$p_n$$p_{n+1}$$p_{n+1} - p_n = O(\log^2p_n)$

$N$$n=|N|=O(\log N)$$N$$[N - \log^3N, N]$$\log^3N = O(n^3)$

$x$$[N - \log^3N, N]$$y=N-x$

$0 \le y \le \log^3N$$|y| = O(\log \log N) = O(\log n)$$y$

$(x,y)$$N = x+y$