Special number field sieve (original) (raw)
특수 수체 체(Special Number Field Sieve, SNFS)는 특수한 꼴의 자연수를 매우 빠르게 소인수분해할 수 있는 알고리즘이다. 이 알고리즘은 re ± s 꼴의 수를 빠르게 소인수분해할 수 있으며, 보통 지수가 작은 메르센 수를 소인수분해할 때 많이 쓰이는 알고리즘이다. 또한 수체 체는 특수 수체 체의 변형된 방법으로, 모든 자연수 n을 빠르게 소인수분해할 수 있는 알고리즘이지만 특수 수체 체보다는 느리다. 이 알고리즘의 실행 시간은 이며, 보통 r과 s가 작은 수일 때 잘 작동한다.
| Property | Value |
|---|---|
| dbo:abstract | La criba especial del cuerpo de números (en inglés special number field sieve, SNFS) es un algoritmo especializado de factorización de números enteros. La criba (general) del cuerpo de números (GNFS) es una versión generalizada de este algoritmo que trata con números de todo tipo. Su tiempo de ejecución y complejidad en notación de Landau parece ser: La criba especial de cuerpo de números es eficaz para los números de la forma , donde y son pequeños. Se recomienda pues especialmente para descomponer en factores los números de Fermat y los números de Mersenne.NFSNET utilizó la SNFS mucho y de otros para descomponer en factores los números del proyecto de Cunningham. (es) Le crible spécial de corps de nombres (SNFS) est un algorithme spécialisé de factorisation en nombres premiers d'un entier naturel. Lorsque la locution « crible de corps de nombres » est utilisée sans la mention spécial ou général, elle se réfère au GNFS, le crible général de corps de nombres. Le crible spécial de corps de nombres est efficace pour les entiers de la forme re ± s, où r et s sont petits. Il est donc particulièrement recommandé pour factoriser les nombres de Fermat et les nombres de Mersenne. On conjecture que sa complexité est (en notation de Landau) : Le SNFS a beaucoup été utilisé par le NFSNet et d'autres pour factoriser les nombres du projet Cunningham. (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Special number field sieve » (voir la liste des auteurs). * Portail de l'informatique théorique * Arithmétique et théorie des nombres (fr) In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it. The special number field sieve is efficient for integers of the form re ± s, where r and s are small (for instance Mersenne numbers). Heuristically, its complexity for factoring an integer is of the form: in O and L-notations. The SNFS has been used extensively by NFSNet (a volunteer distributed computing effort), NFS@Home and others to factorise numbers of the Cunningham project; for some time the records for integer factorization have been numbers factored by SNFS. (en) 특수 수체 체(Special Number Field Sieve, SNFS)는 특수한 꼴의 자연수를 매우 빠르게 소인수분해할 수 있는 알고리즘이다. 이 알고리즘은 re ± s 꼴의 수를 빠르게 소인수분해할 수 있으며, 보통 지수가 작은 메르센 수를 소인수분해할 때 많이 쓰이는 알고리즘이다. 또한 수체 체는 특수 수체 체의 변형된 방법으로, 모든 자연수 n을 빠르게 소인수분해할 수 있는 알고리즘이지만 특수 수체 체보다는 느리다. 이 알고리즘의 실행 시간은 이며, 보통 r과 s가 작은 수일 때 잘 작동한다. (ko) Специальный метод решета числового поля (англ. special number field sieve, SNFS) является методом факторизации целых чисел особого вида. Из него был получен общий метод решета числового поля, являющийся наиболее эффективным алогритмом факторизации больших целых чисел . Метод эффективен для целых чисел вида re ± s, где r N s Z, r и s невелики(например Числа Мерсенна). Эвристическая оценка сложности факторизации числа n выражается формулой: С помощью SNFS было разложено на множители число Ферма , содержащее 155 десятичных цифр. (ru) |
| dbo:wikiPageExternalLink | http://modular.fas.harvard.edu/129-05/final_papers/Steve_Byrnes.pdf http://www.std.org/~msm/common/f9paper.ps http://escatter11.fullerton.edu/nfs/ |
| dbo:wikiPageID | 589132 (xsd:integer) |
| dbo:wikiPageLength | 9560 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1113307427 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algebraic_number_field dbr:Algorithmic_efficiency dbc:Integer_factorization_algorithms dbr:Integer_factorization dbr:Integer_factorization_records dbr:Elliptic_curve_method dbr:L-notation dbr:Mathematics dbr:General_number_field_sieve dbr:Greatest_common_divisor dbr:Modular_arithmetic dbr:Linear_algebra dbr:Sieve_of_Eratosthenes dbr:Computational_complexity_theory dbr:Distributed_computing dbr:Cunningham_project dbr:Irreducible_polynomial dbr:Fibonacci_number dbr:Number_theory dbr:Unique_factorization_domain dbr:Ring_(mathematics) dbr:Big_O_notation dbr:Heuristic dbr:Integer dbr:Mersenne_number dbr:Rational_sieve dbr:Root_of_a_function dbr:Smooth_number dbr:Lucas_number dbr:Ring_homomorphism dbr:Relatively_prime |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Reflist dbt:Tmath 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 |
| rdfs:comment | 특수 수체 체(Special Number Field Sieve, SNFS)는 특수한 꼴의 자연수를 매우 빠르게 소인수분해할 수 있는 알고리즘이다. 이 알고리즘은 re ± s 꼴의 수를 빠르게 소인수분해할 수 있으며, 보통 지수가 작은 메르센 수를 소인수분해할 때 많이 쓰이는 알고리즘이다. 또한 수체 체는 특수 수체 체의 변형된 방법으로, 모든 자연수 n을 빠르게 소인수분해할 수 있는 알고리즘이지만 특수 수체 체보다는 느리다. 이 알고리즘의 실행 시간은 이며, 보통 r과 s가 작은 수일 때 잘 작동한다. (ko) Специальный метод решета числового поля (англ. special number field sieve, SNFS) является методом факторизации целых чисел особого вида. Из него был получен общий метод решета числового поля, являющийся наиболее эффективным алогритмом факторизации больших целых чисел . Метод эффективен для целых чисел вида re ± s, где r N s Z, r и s невелики(например Числа Мерсенна). Эвристическая оценка сложности факторизации числа n выражается формулой: С помощью SNFS было разложено на множители число Ферма , содержащее 155 десятичных цифр. (ru) La criba especial del cuerpo de números (en inglés special number field sieve, SNFS) es un algoritmo especializado de factorización de números enteros. La criba (general) del cuerpo de números (GNFS) es una versión generalizada de este algoritmo que trata con números de todo tipo. Su tiempo de ejecución y complejidad en notación de Landau parece ser: (es) In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it. The special number field sieve is efficient for integers of the form re ± s, where r and s are small (for instance Mersenne numbers). Heuristically, its complexity for factoring an integer is of the form: in O and L-notations. (en) Le crible spécial de corps de nombres (SNFS) est un algorithme spécialisé de factorisation en nombres premiers d'un entier naturel. Lorsque la locution « crible de corps de nombres » est utilisée sans la mention spécial ou général, elle se réfère au GNFS, le crible général de corps de nombres. Le crible spécial de corps de nombres est efficace pour les entiers de la forme re ± s, où r et s sont petits. Il est donc particulièrement recommandé pour factoriser les nombres de Fermat et les nombres de Mersenne. On conjecture que sa complexité est (en notation de Landau) : (fr) |
| rdfs:label | Criba especial del cuerpo de números (es) Algorithme de factorisation par crible sur les corps de nombres spécialisé (fr) 특수 수체 체 (ko) Special number field sieve (en) Специальный метод решета числового поля (ru) |
| owl:sameAs | freebase:Special number field sieve yago-res:Special number field sieve wikidata:Special number field sieve dbpedia-es:Special number field sieve dbpedia-fi:Special number field sieve dbpedia-fr:Special number field sieve dbpedia-ko:Special number field sieve dbpedia-ru:Special number field sieve https://global.dbpedia.org/id/4qRFM |
| prov:wasDerivedFrom | wikipedia-en:Special_number_field_sieve?oldid=1113307427&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Special_number_field_sieve |
| is dbo:wikiPageRedirects of | dbr:SNFS |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:SNFS dbr:Integer_factorization dbr:Integer_factorization_records dbr:List_of_number_theory_topics dbr:Timeline_of_algorithms dbr:General_number_field_sieve dbr:Key_size dbr:Fibonacci_number dbr:John_Pollard_(mathematician) dbr:Prime_number dbr:Mersenne_prime dbr:Reciprocal_polynomial |
| is foaf:primaryTopic of | wikipedia-en:Special_number_field_sieve |