?

16

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

(2n)!=k=0m1akbkck
wobei m=poly(n) , und jedes der ak , bk und ck sind poly(n) in Bitlänge, dann Factoring hat polynomgroße Schaltkreise.

Mit anderen Worten, die (2n)!, 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 ak , bk und ck , 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 )?
user834
quelle
4
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. (2n)!=
mikero
3
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 n ), keine Gleichungen der obigen Form existieren (für unendlich viele n ). nnn
Sasho Nikolov
@mikero, SashoNikolov, ihr beide habt recht, ich entschuldige mich. Ich habe meine Frage bearbeitet.
user834
1
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
1
Beachten Sie, dass , um diese Eigenschaft wahr zu sein, , b k und c k sollte p o l y ( n ) auf Lipton Blog / und in Bitgröße / wie angegeben p o l y ( 2 n ) als ganzen Zahlen . Ihre Definition ist nicht klar. akbkckpoly(n)poly(2n)
Gopi

Antworten:

8

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

(2n)!=k=0m1akbkck
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 ( 2 n ) ergibt ! mod x für x in binärer Form: Berechnen Sie einfach die Summe modulo x unter Verwendung der Potenzierung durch wiederholtes Quadrieren.(2n)!(2n)!modxxx

Nun, wenn wir berechnen könnten ! mod x für willkürliches y könnten wir x faktorisieren: Finden Sie mit der binären Suche das kleinste y, so dass gcd ( x , y ! ) 1 (das wir mit gcd ( x , ( y ! mod x ) ) berechnen können ). Dann muss y der kleinste Primteiler von x sein .y!modxyxygcd(x,y!)1gcd(x,(y!modx))yx

Wenn wir nur Potenzen von für y machen können , können wir trotzdem versuchen, gcd ( x , ( 2 n ) ! ) Für jedes n log x zu berechnen . Einer von diesen wird ein nichttrivialer Teiler von x sein , mit Ausnahme des unglücklichen Falles, wenn es ein n gibt, so dass x gleichbedeutend mit ( 2 n ) ist ! und dividiert ( 2 n + 1 ) ! . Dies ist äquivalent zu der Aussage, dass x2ygcd(x,(2n)!)nlogxxnx(2n)!(2n+1)!xist 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 a k , b k und c k ), wenn man 2 durch eine andere (kleine) Primzahl ersetzt, p . Man könnte vermutlich suchen , bis ein p solche gefunden wird , dass x ist coprime zu ( p n ) ! und nicht ( p n + 1 ) ! nakbkck2ppx(pn)!(pn+1)!
user834