Shanks's square forms factorization (original) (raw)
Метод квадратичных форм Шенкса — метод факторизации целых чисел, основанный на применении квадратичных форм, разработанный Даниелем Шенксом в 1975 году, как развитие метода факторизации Ферма. Для 32-разрядных компьютеров алгоритмы, основанные на данном методе, являются безусловными лидерами среди алгоритмов факторизации для чисел от до и, вероятно, таковыми останутся. Данный алгоритм может разделить практически любое составное 18-значное число менее чем за миллисекунду.Алгоритм является чрезвычайно простым, красивым и эффективным. Кроме того, методы, базирующиеся на данном алгоритме, используются как вспомогательные при разложении делителей больших чисел типа чисел Ферма.
| Property | Value |
|---|---|
| dbo:abstract | La factorización de formas cuadradas de Shanks es un método para factorizar enteros inventado por Daniel Shanks como una mejora del método de factorización de Fermat. El éxito del método depende de encontrar números enteros e tales que , donde es el entero a ser factorizado. Una mejora (indicada por ) es buscar enteros e tales que . Encontrando un par adecuado no se garantiza una factorización de , pero esto implica que es un factor de , y hay una buena posibilidad de que los divisores primos de estén distribuidos entre esos dos factores, así que el cálculo del máximo común divisor de y dará un factor no trivial de . Un algoritmo práctico para encontrar pares que satisfagan fue desarrollado por Shanks, que lo llamó Factorización de formas cuadradas (en inglés Square Forms Factorization o SQUFOF). El algoritmo puede ser expresado en términos de fracciones continuas, o en términos de formas cuadráticas. A pesar de que ahora existen métodos de factorización más eficientes disponibles, SQUFOF tiene la ventaja de que es lo suficientemente pequeño para ser implementado en una calculadora programable. (es) Shanks's square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method. The success of Fermat's method depends on finding integers and such that , where is the integer to be factored. An improvement (noticed by Kraitchik) is to look for integers and such that . Finding a suitable pair does not guarantee a factorization of , but it implies that is a factor of , and there is a good chance that the prime divisors of are distributed between these two factors, so that calculation of the greatest common divisor of and will give a non-trivial factor of . A practical algorithm for finding pairs which satisfy was developed by Shanks, who named it Square Forms Factorization or SQUFOF. The algorithm can be expressed in terms of continued fractions or in terms of quadratic forms. Although there are now much more efficient factorization methods available, SQUFOF has the advantage that it is small enough to be implemented on a programmable calculator. In 1858, the Czech mathematician Václav Šimerka used a method similar to SQUFOF to factor . (en) Метод квадратичных форм Шенкса — метод факторизации целых чисел, основанный на применении квадратичных форм, разработанный Даниелем Шенксом в 1975 году, как развитие метода факторизации Ферма. Для 32-разрядных компьютеров алгоритмы, основанные на данном методе, являются безусловными лидерами среди алгоритмов факторизации для чисел от до и, вероятно, таковыми останутся. Данный алгоритм может разделить практически любое составное 18-значное число менее чем за миллисекунду.Алгоритм является чрезвычайно простым, красивым и эффективным. Кроме того, методы, базирующиеся на данном алгоритме, используются как вспомогательные при разложении делителей больших чисел типа чисел Ферма. (ru) Метод квадратичних форм Шенкса — метод , оснований на застосуванні квадратичних форм, розроблений Даніелем Шенксом (англ. Daniel Shanks) в , як розвиток метода факторизації Ферма. Для 32-різноманітних комп'ютерів, алгоритми яких основані на даному методі, є безумовними лідерами серед алгоритмів факторизації для чисел від до і, ймовірно, такими і залишаться. Даний алгоритм може розділити практично будь-яке складене 18-значне число менше ніж за мілісекунду.Алгоритм є надзвичайно простим, красивим і ефективним. Крім того, методи, що базуються на даному алгоритмі, використовуються при розкладанні дільників великих чисел, типу чисел Ферма. (uk) |
| dbo:wikiPageExternalLink | https://github.com/TilmanNeumann/java-math-library https://archive.org/details/factorizationpri0000bres https://archive.org/details/binaryquadraticf0000buel http://colin.barker.pagesperso-orange.fr/lpa/big_squf.htm https://web.archive.org/web/20181130202028/https:/www.usna.edu/Users/math/wdj/_files/documents/mcmath/TridentFinal.pdf https://web.archive.org/web/20181130202030/https:/www.usna.edu/Users/math/wdj/_files/documents/mcmath/shanks_squfof.pdf https://web.archive.org/web/20181201005104/https:/www.usna.edu/Users/math/wdj/_files/documents/mcmath/shanks_analysis.pdf https://web.archive.org/web/20200930034823/https:/www.usna.edu/Users/cs/crabbe/papers/mcmath-IJPAM.pdf http://www.ams.org/bookpages/stml-68 http://www.ams.org/journals/mcom/2008-77-261/S0025-5718-07-02010-8/S0025-5718-07-02010-8.pdf http://homes.cerias.purdue.edu/~ssw/squfof.pdf |
| dbo:wikiPageID | 3387328 (xsd:integer) |
| dbo:wikiPageLength | 8748 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094553504 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Integer_factorization_algorithms dbr:Integer_factorization dbr:Greatest_common_divisor dbr:Maurice_Kraitchik dbr:Václav_Šimerka dbr:Daniel_Shanks dbr:Prime_number dbr:Square_number dbr:Fermat's_factorization_method dbr:Prime_divisor |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_book dbt:More_footnotes dbt:Reflist dbt:Number_theoretic_algorithms |
| dct:subject | dbc:Integer_factorization_algorithms |
| rdfs:comment | Метод квадратичных форм Шенкса — метод факторизации целых чисел, основанный на применении квадратичных форм, разработанный Даниелем Шенксом в 1975 году, как развитие метода факторизации Ферма. Для 32-разрядных компьютеров алгоритмы, основанные на данном методе, являются безусловными лидерами среди алгоритмов факторизации для чисел от до и, вероятно, таковыми останутся. Данный алгоритм может разделить практически любое составное 18-значное число менее чем за миллисекунду.Алгоритм является чрезвычайно простым, красивым и эффективным. Кроме того, методы, базирующиеся на данном алгоритме, используются как вспомогательные при разложении делителей больших чисел типа чисел Ферма. (ru) Метод квадратичних форм Шенкса — метод , оснований на застосуванні квадратичних форм, розроблений Даніелем Шенксом (англ. Daniel Shanks) в , як розвиток метода факторизації Ферма. Для 32-різноманітних комп'ютерів, алгоритми яких основані на даному методі, є безумовними лідерами серед алгоритмів факторизації для чисел від до і, ймовірно, такими і залишаться. Даний алгоритм може розділити практично будь-яке складене 18-значне число менше ніж за мілісекунду.Алгоритм є надзвичайно простим, красивим і ефективним. Крім того, методи, що базуються на даному алгоритмі, використовуються при розкладанні дільників великих чисел, типу чисел Ферма. (uk) La factorización de formas cuadradas de Shanks es un método para factorizar enteros inventado por Daniel Shanks como una mejora del método de factorización de Fermat. El éxito del método depende de encontrar números enteros e tales que , donde es el entero a ser factorizado. Una mejora (indicada por ) es buscar enteros e tales que . Encontrando un par adecuado no se garantiza una factorización de , pero esto implica que es un factor de , y hay una buena posibilidad de que los divisores primos de estén distribuidos entre esos dos factores, así que el cálculo del máximo común divisor de y dará un factor no trivial de . (es) Shanks's square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method. The success of Fermat's method depends on finding integers and such that , where is the integer to be factored. An improvement (noticed by Kraitchik) is to look for integers and such that . Finding a suitable pair does not guarantee a factorization of , but it implies that is a factor of , and there is a good chance that the prime divisors of are distributed between these two factors, so that calculation of the greatest common divisor of and will give a non-trivial factor of . (en) |
| rdfs:label | Factorización de formas cuadradas de Shanks (es) Shanks's square forms factorization (en) Метод квадратичных форм Шенкса (ru) Метод квадратичних форм Шенкса (uk) |
| owl:sameAs | wikidata:Shanks's square forms factorization dbpedia-es:Shanks's square forms factorization dbpedia-ru:Shanks's square forms factorization dbpedia-uk:Shanks's square forms factorization https://global.dbpedia.org/id/3yRi3 |
| prov:wasDerivedFrom | wikipedia-en:Shanks's_square_forms_factorization?oldid=1094553504&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Shanks's_square_forms_factorization |
| is dbo:wikiPageRedirects of | dbr:SQUFOF dbr:Shanks'_square_forms_factorization dbr:Shanks'_SQUFOF dbr:Shanks'_square_forms_factorisation dbr:Shanks_SQUFOF dbr:Shank’s_Algorithm |
| is dbo:wikiPageWikiLink of | dbr:SQUFOF dbr:Integer_factorization dbr:Daniel_Shanks dbr:Shanks'_square_forms_factorization dbr:Shanks'_SQUFOF dbr:Shanks'_square_forms_factorisation dbr:Shanks_SQUFOF dbr:Shank’s_Algorithm |
| is foaf:primaryTopic of | wikipedia-en:Shanks's_square_forms_factorization |