Berlekamp–Zassenhaus algorithm (original) (raw)
In mathematics, in particular in computational algebra, the Berlekamp–Zassenhaus algorithm is an algorithm for factoring polynomials over the integers, named after Elwyn Berlekamp and Hans Zassenhaus. As a consequence of Gauss's lemma, this amounts to solving the problem also over the rationals. The algorithm starts by finding factorizations over suitable finite fields using Hensel's lemma to lift the solution from modulo a prime p to a convenient power of p. After this the right factors are found as a subset of these. The worst case of this algorithm is exponential in the number of factors.
| Property | Value |
|---|---|
| dbo:abstract | In mathematics, in particular in computational algebra, the Berlekamp–Zassenhaus algorithm is an algorithm for factoring polynomials over the integers, named after Elwyn Berlekamp and Hans Zassenhaus. As a consequence of Gauss's lemma, this amounts to solving the problem also over the rationals. The algorithm starts by finding factorizations over suitable finite fields using Hensel's lemma to lift the solution from modulo a prime p to a convenient power of p. After this the right factors are found as a subset of these. The worst case of this algorithm is exponential in the number of factors. improved this algorithm by using the LLL algorithm, substantially reducing the time needed to choose the right subsets of mod p factors. (en) En mathématiques, et plus particulièrement en calcul formel, l'algorithme de Berlekamp-Zassenhaus est un algorithme permettant de factoriser des polynômes à coefficients entiers. Il est nommé d'après Elwyn Berlekamp et Hans Zassenhaus. D'après le lemme de Gauss (pour les polynômes), cela permet également de factoriser les polynômes à coefficients rationnels. L'algorithme commence par trouver une factorisation sur un corps fini adéquat, puis utilise le lemme de Hensel pour obtenir à partir d'une solution modulo (un nombre premier), une solution modulo une certaine puissance de , en utilisant la borne de Landau-Mignotte. Les facteurs dans forment alors un sous-ensemble des facteurs trouvés sur le corps fini. La complexité dans le pire cas est donc exponentielle par rapport au nombre de facteurs. a amélioré l'algorithme en utilisant l'algorithme LLL, ce qui réduit de façon prononcée le temps nécessaire pour trouver les sous-ensembles des facteurs modulo . (fr) |
| dbo:wikiPageExternalLink | https://archive.org/details/algorithmsforcom0000gedd |
| dbo:wikiPageID | 25744542 (xsd:integer) |
| dbo:wikiPageLength | 3263 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1059406170 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bell_System_Technical_Journal dbr:Algorithm dbr:Computer_algebra dbr:Mathematics dbr:Elwyn_Berlekamp dbr:Gauss's_lemma_(number_theory) dbr:Berlekamp's_algorithm dbr:Mathematics_of_Computation dbr:Finite_field dbr:Hans_Zassenhaus dbr:Journal_of_Number_Theory dbc:Computer_algebra dbr:Hensel's_lemma dbr:Polynomial dbr:Integer dbr:LLL_algorithm |
| dbp:author | Domazet, Haris (en) |
| dbp:id | Berlekamp-ZassenhausAlgorithm (en) |
| dbp:title | Berlekamp-Zassenhaus Algorithm (en) |
| dbp:wikiPageUsesTemplate | dbt:Algebra-stub dbt:Algorithm-stub dbt:Citation dbt:Harvtxt dbt:Mathworld |
| dct:subject | dbc:Computer_algebra |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software |
| rdfs:comment | In mathematics, in particular in computational algebra, the Berlekamp–Zassenhaus algorithm is an algorithm for factoring polynomials over the integers, named after Elwyn Berlekamp and Hans Zassenhaus. As a consequence of Gauss's lemma, this amounts to solving the problem also over the rationals. The algorithm starts by finding factorizations over suitable finite fields using Hensel's lemma to lift the solution from modulo a prime p to a convenient power of p. After this the right factors are found as a subset of these. The worst case of this algorithm is exponential in the number of factors. (en) En mathématiques, et plus particulièrement en calcul formel, l'algorithme de Berlekamp-Zassenhaus est un algorithme permettant de factoriser des polynômes à coefficients entiers. Il est nommé d'après Elwyn Berlekamp et Hans Zassenhaus. D'après le lemme de Gauss (pour les polynômes), cela permet également de factoriser les polynômes à coefficients rationnels. a amélioré l'algorithme en utilisant l'algorithme LLL, ce qui réduit de façon prononcée le temps nécessaire pour trouver les sous-ensembles des facteurs modulo . (fr) |
| rdfs:label | Berlekamp–Zassenhaus algorithm (en) Algorithme de Berlekamp-Zassenhaus (fr) |
| owl:sameAs | freebase:Berlekamp–Zassenhaus algorithm wikidata:Berlekamp–Zassenhaus algorithm dbpedia-fr:Berlekamp–Zassenhaus algorithm https://global.dbpedia.org/id/4YDGg |
| prov:wasDerivedFrom | wikipedia-en:Berlekamp–Zassenhaus_algorithm?oldid=1059406170&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Berlekamp–Zassenhaus_algorithm |
| is dbo:wikiPageRedirects of | dbr:Berlekamp-Zassenhaus_algorithm dbr:Berlekamp-Zassenhaus_Algorithm |
| is dbo:wikiPageWikiLink of | dbr:Elwyn_Berlekamp dbr:Berlekamp-Zassenhaus_algorithm dbr:Hans_Zassenhaus dbr:Berlekamp-Zassenhaus_Algorithm |
| is foaf:primaryTopic of | wikipedia-en:Berlekamp–Zassenhaus_algorithm |