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.
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ł.
źródło
Odpowiedzi:
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 .do do log log x ∗ y ∗ x1∗ … ∗ xlogn P. do
Zauważ, że każda liczba może być zapisana jako suma potęgi 2 . Każdy z nich jest łatwy do uwzględnienia.logn 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 P.FactSum P. N C.1
źródło
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
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ą.O N
Współczynnik PROCEDURY ( )N
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.
źródło
Ta odpowiedź jest niezależna od mojej poprzedniej odpowiedzi . Jego celem jest uwzględnienie obaw @ Kaveha w komentarzach:
Miałem podobny problem:
(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:
źródło