Que sait-on de la complexité de calcul de la factorisation d'entiers dans des champs de nombres généraux? Plus précisement: Sur les entiers, nous représentons des entiers via leurs extensions binaires. Quelles sont les représentations analogues d'entiers dans des champs numériques généraux? Est-il...
Rappelons le nombre de nombres premiers est la fonction de décompte des nombres premiers . Par "PRIMES in P", le calcul est en #P. Le problème # P-est-il complet? Ou, peut-être, il y a une raison complexe de croire que ce problème n'est pas # P-complet? π(n)π(n)\pi(n)≤n≤n\le nπ ( n )π(n)π(n)\pi(n)...
Quels sont les algorithmes efficaces connus pour calculer un déterminant d'une matrice entière à coefficients dans , l'anneau de résidus modulo . Le nombre peut ne pas être premier mais composite (donc les calculs sont effectués en anneau, pas dans un champ). mmZmZm\mathbb{Z}_mmmmmmm Pour autant...
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
D'après les commentaires sur une de mes questions sur mathoverflow je le sentiment que la question concernant GCD étant en par rapport à P est semblable à la question concernant Integer factorisation être dans P par rapport à N P .N CNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}N PNP\mathsf{NP} Y at - il...
Quelle est la complexité de décider si un intervalle des nombres naturels contient un nombre premier? Une variante du tamis d'Ératosthène donne un algorithme O~(L)O~(L)\tilde O(L) , où LLL est la longueur de l'intervalle et ∼∼\sim cache les facteurs poly-logarithmiques au point de départ de...
La fonction Mobius est définie comme , si a un facteur premier carré, et si tous les nombres premiers sont différents. Est-il possible de calculer sans calculer la factorisation première de ?μ ( 1 ) = 1 μ ( n
J'essaie de comprendre à quelle classe de complexité appartient le problème suivant: Exponentiating Polynomial Root Problem (EPRP) Soit un polynôme avec deg ( p ) ≥ 0 avec des coefficients tirés d'un champ fini G F ( q ) avec q un nombre premier, et r une racine primitive pour ce champ. Déterminez...
Sean Anderson a publié des hacks twiddling contenant l'algorithme d'Eric Cole pour trouver le ⌈log2v⌉⌈log2v⌉\lceil\log_2 v \rceil d'un entier à NNN bits vvv dans les opérations O(lg(N))O(lg(N))O(\lg(N)) avec multiplication et recherche. L'algorithme repose sur un nombre "magique" de la séquence...
Y at - il un nombre transcendantal calculable connu tel que son ième chiffre est calculable en temps polynomial, mais pas dans O ( n ) ?nnnO ( n
Étant donné le coprime , pouvez-vous calculer rapidementa,ba,ba, bminx,y>0|ax−by|minx,y>0|ax−by| \min_{x, y > 0} |a^x - b^y| Ici x,yx,yx, y sont des entiers. Évidemment, prendre x=y=0x=y=0x = y = 0 donne une réponse sans intérêt; en général, à quel point ces pouvoirs peuvent-ils se...