General number field sieve (original) (raw)

About DBpedia

Das Zahlkörpersieb (englisch number field sieve, NFS) ist ein Begriff aus dem mathematischen Teilgebiet der Zahlentheorie. Es ist einer der schnellsten bekannten Algorithmen zur Faktorisierung großer Zahlen. Das Zahlkörpersieb wird vor allem für Zahlen mit über 100 Stellen benutzt, die durch andere Verfahren nicht zerlegt werden konnten. Typischerweise werden dabei mehrere 100 Rechner parallel betrieben.

Property Value
dbo:abstract En matemàtiques, el sedàs de cos de nombre general (GNFS) és l'algorisme clàssic més conegut per factoritzar enters més grans de 100 dígits. Heurísticament, la seva complexitat per factoritzar un enter n (de log n bits) és de la forma (en notacions O i L notacions) per a una constant que depèn de la mesura de complexitat i de la variant de l'algorisme. És una generalització del : mentre que aquest últim només pot factoritzar nombres d'una certa forma especial, el sedàs de cos de nombres general pot factoritzar qualsevol nombre (a banda de , però això és un problema menor). Quan es fa servir el terme sedàs de cos de nombres (NFS) és sense qualificatiu, es refereix al sedàs de cos de nombres general. El principi del sedàs de cos de nombre (tant especial com general) es pot entendre com a ampliació del més simple. Quan es fa servir el sedàs racional per factoritzar un nombre gran n, és necessari buscar (i.e. nombres amb factors primers petits) d'ordre n; la raresa d'aquests fan que el sedàs racional sigui poc pràctic. El sedàs de cos de nombre general, per altra banda, només exigeix una cerca de nombres llisos d'ordre n 1/d , on d és algun enter més gran que u. Ja que els nombres més grans tenen moltes menys possibilitats de ser llissos que els nombres més petits, això és la clau a l'eficiència del sedàs de cos de nombres. Però per a aconseguir això augmentar la velocitat, el sedàs de cos de nombre ha de realitzar càlculs i factorizations en el . Això ocasiona molts aspectes bastant complicats de l'algorisme, en comparació amb el sedàs racional que és més simple. Fixeu-vos que log n és el nombre de dígits en la representació binària de n, això és la mida de l'entrada a l'algorisme. En el (pitjor cas) el temps d'execució és superpolinomic respecte a la mida de l'entrada. És un problema obert important saber si la factorització es pot fer en termini prudencial — temps polinòmic — en un ordinador clàssic. En un ordinador quàntic, la factorització és un problema tractable que fa servir l'algorisme de Shor. (ca) Das Zahlkörpersieb (englisch number field sieve, NFS) ist ein Begriff aus dem mathematischen Teilgebiet der Zahlentheorie. Es ist einer der schnellsten bekannten Algorithmen zur Faktorisierung großer Zahlen. Das Zahlkörpersieb wird vor allem für Zahlen mit über 100 Stellen benutzt, die durch andere Verfahren nicht zerlegt werden konnten. Typischerweise werden dabei mehrere 100 Rechner parallel betrieben. (de) In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an integer n (consisting of ⌊log2 n⌋ + 1 bits) is of the form (in L-notation), where ln is the natural logarithm. It is a generalization of the special number field sieve: while the latter can only factor numbers of a certain special form, the general number field sieve can factor any number apart from prime powers (which are trivial to factor by taking roots). The principle of the number field sieve (both special and general) can be understood as an improvement to the simpler rational sieve or quadratic sieve. When using such algorithms to factor a large number n, it is necessary to search for smooth numbers (i.e. numbers with small prime factors) of order n1/2. The size of these values is exponential in the size of n (see below). The general number field sieve, on the other hand, manages to search for smooth numbers that are subexponential in the size of n. Since these numbers are smaller, they are more likely to be smooth than the numbers inspected in previous algorithms. This is the key to the efficiency of the number field sieve. In order to achieve this speed-up, the number field sieve has to perform computations and factorizations in number fields. This results in many rather complicated aspects of the algorithm, as compared to the simpler rational sieve. The size of the input to the algorithm is log2 n or the number of bits in the binary representation of n. Any element of the order nc for a constant c is exponential in log n. The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input. (en) En théorie des nombres, l'algorithme du crible du corps de nombres généralisé (GNFS) obtient la décomposition d'un entier en produit de facteurs premiers. C'est à l'heure actuelle (2018) le plus efficace algorithme connu pour obtenir cette décomposition, lorsque le nombre considéré est assez grand, c'est-à-dire au-delà d'environ 10100, et ne possède pas de structure remarquable. Cette efficacité est due pour partie à l'utilisation d'une méthode de crible et pour partie à l'utilisation d'algorithmes efficaces pour certaines opérations (comme la manipulation de matrices creuses). La complexité algorithmique du crible de corps de nombres n'est pas prouvée, elle n'est qu'heuristique. Cette estimation est utilisée par les organismes de standardisation tels que le NIST pour fixer des tailles des clés RSA à un niveau de sécurité donné. De manière remarquable, l'algorithme permet également (au prix de modifications simples) de calculer des logarithmes discrets dans les corps finis, avec la même complexité. C'est à l'heure actuelle (2018) l'algorithme le plus efficace connu dans les corps finis de caractéristique première très grande. En revanche, l'algorithme du crible du corps de nombres n'est pas applicable au calcul du logarithme discret dans un groupe abstrait générique, ce qui est une des motivations derrière la cryptographie sur les courbes elliptiques. Pour ces raisons, l'algorithme est responsable aujourd'hui de nombreux records de factorisation (et de calculs de logarithmes discrets) et joue un rôle important en cryptographie. Enfin, quoique de manière plus anecdotique, il intervient également dans le contexte plus large de la sécurité informatique, par exemple dans l' dont il est un composant essentiel : les auteurs ont montré comment intercepter une communication TLS 1.2, une des étapes consistant à calculer au moyen du crible du corps de nombres un logarithme discret dans un corps de 512 bits en moins d'une minute. (fr) En teoría de números, la criba general del cuerpo de números (del inglés general number field sieve (GNFS) es el algoritmo clásico conocido más eficiente para factorizar enteros mayores de 100 dígitos. Heurísticamente, su complejidad para factorizar un entero n (consistente en log2 n bits) es de la forma (en ), donde ln es el logaritmo en base e.​ Es una generalización de la criba especial del cuerpo de números: mientras que el último puede factorizar únicamente números de una cierta forma especial, la criba general del cuerpo de números puede factorizar cualquier número aparte de potencias primas (que es trivial factorizar tomando raíces). Cuando el término en inglés number field sieve (NFS) es usado sin calificación, este se refiere a la criba general del cuerpo de números. El principio de la criba del cuerpo de números (ambas, especial y general) se puede entender como una mejora de la más simple criba racional o criba cuadrática. Cuando se usan tales algoritmos para factorizar un número grande n, es necesaria la búsqueda de números lisos (i.e. números con factores primos pequeños) de orden n1/2. El tamaño de esos valores es exponencial en el tamaño de n (véase después). La criba general del cuerpo de números, por otra parte, gestiona la búsqueda de números lisos que sean subexponenciales en el tamaño de n. Puesto que esos números son más pequeños, son más propensos a ser lisos que los números evaluados en los algoritmos anteriores. Esta es la clave de la eficiencia de la criba del cuerpo de números. Con el fin de lograr esta aceleración, la criba del cuerpo de números tiene que realizar los cálculos y factorizaciones en cuerpos numéricos. Esto resulta en muchos aspectos lo más complicado del algoritmo, si lo comparamos con la más simple criba racional. Nótese que log2 n es el número de bits en la representación binaria del n, que es el tamaño de la entrada para el algoritmo, así que cualquier elemento de orden nc para una constante c es exponencial en log n. El tiempo de ejecución de la criba del cuerpo de números es super-polinomial pero sub-exponencial en el tamaño de la entrada. (es) 수체 체 (General Number Field Sieve) 알고리즘은 어떤 양의 정수 N을 빠르게 소인수분해할 수 있는 소인수분해 알고리즘이다. 이 알고리즘은 일반적으로 소인수분해하고자 하는 수가 100자리가 넘을 때 이차 체보다 빨라지게 되고, 일반적인 컴퓨터로 실행할 수 있는 소인수분해 알고리즘 중에서 가장 빠르며, 보통 100자리가 넘는 정수에 대해서 사용한다. RSA-704, RSA-768 등을 소인수분해할 때 사용되었고, 200번째 베르누이 수의 분자를 소인수분해할 때에도 사용되었다. (ko) De getallenlichamenzeef is een algoritme om samengestelde getallen te ontbinden in priemfactoren. De basis van deze methode is rond 1988 ontwikkeld door de Britse wiskundige John Pollard, die daarmee het zevende fermatgetal factoriseerde. In de jaren daarna zijn verschillende verbeteringen aangebracht, onder andere door Arjen en Hendrik Lenstra, waardoor het momenteel een van de snelste algoritmen is om een getal te factoriseren. Vooral voor getallen vanaf 100 cijfers is deze methode zeer geschikt; kleinere getallen kunnen sneller met de kwadratische zeef, een eenvoudigere methode om getallen te ontbinden, worden gefactoriseerd. (nl) In matematica, il crivello dei campi di numeri generale (noto anche semplicemente come crivello dei campi di numeri o anche GNFS, dall'inglese general number field sieve) è il più efficiente algoritmo classico conosciuto per fattorizzare gli interi con più di 100 cifre. Euristicamente, la sua complessità computazionale, per fattorizzare un intero n è (vedi notazione O grande), ove c è una costante che dipende dalla variante dell'algoritmo utilizzata. È una generalizzazione del crivello dei campi di numeri speciale. A differenza di quest'ultimo che può essere utilizzato solo su numeri di una particolare forma, il crivello dei campi di numeri generale può essere utilizzato per fattorizzare ogni numero (ad eccezione delle potenze dei primi, che però si possono fattorizzare facilmente con altri metodi). Il crivello dei campi di numeri (sia generale che speciale) può essere considerato un'estensione del più semplice . Per fattorizzare un intero grande n, quest'ultimo algoritmo ha bisogno di trovare numeri dello stesso ordine di n che hanno fattori primi piccoli; la rarità di questi numeri rende di fatto inutilizzabile il rational sieve. Per ovviare a questo problema, il crivello dei campi di numeri sposta il problema negli anelli degli interi di alcuni campi di numeri. Questo approccio, pur introducendo alcune complicazioni teoriche, rende sufficiente cercare gli interi con fattori primi piccoli tra i numeri di ordine n1/d, ove d è un intero maggiore di 1. Dato che i numeri più piccoli hanno generalmente fattori primi più piccoli, questa modifica aumenta notevolmente l'efficienza del metodo. Si noti che log n è essenzialmente il numero di cifre nella rappresentazione binaria di n e di conseguenza, nei casi peggiori, il tempo necessario per compiere una fattorizzazione è più che polinomiale (nel numero delle cifre). Non è ancora noto, se esistono degli algoritmi per computer classici che risolvono il problema della fattorizzazione in un tempo polinomiale, mentre ne è stato trovato uno, l'algoritmo di fattorizzazione di Shor, che risolve il problema per i computer quantistici. (it) 数論において、一般数体篩法（いっぱんすうたいふるいほう、英: General number field sieve, GNFS）は、10100より大きい整数を素因数分解する古典的アルゴリズムであり、現在知られている最もなものである。ヒューリスティックに、整数 n （ ⌊log2 n⌋ + 1 ビットで構成される）を素因数分解するための複雑性は、(L-notation)を用いて以下のように表される。 ここで、 ln は自然対数である。これは(special number field sieve)の一般化である：特殊数体篩法は特定形式の数のみを素因数分解できるが、一般数体篩法は素数冪（根を求めることで素因数分解は容易である）以外の任意の数を素因数分解できる。 （特殊・一般）数体篩法の原理は、より単純な(rational sieve)や(quadratic sieve)の改良ととらえることができる。このようなアルゴリズムを用いて大きな数 n を素因数分解する場合、 n1/2 次の(smooth number)（つまり、小さな素因数を持つ数）を探す必要がある。これらの値の大きさは、 n の大きさに対して指数関数的である（後述）。一方、一般数体篩法は、 n の大きさに対して準指数関数的な滑らかな数を検索することができる。値が小さくなるため、上のアルゴリズムで調べられる値よりも滑らかである可能性が高くなる。これが一般数体篩法の効率性の鍵である。このスピードアップのためには、一般数体篩法は数体内で計算と素因数分解を行う必要がある。そのため、単純な有理篩法と比較して、アルゴリズムに複雑な部分が多くなる。 アルゴリズムへの入力のサイズは log2 n 、つまり n の二進表現のビット数である。定数 c について、 nc 次のどの要素も、log n の指数関数的である。数体篩法の実行時間は入力のサイズに対して超多項式的であるが、準指数関数的である。 (ja) Общий метод решета числового поля (англ. general number field sieve, GNFS) — метод факторизации целых чисел. Является наиболее эффективным алгоритмом факторизации чисел длиной более 110 десятичных знаков. Сложность алгоритма оценивается эвристической формулой Метод является обобщением специального метода решета числового поля: тогда как последний позволяет факторизовать числа только некоторого специального вида, общий метод работает на множестве целых чисел, за исключением степеней простых чисел (которые факторизуются тривиально извлечением корней). (ru) Ogólne sito ciała liczbowego (GNFS, ang. General Number Field Sieve) jest najszybszym obecnie znanym algorytmem faktoryzacji dużych (ponad 100-cyfrowych) liczb. Używając tego algorytmu, zespół z Uniwersytetu w Bonn (wspólnie z kilkoma innymi instytutami) 3 grudnia 2003 rozłożył na czynniki pierwsze liczbę RSA-576 (mającą 576 bitów, czyli 174 cyfry dziesiętne), a 2 listopada 2005 rozłożył liczbę RSA-640 (mającą 193 cyfry dziesiętne). Pierwsze obliczenie wymagało około 3 miesięcy pracy, a drugie około 5 miesięcy. (pl) Na teoria dos números, um ramo da matemática, o campo de número de peneira geral, (em inglês: GNFS) é o mais eficiente algoritmo clássico, conhecido por fatorar inteiros maiores do que 100 dígitos. O segundo melhor algoritmo clássico, conhecido por fatoração inteiro é o método de . É melhor do que o campo de número de peneira geral quando factores são pequenos, uma vez que funciona olhando para valores normais da ordem do menor divisor primo de , o seu tempo de funcionamento depende do tamanho do divisor. Heuristicamente, a sua complexidade para fatorar um número inteiro (composto de bits) é da forma: em , onde é o logaritmo natural. (pt) 在数论中，普通数域筛选法（GNFS）是已知效率最高的分解整数的算法。分解整数n（由⌊log2 n⌋ + 1个位元组成）需要 步（参见L符号）。它是从引申出来的。如果条件数域筛没有限定条件，就是指普通数域筛选。 (zh) У теорії чисел метод решета числового поля є найбільш ефективним серед алгоритмів факторизації чисел, що більші ніж 10100. Складність факторизації цілого числа n за допомогою методу решета числового поля оцінюється евристичною формулою: Метод є узагальненням методу спеціального решета числового поля. На відміну від останнього, котрий факторизує тільки числа спеціального вигляду, він працює на всій множині цілих чисел, окрім степенів простих чисел. (uk)
dbo:wikiPageExternalLink http://cado-nfs.inria.fr/ http://escatter11.fullerton.edu/nfs/ http://www.math.ttu.edu/~cmonico/software/ggnfs/ http://kmgnfs.cti.gr http://sourceforge.net/projects/msieve/ https://sourceforge.net/projects/factor-by-gnfs/
dbo:wikiPageID 152734 (xsd:integer)
dbo:wikiPageLength 13294 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1113306242 (xsd:integer)
dbo:wikiPageWikiLink dbr:Prime_power dbr:Monic_polynomial dbr:Algebraic_number_field dbr:Algorithm dbr:Algorithmic_efficiency dbc:Integer_factorization_algorithms dbr:Homomorphism dbr:Ring_of_integers dbr:United_Kingdom dbr:Degree_of_a_polynomial dbr:Integer_factorization dbr:Internet dbr:L-notation dbr:Special_number_field_sieve dbr:GPL dbr:Gaussian_elimination dbr:Greatest_common_divisor dbr:Modular_arithmetic dbr:Computational_complexity_theory dbr:Centrum_Wiskunde_&_Informatica dbr:Cunningham_project dbr:Irreducible_polynomial dbr:Lattice_sieving dbr:Algebraic_number dbr:Number_field dbr:Number_theory dbr:Carl_Pomerance dbr:Quadratic_sieve dbr:Radix dbr:Hendrik_Lenstra dbr:Arjen_Lenstra dbr:Block_Wiedemann_algorithm dbr:Heuristic dbr:Polynomial dbr:Field_norm dbr:Natural_logarithm dbr:Rational_number dbr:Rational_sieve dbr:Root_of_a_function dbr:Smooth_number dbr:Paul_Leyland dbr:Block_Lanczos_algorithm_for_nullspace_of_a_matrix_over_a_finite_field dbr:Jason_Papadopoulos dbr:Thorsten_Kleinjung
dbp:wikiPageUsesTemplate dbt:= dbt:Citation_needed dbt:Confusing dbt:ISBN dbt:Main dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Number_theoretic_algorithms
dct:subject dbc:Integer_factorization_algorithms
rdf:type yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatIntegerFactorizationAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms
rdfs:comment Das Zahlkörpersieb (englisch number field sieve, NFS) ist ein Begriff aus dem mathematischen Teilgebiet der Zahlentheorie. Es ist einer der schnellsten bekannten Algorithmen zur Faktorisierung großer Zahlen. Das Zahlkörpersieb wird vor allem für Zahlen mit über 100 Stellen benutzt, die durch andere Verfahren nicht zerlegt werden konnten. Typischerweise werden dabei mehrere 100 Rechner parallel betrieben. (de) 수체 체 (General Number Field Sieve) 알고리즘은 어떤 양의 정수 N을 빠르게 소인수분해할 수 있는 소인수분해 알고리즘이다. 이 알고리즘은 일반적으로 소인수분해하고자 하는 수가 100자리가 넘을 때 이차 체보다 빨라지게 되고, 일반적인 컴퓨터로 실행할 수 있는 소인수분해 알고리즘 중에서 가장 빠르며, 보통 100자리가 넘는 정수에 대해서 사용한다. RSA-704, RSA-768 등을 소인수분해할 때 사용되었고, 200번째 베르누이 수의 분자를 소인수분해할 때에도 사용되었다. (ko) De getallenlichamenzeef is een algoritme om samengestelde getallen te ontbinden in priemfactoren. De basis van deze methode is rond 1988 ontwikkeld door de Britse wiskundige John Pollard, die daarmee het zevende fermatgetal factoriseerde. In de jaren daarna zijn verschillende verbeteringen aangebracht, onder andere door Arjen en Hendrik Lenstra, waardoor het momenteel een van de snelste algoritmen is om een getal te factoriseren. Vooral voor getallen vanaf 100 cijfers is deze methode zeer geschikt; kleinere getallen kunnen sneller met de kwadratische zeef, een eenvoudigere methode om getallen te ontbinden, worden gefactoriseerd. (nl) Общий метод решета числового поля (англ. general number field sieve, GNFS) — метод факторизации целых чисел. Является наиболее эффективным алгоритмом факторизации чисел длиной более 110 десятичных знаков. Сложность алгоритма оценивается эвристической формулой Метод является обобщением специального метода решета числового поля: тогда как последний позволяет факторизовать числа только некоторого специального вида, общий метод работает на множестве целых чисел, за исключением степеней простых чисел (которые факторизуются тривиально извлечением корней). (ru) Ogólne sito ciała liczbowego (GNFS, ang. General Number Field Sieve) jest najszybszym obecnie znanym algorytmem faktoryzacji dużych (ponad 100-cyfrowych) liczb. Używając tego algorytmu, zespół z Uniwersytetu w Bonn (wspólnie z kilkoma innymi instytutami) 3 grudnia 2003 rozłożył na czynniki pierwsze liczbę RSA-576 (mającą 576 bitów, czyli 174 cyfry dziesiętne), a 2 listopada 2005 rozłożył liczbę RSA-640 (mającą 193 cyfry dziesiętne). Pierwsze obliczenie wymagało około 3 miesięcy pracy, a drugie około 5 miesięcy. (pl) 在数论中，普通数域筛选法（GNFS）是已知效率最高的分解整数的算法。分解整数n（由⌊log2 n⌋ + 1个位元组成）需要 步（参见L符号）。它是从引申出来的。如果条件数域筛没有限定条件，就是指普通数域筛选。 (zh) У теорії чисел метод решета числового поля є найбільш ефективним серед алгоритмів факторизації чисел, що більші ніж 10100. Складність факторизації цілого числа n за допомогою методу решета числового поля оцінюється евристичною формулою: Метод є узагальненням методу спеціального решета числового поля. На відміну від останнього, котрий факторизує тільки числа спеціального вигляду, він працює на всій множині цілих чисел, окрім степенів простих чисел. (uk) En matemàtiques, el sedàs de cos de nombre general (GNFS) és l'algorisme clàssic més conegut per factoritzar enters més grans de 100 dígits. Heurísticament, la seva complexitat per factoritzar un enter n (de log n bits) és de la forma (ca) En teoría de números, la criba general del cuerpo de números (del inglés general number field sieve (GNFS) es el algoritmo clásico conocido más eficiente para factorizar enteros mayores de 100 dígitos. Heurísticamente, su complejidad para factorizar un entero n (consistente en log2 n bits) es de la forma (es) In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an integer n (consisting of ⌊log2 n⌋ + 1 bits) is of the form (in L-notation), where ln is the natural logarithm. It is a generalization of the special number field sieve: while the latter can only factor numbers of a certain special form, the general number field sieve can factor any number apart from prime powers (which are trivial to factor by taking roots). (en) En théorie des nombres, l'algorithme du crible du corps de nombres généralisé (GNFS) obtient la décomposition d'un entier en produit de facteurs premiers. C'est à l'heure actuelle (2018) le plus efficace algorithme connu pour obtenir cette décomposition, lorsque le nombre considéré est assez grand, c'est-à-dire au-delà d'environ 10100, et ne possède pas de structure remarquable. Cette efficacité est due pour partie à l'utilisation d'une méthode de crible et pour partie à l'utilisation d'algorithmes efficaces pour certaines opérations (comme la manipulation de matrices creuses). La complexité algorithmique du crible de corps de nombres n'est pas prouvée, elle n'est qu'heuristique. Cette estimation est utilisée par les organismes de standardisation tels que le NIST pour fixer des tailles des (fr) In matematica, il crivello dei campi di numeri generale (noto anche semplicemente come crivello dei campi di numeri o anche GNFS, dall'inglese general number field sieve) è il più efficiente algoritmo classico conosciuto per fattorizzare gli interi con più di 100 cifre. Euristicamente, la sua complessità computazionale, per fattorizzare un intero n è (it) 数論において、一般数体篩法（いっぱんすうたいふるいほう、英: General number field sieve, GNFS）は、10100より大きい整数を素因数分解する古典的アルゴリズムであり、現在知られている最もなものである。ヒューリスティックに、整数 n （ ⌊log2 n⌋ + 1 ビットで構成される）を素因数分解するための複雑性は、(L-notation)を用いて以下のように表される。 ここで、 ln は自然対数である。これは(special number field sieve)の一般化である：特殊数体篩法は特定形式の数のみを素因数分解できるが、一般数体篩法は素数冪（根を求めることで素因数分解は容易である）以外の任意の数を素因数分解できる。 アルゴリズムへの入力のサイズは log2 n 、つまり n の二進表現のビット数である。定数 c について、 nc 次のどの要素も、log n の指数関数的である。数体篩法の実行時間は入力のサイズに対して超多項式的であるが、準指数関数的である。 (ja) Na teoria dos números, um ramo da matemática, o campo de número de peneira geral, (em inglês: GNFS) é o mais eficiente algoritmo clássico, conhecido por fatorar inteiros maiores do que 100 dígitos. O segundo melhor algoritmo clássico, conhecido por fatoração inteiro é o método de . É melhor do que o campo de número de peneira geral quando factores são pequenos, uma vez que funciona olhando para valores normais da ordem do menor divisor primo de , o seu tempo de funcionamento depende do tamanho do divisor. Heuristicamente, a sua complexidade para fatorar um número inteiro (composto de bits) é da forma: (pt)
rdfs:label Garbell sobre el cos de nombres generalitzat (ca) Zahlkörpersieb (de) Criba general del cuerpo de números (es) General number field sieve (en) Crible algébrique (fr) Crivello dei campi di numeri generale (it) 一般数体篩法 (ja) 수체 체 (ko) Getallenlichamenzeef (nl) GNFS (pl) Campo de número de peneira geral (pt) Общий метод решета числового поля (ru) 普通数域筛选法 (zh) Метод решета числового поля (uk)
owl:sameAs freebase:General number field sieve yago-res:General number field sieve wikidata:General number field sieve dbpedia-ca:General number field sieve dbpedia-de:General number field sieve dbpedia-es:General number field sieve dbpedia-fi:General number field sieve dbpedia-fr:General number field sieve dbpedia-he:General number field sieve dbpedia-it:General number field sieve dbpedia-ja:General number field sieve dbpedia-ko:General number field sieve dbpedia-nl:General number field sieve dbpedia-pl:General number field sieve dbpedia-pt:General number field sieve dbpedia-ru:General number field sieve dbpedia-th:General number field sieve dbpedia-uk:General number field sieve dbpedia-zh:General number field sieve https://global.dbpedia.org/id/Qjdd
prov:wasDerivedFrom wikipedia-en:General_number_field_sieve?oldid=1113306242&ns=0
foaf:isPrimaryTopicOf wikipedia-en:General_number_field_sieve
is dbo:wikiPageDisambiguates of dbr:Sieve_(disambiguation)
is dbo:wikiPageRedirects of dbr:Number_field_sieve dbr:General_Number_Field_Sieve dbr:NFSNet dbr:GNFS dbr:Sieving_with_large_primes dbr:NFSNET dbr:Number_Field_Sieve
is dbo:wikiPageWikiLink of dbr:List_of_algorithms dbr:Number_field_sieve dbr:Integer_factorization dbr:International_Association_for_Cryptologic_Research dbr:L-notation dbr:List_of_number_theory_topics dbr:Special_number_field_sieve dbr:Quadratic_residue dbr:Quantum_algorithm dbr:Timeline_of_algorithms dbr:General_Number_Field_Sieve dbr:NFSNet dbr:Congruence_of_squares dbr:Lenstra_elliptic-curve_factorization dbr:Shor's_algorithm dbr:Computational_complexity_of_mathematical_operations dbr:Computational_complexity_theory dbr:Time_complexity dbr:Trial_division dbr:Texas_Instruments_signing_key_controversy dbr:TI-84_Plus_series dbr:Quadratic_sieve dbr:RSA_numbers dbr:Prime_number dbr:Arjen_Lenstra dbr:Fermat's_factorization_method dbr:RSA_(cryptosystem) dbr:Rational_sieve dbr:Sieve_(disambiguation) dbr:Sieve_theory dbr:Smooth_number dbr:Supersingular_isogeny_key_exchange dbr:TWIRL dbr:Factor_base dbr:List_of_volunteer_computing_projects dbr:P_versus_NP_problem dbr:GNFS dbr:Sieving_with_large_primes dbr:NFSNET dbr:Number_Field_Sieve
is foaf:primaryTopic of wikipedia-en:General_number_field_sieve