Quelle est la complexité la plus défavorable du tamis de champ numérique?

Compte tenu composite $N\in\Bbb N$ tamis de champ numérique général est le meilleur algorithme de factorisation connu pour factorisation entier de $N$ . Il s'agit d'un algorithme randomisé et nous obtenons une complexité attendue de $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$ à facteur $N$ .

J'ai cherché des informations sur la complexité du pire des cas sur cet algorithme randomisé. Cependant, je ne parviens pas à localiser les informations.

(1) Quelle est la complexité la plus défavorable du tamis à champ numérique?

(2) Le caractère aléatoire peut-il également être supprimé ici pour donner un algorithme sous-exponentiel déterministe?

reference-request derandomization factoring average-case-complexity worst-case
la source

Réponses:

$e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$

$x$ $x^2 \pmod{n}$ $n$ $n$

La complexité nominale du pire des cas de tous ces algorithmes est infinie: dans le cas du tamis quadratique et du tamis à champ numérique, vous pourriez toujours générer le même , tandis que dans la méthode de la courbe elliptique, vous pourriez toujours générer la même courbe elliptique . Il existe de nombreuses façons de contourner cela, par exemple en exécutant un algorithme de temps exponentiel en parallèle. $x$

Yuval Filmus
la source

Puisque vous avez également abordé ECM: nous connaissons un algorithme randomisé sous-exp pour calculer en temps utilisant ECM où est inconnu et randomisé. Avez-vous une estimation du nombre d'essais de cet algorithme suffisant pour obtenir et où ?

n! r

$n!r$

O (e x p (\sqrt{\log n}))

$O(exp(\sqrt{\log n}))$

r

$r$

n! r

$n!r$

n! s

$n!s$

(r, s) = 1

$(r,s)=1$

Je n'ai aucune idée de ce que est , mais d'une manière générale, lors du choix des paramètres dans ECM, nous équilibrons entre la probabilité que la courbe soit suffisamment lisse et le temps d'exécution requis pour tester chaque courbe. En général , le point d'équilibre est quand . Le nombre d'essais attendu doit donc être .

n! r

$n!r$

p

$p$

T

$T$

1 / p \approx T

$1/p \approx T$

O (\exp \sqrt{\log n})

$O(\exp\sqrt{\log n})$

Yuval Filmus

n!

$n!$ est factorielle de . C'est un problème ouvert pour obtenir la complexité en ligne droite de factorielle. Nous savons calculer où est inconnu en temps subexp. Si nous connaissons deux et , nous pouvons obteniren temps subexp si .

n

$n$

n! r

$n!r$

r

$r$

n! r

$n!r$

n! s

$n!s$

(n! r, n! s) = n!

$(n!r,n!s)=n!$

(r, s) = 1

$(r,s)=1$

Je me souviens avoir calculé il y a quelque temps. Je ne pense pas que je pourrais obtenir une amélioration car il y avait un hic et je ne me souviens pas des détails.

le dernier paragraphe semble étrange et pourrait être clarifié davantage. parlez-vous d'un scénario où le RNG est "cassé" dans le sens où il n'échantillonne pas l'espace de distribution global? mais alors le parallélisme ne serait-il pas là? parce que ce serait le même RNG "cassé" en parallèle? ou est-ce l'idée que ce serait un RNG différent exécuté en parallèle? en fait, la complexité parallèle des algorithmes d'affacturage est vraiment un tout autre sujet complexe, par exemple certains peuvent être parallélisés mieux que d'autres, le big-O peut ne pas être exactement applicable, etc.

vzn

Au cours des derniers mois, une version du tamis numérique a été rigoureusement analysée: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring

Fondamentalement, le temps d'exécution le plus défavorable est sans condition et sous GRH. Ce n'est pas pour le tamis de champ numérique "classique", mais une version légèrement modifiée qui randomise plus d'étapes afin de faciliter l'analyse de la complexité. $L_n(1/3, 2.77)$ $L_n(1/3, (64/9)^{1/3})$

Je pense que le document correspondant est toujours en cours d'examen.

Mise à jour: le document est maintenant disponible. Jonathan D. Lee et Ramarathnam Venkatesan, "Analyse rigoureuse d'un tamis à champ de nombres aléatoires", Journal of Number Theory 187 (2018), pp. 92-159, doi: 10.1016 / j.jnt.2017.10.019

djao
la source

Pouvez-vous donner une référence plus complète où nous pouvons en savoir plus, avec le titre, l'auteur et le lieu de publication, afin que la réponse soit toujours utile même si le lien cesse de fonctionner?

Étant donné que le résultat n'a été annoncé que récemment, je pense qu'il est actuellement en cours d'examen, comme indiqué dans ma réponse, et qu'il n'est donc pas encore publié. Je mettrai à jour ma réponse à l'avenir lorsque les informations de publication seront disponibles.

djao

FWIW il ne semble pas être sur arxiv.org. Cependant, l'auteur est Ramarathnam Venkatesan, ce qui peut aider les recherches futures si elles sont nécessaires.

Peter Taylor

Il s'agit en fait d'une œuvre à deux auteurs (JD Lee et R. Venkatesan): cmi.ac.in/activities/…

Sary