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

22

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

Joshua Grochow
źródło
6
Myślę, że lepszym tytułem będzie: „Czy faktoring jest sumą dwóch liczb całkowitych reprezentowanych przez ich faktoryzację równie trudną jak faktoring?”
MS Dousti
1
Fajne pytanie. Jeśli możemy napisać daną liczbę całkowitą jako sumę dwóch łatwych do uwzględnienia liczb całkowitych, to co chcesz, następuje. Jest to łatwe do zrobienia, jeśli chcieliśmy liczb, ale nie widzę jak to zrobić nawet z log log n liczb. Warto spojrzeć na klasy liczb, które są łatwe do uwzględnienia. lognloglogn
Kaveh
1
kilka powiązanych pytań na temat MO i Math. SE: 1 , 2 , 3
Kaveh

Odpowiedzi:

15

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 1x log n ) i zawiera P (ten ostatni warunek można osłabić). Pokażemy, że faktoring jest również w C .CCloglogxyx1xlognPC

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

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 ).logPFactSumPNC1

Kaveh
źródło
10

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 faktorowanychO

x=i=1npiαi

i

y=i=1mqiβi,

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ą.ON

Współczynnik PROCEDURY ( )N

  1. Znajdź liczbę pierwszą taką, że N / 2 x N - 1 , i niech y = N - x .xN/2xN1y=Nx
  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 ) ) .yyyO(x,factor(y))
  3. W przeciwnym razie wyjście .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.NN/2N1NN

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.

MS Dousti
źródło
3
Myślę, że jest otwarte, jeśli potrafimy skutecznie znaleźć
Kaveh
1
@Kaveh: Masz rację! Po kilku dodatkowych krokach myślę, że mogę zmienić algorytm, aby nie wymagał, aby był liczbą pierwszą, a następnie rozliczyć go jak y ; lub możemy założyć, że redukcja jest probabilistyczna (ponieważ w probabilistycznym czasie wielomianowym możemy znaleźć liczbę pierwszą w danym zakresie). xy
MS Dousti
2
Tak, myślę, że mieliśmy ten sam pomysł, tzn. Chcieliśmy znaleźć łatwe do uwzględnienia liczby całkowite, które sumują się do danych wejściowych, próbowałeś użyć liczb pierwszych, użyłem potęg 2. 2. Wciąż nie wiem, czy możemy to zrobić z mniej niż logarytmiczna liczba zapytań do wyroczni, i wydaje się, że jest to związane z interesującym i naturalnym pytaniem teorii liczb (zapisywanie liczb jako suma liczb łatwych do uwzględnienia).
Kaveh
5

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

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:

pnpn+1pn+1pn=O(log2pn)

Nn=|N|=O(logN)N[Nlog3N,N]log3N=O(n3)

x[Nlog3N,N]y=Nx

0ylog3N|y|=O(loglogN)=O(logn)y

(x,y)N=x+y

MS Dousti
źródło
Dzięki Sadeq, ale wyniki warunkowe nie były tym, o co prosiłem. ps: Interesują mnie interesujące reprezentacje liczb, a reprezentacja uzyskana z twojej odpowiedzi (wyciągnięcie dużej liczby pierwszej) nie wydaje mi się bardzo interesująca. Za nadanie smaku tego, co byłoby dla mnie interesujące: każda liczba naturalna jest sumą czterech kwadratów .
Kaveh