?

Während ich Dick Liptons Blog las, stieß ich gegen Ende seines Bourne-Factor- Posts auf folgende Tatsachen :

Wenn für jedes $n$ eine Beziehung der Form
$(2^{n})! = \sum_{k = 0}^{m - 1} a_{k} b_{k}^{c_{k}}$ $(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k}$ wobei $m = poly(n)$ , und jedes der $a_k$ , $b_k$ und $c_k$ sind $poly(n)$ in Bitlänge, dann Factoring hat polynomgroße Schaltkreise.

Mit anderen Worten, die $(2^n)!$ , die eine exponentielle Anzahl von Bits hat , kann möglicherweise effizient dargestellt werden.

Ich habe ein paar Fragen:

Könnte jemand einen Beweis für die obige Beziehung erbringen, mir den Namen mitteilen und / oder Referenzen angeben?
Wenn ich Ihnen $n$ , $m$ und jedes der $a_k$ , $b_k$ und $c_k$ , könnten Sie mir einen polynomialen Zeitalgorithmus zur Verfügung stellen, um die Gültigkeit der Relation zu überprüfen (dh, ist es in $NP$ )?

ds.algorithms reference-request factoring comp-number-theory user834
quelle

Behauptet dieser Blog-Beitrag nicht tatsächlich das Gegenteil? Das heißt, wenn Gleichungen der obigen Form

haben Lösungen im Allgemeinen , dann hat Factoring polynomgroße Schaltungen.

(2^{n})! = \sum \dots

$(2^n)! = \sum \cdots$

mikero

Ich denke, Sie haben tatsächlich das Gegenteil von dem geschrieben, was Dick Lipton geschrieben hat. Er sagt, wenn eine solche Gleichung für jedes

, dann hat Factoring Polynomgrößenschaltungen. Die Implikation ist also, dass, wenn Factoring ungleichmäßig hart ist (für unendlich viele

), keine Gleichungen der obigen Form existieren (für unendlich viele

n

$n$

n

$n$

n

$n$

Sasho Nikolov

@mikero, SashoNikolov, ihr beide habt recht, ich entschuldige mich. Ich habe meine Frage bearbeitet.

user834

man beachte, dass "polynomialer Zeitalgorithmus" normalerweise einen einheitlichen Algorithmus bedeutet. Liptons Beitrag behauptet nur, dass es eine Polysize-Schaltkreisfamilie für Factoring gibt.

Sasho Nikolov

Beachten Sie, dass , um diese Eigenschaft wahr zu sein,

und

sollte

auf Lipton Blog / und in Bitgröße / wie angegeben

als ganzen Zahlen . Ihre Definition ist nicht klar.

a_{k}

$a_k$

b_{k}

$b_k$

c_{k}

$c_k$

p o l y (n)

$poly(n)$

p o l y (2^{n})

$poly(2^n)$

Gopi

Antworten:

Ich werde kommentieren, warum eine Beziehung wie in der Frage (für jedes ) hilft beim Factoring. Ich kann das Argument nicht ganz beenden, aber vielleicht kann es jemand.

(2^{n})! = \sum_{k = 0}^{m - 1} a_{k} b_{k}^{c_{k}}

$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k}$

n

$n$

Die erste Beobachtung ist, dass eine Beziehung wie oben (und allgemeiner die Existenz von Polygrößen-Arithmetikschaltungen für ) Eine Polygrößen-Schaltung zum Berechnen von ergibt für in binärer Form: Berechnen Sie einfach die Summe modulo unter Verwendung der Potenzierung durch wiederholtes Quadrieren. $(2^n)!$ $(2^n)!\bmod x$ $x$ $x$

Nun, wenn wir berechnen könnten für willkürliches könnten wir faktorisieren: Finden Sie mit der binären Suche das kleinste so dass (das wir mit berechnen können ). Dann muss der kleinste Primteiler von . $y!\bmod x$ $y$ $x$ $y$ $\gcd(x,y!)\ne1$ $\gcd(x,(y!\bmod x))$ $y$ $x$

Wenn wir nur Potenzen von für , können wir trotzdem versuchen, Für jedes zu berechnen . Einer von diesen wird ein nichttrivialer Teiler von , mit Ausnahme des unglücklichen Falles, wenn es ein so dass gleichbedeutend mit und dividiert . Dies ist äquivalent zu der Aussage, dass $2$ $y$ $\gcd(x,(2^n)!)$ $n\le\log x$ $x$ $n$ $x$ $(2^n)!$ $(2^{n+1})!$ $x$ ist quadratfrei und alle Primfaktoren haben die gleiche Bitlänge. Ich weiß nicht, was ich in diesem (ziemlich wichtigen, vgl. Blum-Ganzzahlen) Fall tun soll.

Emil Jeřábek unterstützt Monica
quelle

Wenn die Beziehung gilt (für alle

), dann gilt sie vielleicht auch (mit einer anderen Wahl von

und

), wenn man

durch eine andere (kleine) Primzahl ersetzt,

. Man könnte vermutlich suchen , bis ein

solche gefunden wird , dass

ist coprime zu

und nicht

n

$n$

a_{k}

$a_k$

b_{k}

$b_k$

c_{k}

$c_k$

2

$2$

p

$p$

p

$p$

x

$x$

(p^{n})!

$(p^n)!$

(p^{n + 1})!

$(p^{n+1})!$

user834