| 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
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3263 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:author
| |
| dbp:id
|
- Berlekamp-ZassenhausAlgorithm (en)
|
| dbp:title
|
- Berlekamp-Zassenhaus Algorithm (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
