| dbo:abstract
|
- Quadratisches Sieb ist ein Begriff aus dem Bereich Zahlentheorie der Mathematik und bezeichnet einen der schnellsten bekannten Algorithmen zur Faktorisierung großer natürlicher Zahlen. Es ist ein allgemeines Faktorisierungsverfahren, d. h. die Laufzeit hängt nur von der Größe der zu faktorisierenden Zahl ab und nicht von speziellen Eigenschaften der Zahl (bzw. ihrer Teiler). Für Zahlen mit bis ca. 100 Dezimalstellen ist es das schnellste (allgemeine) Faktorisierungsverfahren. Für größere Zahlen ist das Zahlkörpersieb schneller. Die Laufzeit zum Faktorisieren einer Zahl n mit dem quadratischen Sieb ist (unter einigen als wahrscheinlich geltenden Annahmen) in der Größenordnung von (de)
- El algoritmo de criba cuadrática (QS del inglés quadratic sieve), es un algoritmo de factorización de enteros y, en la práctica, el segundo método más rápido conocido (después de la criba general del cuerpo de números). Es todavía el más rápido para enteros que tienen 100 o menos dígitos decimales, y es considerado mucho más sencillo que la criba de cuerpos numéricos. Es un algoritmo de factorización de propósito general, lo que significa que su tiempo de ejecución únicamente depende el tamaño del entero a ser factorizado, y no sobre una estructura especial o propiedades. Fue inventado por Carl Pomerance en 1981 como una mejora a la criba lineal de Schroeppel. (es)
- The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve. (en)
- L'algorithme du crible quadratique est un algorithme de factorisation fondé sur l'arithmétique modulaire. C'est en pratique le plus rapide après le crible général des corps de nombres, lequel est cependant bien plus compliqué, et n'est plus performant que pour factoriser un nombre entier d'au moins cent chiffres. Le crible quadratique est un algorithme de factorisation non spécialisé, c'est-à-dire que son temps d'exécution dépend uniquement de la taille de l'entier à factoriser, et non de propriétés particulières de celui-ci. (fr)
- ( 다른 뜻에 대해서는 이차 수체 문서를 참고하십시오.) 이차 체(Quadratic sieve, QS)는 어떤 큰 자연수 N을 소인수분해하기 위해 사용되는 소인수 분해 알고리즘으로, 양자컴퓨터가 상용화되었을 때 기준으로는 현재까지 발견된 알고리즘 중에서 3번째(쇼어 알고리즘, 수체 체 (General number field sieve))로 빠른 알고리즘이며 (양자컴퓨터를 제외하면 2번째), 수체 체의 기본이 되어 수체 체보다 더 간단한 알고리즘이다. (ko)
- Il crivello quadratico è un algoritmo di fattorizzazione creato da Carl Pomerance.Questo algoritmo è particolarmente famoso perché nel 1994 ha fattorizzato il numero RSA-129, composto da 129 cifre in base dieci. (it)
- De kwadratische zeef is een algoritme om samengestelde getallen te ontbinden in priemfactoren. Deze methode is gebaseerd op Dixons factorisatiemethode en is in 1984 ontwikkeld door de Amerikaanse wiskundige Carl Pomerance. De kwadratische zeef is in 1994 gebruikt om te kraken. Momenteel is de kwadratische zeef een van de snelste algoritmen om een getal te factoriseren. De getallenlichamenzeef is een stuk ingewikkelder dan de kwadratische zeef, maar sneller voor getallen groter dan 130 cijfers. De tijd die de kwadratische zeef en de getallenlichamenzeef nodig hebben om getallen tussen de 100 en 130 cijfers te ontbinden, is sterk afhankelijk van de implementatie van het algoritme en de beschikbare opslagruimte. Pomerance schrijft dat de kwadratische zeef sneller is voor getallen tot 100 cijfers. (nl)
- Sito kwadratowe (ang. Quadratic Sieve) – najszybszy znany algorytm do faktoryzacji liczb, które są krótsze niż 150 cyfr dziesiętnych. (pl)
- Квадратичне решето (англ. quadratic sieve, QS) — алгоритм факторизації цілих чисел, на практиці найшвидший для чисел до 10100. Асипмтотично є другим за швидкістю після загального решета цифрового поля, і значно простіший за нього. Це метод факторизації загального призначення, тобто, час його виконання залежить лише від розміру цілого числа на вході, і не залежить від його вигляду (на відміну від ). Метод винайшов математик 1981 року як поліпшення . (uk)
- Метод квадратичного решета (Quadratic sieve algorithm, сокр. QS) — метод факторизации больших чисел, разработанный Померанцем в 1981 году. Долгое время превосходил другие методы факторизации целых чисел общего вида, не имеющих простых делителей, порядок которых значительно меньше (для чисел , имеющих простые делители, много меньшие более быстрым является метод факторизации на эллиптических кривых). Метод квадратичного решета представляет собой разновидность (обобщение метода факторизации Ферма).Этот метод считается вторым по быстроте (после общего метода решета числового поля). И до сих пор является самым быстрым для целых чисел до 100 десятичных цифр и устроен значительно проще чем общий метод решета числового поля. Это универсальный алгоритм факторизации, так как время его выполнения исключительно зависит от размера факторизуемого числа, а не от его особой структуры и свойств. (ru)
- 二次篩選（Quadratic Sieve）演算法是一個整數分解演算法，在實際用途中為已知第二快的方法（目前第一快為普通數域篩選法）。但對於大約 100 位數以內的整數，它仍然是最快的算法，而且比起普通數域篩選法來說簡潔得多。這是一個通用的整數分解演算法，意即其運算時間完全取決於欲分解的整數本身位數的大小，而不是在於特殊結構或特性。 二次篩選法是由在1981年所發明，並作為理查德·施羅佩爾的線性篩法之改良版。 (zh)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 27576 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Quadratisches Sieb ist ein Begriff aus dem Bereich Zahlentheorie der Mathematik und bezeichnet einen der schnellsten bekannten Algorithmen zur Faktorisierung großer natürlicher Zahlen. Es ist ein allgemeines Faktorisierungsverfahren, d. h. die Laufzeit hängt nur von der Größe der zu faktorisierenden Zahl ab und nicht von speziellen Eigenschaften der Zahl (bzw. ihrer Teiler). Für Zahlen mit bis ca. 100 Dezimalstellen ist es das schnellste (allgemeine) Faktorisierungsverfahren. Für größere Zahlen ist das Zahlkörpersieb schneller. Die Laufzeit zum Faktorisieren einer Zahl n mit dem quadratischen Sieb ist (unter einigen als wahrscheinlich geltenden Annahmen) in der Größenordnung von (de)
- El algoritmo de criba cuadrática (QS del inglés quadratic sieve), es un algoritmo de factorización de enteros y, en la práctica, el segundo método más rápido conocido (después de la criba general del cuerpo de números). Es todavía el más rápido para enteros que tienen 100 o menos dígitos decimales, y es considerado mucho más sencillo que la criba de cuerpos numéricos. Es un algoritmo de factorización de propósito general, lo que significa que su tiempo de ejecución únicamente depende el tamaño del entero a ser factorizado, y no sobre una estructura especial o propiedades. Fue inventado por Carl Pomerance en 1981 como una mejora a la criba lineal de Schroeppel. (es)
- The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve. (en)
- L'algorithme du crible quadratique est un algorithme de factorisation fondé sur l'arithmétique modulaire. C'est en pratique le plus rapide après le crible général des corps de nombres, lequel est cependant bien plus compliqué, et n'est plus performant que pour factoriser un nombre entier d'au moins cent chiffres. Le crible quadratique est un algorithme de factorisation non spécialisé, c'est-à-dire que son temps d'exécution dépend uniquement de la taille de l'entier à factoriser, et non de propriétés particulières de celui-ci. (fr)
- ( 다른 뜻에 대해서는 이차 수체 문서를 참고하십시오.) 이차 체(Quadratic sieve, QS)는 어떤 큰 자연수 N을 소인수분해하기 위해 사용되는 소인수 분해 알고리즘으로, 양자컴퓨터가 상용화되었을 때 기준으로는 현재까지 발견된 알고리즘 중에서 3번째(쇼어 알고리즘, 수체 체 (General number field sieve))로 빠른 알고리즘이며 (양자컴퓨터를 제외하면 2번째), 수체 체의 기본이 되어 수체 체보다 더 간단한 알고리즘이다. (ko)
- Il crivello quadratico è un algoritmo di fattorizzazione creato da Carl Pomerance.Questo algoritmo è particolarmente famoso perché nel 1994 ha fattorizzato il numero RSA-129, composto da 129 cifre in base dieci. (it)
- Sito kwadratowe (ang. Quadratic Sieve) – najszybszy znany algorytm do faktoryzacji liczb, które są krótsze niż 150 cyfr dziesiętnych. (pl)
- Квадратичне решето (англ. quadratic sieve, QS) — алгоритм факторизації цілих чисел, на практиці найшвидший для чисел до 10100. Асипмтотично є другим за швидкістю після загального решета цифрового поля, і значно простіший за нього. Це метод факторизації загального призначення, тобто, час його виконання залежить лише від розміру цілого числа на вході, і не залежить від його вигляду (на відміну від ). Метод винайшов математик 1981 року як поліпшення . (uk)
- 二次篩選（Quadratic Sieve）演算法是一個整數分解演算法，在實際用途中為已知第二快的方法（目前第一快為普通數域篩選法）。但對於大約 100 位數以內的整數，它仍然是最快的算法，而且比起普通數域篩選法來說簡潔得多。這是一個通用的整數分解演算法，意即其運算時間完全取決於欲分解的整數本身位數的大小，而不是在於特殊結構或特性。 二次篩選法是由在1981年所發明，並作為理查德·施羅佩爾的線性篩法之改良版。 (zh)
- De kwadratische zeef is een algoritme om samengestelde getallen te ontbinden in priemfactoren. Deze methode is gebaseerd op Dixons factorisatiemethode en is in 1984 ontwikkeld door de Amerikaanse wiskundige Carl Pomerance. De kwadratische zeef is in 1994 gebruikt om te kraken. Momenteel is de kwadratische zeef een van de snelste algoritmen om een getal te factoriseren. De getallenlichamenzeef is een stuk ingewikkelder dan de kwadratische zeef, maar sneller voor getallen groter dan 130 cijfers. De tijd die de kwadratische zeef en de getallenlichamenzeef nodig hebben om getallen tussen de 100 en 130 cijfers te ontbinden, is sterk afhankelijk van de implementatie van het algoritme en de beschikbare opslagruimte. Pomerance schrijft dat de kwadratische zeef sneller is voor getallen tot 100 cij (nl)
- Метод квадратичного решета (Quadratic sieve algorithm, сокр. QS) — метод факторизации больших чисел, разработанный Померанцем в 1981 году. Долгое время превосходил другие методы факторизации целых чисел общего вида, не имеющих простых делителей, порядок которых значительно меньше (для чисел , имеющих простые делители, много меньшие более быстрым является метод факторизации на эллиптических кривых). Метод квадратичного решета представляет собой разновидность (обобщение метода факторизации Ферма).Этот метод считается вторым по быстроте (после общего метода решета числового поля). И до сих пор является самым быстрым для целых чисел до 100 десятичных цифр и устроен значительно проще чем общий метод решета числового поля. Это универсальный алгоритм факторизации, так как время его выполнения (ru)
|
| rdfs:label
|
- Quadratisches Sieb (de)
- Criba cuadrática (es)
- Crible quadratique (fr)
- Crivello quadratico (it)
- 이차 체 (ko)
- Quadratic sieve (en)
- Kwadratische zeef (nl)
- Sito kwadratowe (pl)
- Метод квадратичного решета (ru)
- 二次篩選法 (zh)
- Квадратичне решето (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
