?

16

En lisant le blog de Dick Lipton, je suis tombé sur le fait suivant vers la fin de son billet Bourne Factor :

Si, pour tout , il existe une relation de la forme où , et chacun des , et ont une longueur de bits , puis l'affacturage a un polynôme circuits de taille.n

(2n)!=k=0m1akbkck
m=poly(n)akbkckpoly(n)

En d'autres termes, le, qui a un nombre exponentiel de bits , peut potentiellement être représenté efficacement.(2n)!

J'ai quelques questions:

  • Quelqu'un pourrait-il fournir une preuve de la relation ci-dessus, me dire le nom et / ou fournir des références?
  • Si je devais vous donner , et chacun des , et , pourriez-vous me fournir un algorithme de temps polynomial pour vérifier la validité de la relation (c.-à-d. Est-ce en )?nmakbkckNP
user834
la source
4
Ce billet de blog ne revendique-t-il pas réellement l'inverse? Autrement dit, si les équations de la forme ci-dessus ont des solutions en général , alors l'affacturage a des circuits de taille polynomiale. (2n)!=
mikero
3
Je pense que vous avez écrit l'inverse de ce que Dick Lipton a écrit. Il dit que si une telle équation existe pour tout , alors l'affacturage a des circuits de taille polynomiale. L'implication est donc que si l'affacturage est dur de manière non uniforme (pour une infinité de n ) alors les équations de la forme ci-dessus n'existent pas (pour une infinité de n ). nnn
Sasho Nikolov
@mikero, SashoNikolov, vous avez tous les deux raison, mes excuses. J'ai édité ma question.
user834
1
notons que "algorithme de temps polynomial" signifie généralement un algorithme uniforme. Le billet de Lipton affirme seulement l'existence d'une famille de circuits polysize pour l'affacturage.
Sasho Nikolov
1
Notez que pour que cette propriété soit vraie, , b k et c k doivent être p o l y ( n ) en taille de bit / comme indiqué sur le blog de Lipton /, et p o l y ( 2 n ) comme entiers . Votre définition n'est pas claire. akbkckpoly(n)poly(2n)
Gopi

Réponses:

8

Je vais expliquer pourquoi une relation comme dans la question (pour chaque n ) aide à l'affacturage. Je ne peux pas tout à fait terminer l'argument, mais peut-être que quelqu'un le peut.

(2n)!=k=0m1akbkck
n

La première observation est qu'une relation comme ci-dessus (et plus généralement, l'existence de circuits arithmétiques poly-taille pour ) Donne un circuit poly-taille pour le calcul ( 2 n ) ! mod x pour x donné en binaire: évaluez simplement la somme modulo x , en utilisant l'exponentiation par quadrature répétée.(2n)!(2n)!modxxx

Maintenant, si nous pouvions calculer pour y arbitraire , nous pourrions factoriser x : en utilisant la recherche binaire, trouver le plus petit y tel que gcd ( x , y ! ) 1 (que nous pouvons calculer en utilisant gcd ( x , ( y ! mod x ) ) ). Alors y doit être le plus petit diviseur premier de x .y!modxyxygcd(x,y!)1gcd(x,(y!modx))yx

Si nous ne pouvons faire que des puissances de pour y , nous pouvons toujours essayer de calculer gcd ( x , ( 2 n ) ! ) Pour chaque n log x . L'un d'entre eux sera un diviseur non trivial de x , sauf dans le cas malheureux où il y a un n tel que x est coprime à ( 2 n ) ! , et divise ( 2 n + 1 ) ! . Cela revient à dire que x2ygcd(x,(2n)!)nlogxxnx(2n)!(2n+1)!xest sans carré, et tous ses facteurs premiers ont la même longueur de bits. Je ne sais pas quoi faire dans ce cas (plutôt important, cf. Blum integers).

Emil Jeřábek soutient Monica
la source
Si la relation est vraie (pour tout ), alors peut-être aussi (avec un choix différent de a k , b k et c k ) quand on remplace 2 par un autre (petit) premier, p . On pourrait probablement chercher jusqu'à ce qu'un p soit trouvé tel que x soit coprime à ( p n ) ! et non ( p n + 1 ) ! nakbkck2ppx(pn)!(pn+1)!
user834