?

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$
$(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}$ $m = poly(n)$ $a_k$ $b_k$ $c_k$ $poly(n)$

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

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 )? $n$ $m$ $a_k$ $b_k$ $c_k$ $NP$

ds.algorithms reference-request factoring comp-number-theory user834
la source

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.

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

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

mikero

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

) alors les équations de la forme ci-dessus n'existent pas (pour une infinité de

n

$n$

n

$n$

n

$n$

Sasho Nikolov

@mikero, SashoNikolov, vous avez tous les deux raison, mes excuses. J'ai édité ma question.

user834

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

Notez que pour que cette propriété soit vraie,

doivent être

en taille de bit / comme indiqué sur le blog de Lipton /, et

comme entiers . Votre définition n'est pas claire.

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

Réponses:

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

(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$

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 pour donné en binaire: évaluez simplement la somme modulo , en utilisant l'exponentiation par quadrature répétée. $(2^n)!$ $(2^n)!\bmod x$ $x$ $x$

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

Si nous ne pouvons faire que des puissances de pour , nous pouvons toujours essayer de calculer Pour chaque . L'un d'entre eux sera un diviseur non trivial de , sauf dans le cas malheureux où il y a un tel que est coprime à , et divise . Cela revient à dire que $2$ $y$ $\gcd(x,(2^n)!)$ $n\le\log x$ $x$ $n$ $x$ $(2^n)!$ $(2^{n+1})!$ $x$ est 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

) quand on remplace

par un autre (petit) premier,

. On pourrait probablement chercher jusqu'à ce qu'un

soit trouvé tel que

soit coprime à

et non

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