Deterministic distinct-degree factorization of polynomials over finite fields
A deterministic polynomial time algorithm is presented for finding the distinct-degree factorization of multivariate polynomials over finite fields. As a consequence, one can count the number of irreducible factors of polynomials over finite fields in deterministic polynomial time, thus resolving a...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2004
|
| _version_ | 1797058982610731008 |
|---|---|
| author | Gao, S Kaltofen, E Lauder, A |
| author_facet | Gao, S Kaltofen, E Lauder, A |
| author_sort | Gao, S |
| collection | OXFORD |
| description | A deterministic polynomial time algorithm is presented for finding the distinct-degree factorization of multivariate polynomials over finite fields. As a consequence, one can count the number of irreducible factors of polynomials over finite fields in deterministic polynomial time, thus resolving a theoretical open problem of Kaltofen from 1987. © 2004 Elsevier Ltd. All rights reserved. |
| first_indexed | 2024-03-06T19:57:47Z |
| format | Journal article |
| id | oxford-uuid:263c7914-39ed-4a81-bbf9-11e04978b468 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:57:47Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | oxford-uuid:263c7914-39ed-4a81-bbf9-11e04978b4682022-03-26T11:59:46ZDeterministic distinct-degree factorization of polynomials over finite fieldsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:263c7914-39ed-4a81-bbf9-11e04978b468EnglishSymplectic Elements at Oxford2004Gao, SKaltofen, ELauder, AA deterministic polynomial time algorithm is presented for finding the distinct-degree factorization of multivariate polynomials over finite fields. As a consequence, one can count the number of irreducible factors of polynomials over finite fields in deterministic polynomial time, thus resolving a theoretical open problem of Kaltofen from 1987. © 2004 Elsevier Ltd. All rights reserved. |
| spellingShingle | Gao, S Kaltofen, E Lauder, A Deterministic distinct-degree factorization of polynomials over finite fields |
| title | Deterministic distinct-degree factorization of polynomials over finite fields |
| title_full | Deterministic distinct-degree factorization of polynomials over finite fields |
| title_fullStr | Deterministic distinct-degree factorization of polynomials over finite fields |
| title_full_unstemmed | Deterministic distinct-degree factorization of polynomials over finite fields |
| title_short | Deterministic distinct-degree factorization of polynomials over finite fields |
| title_sort | deterministic distinct degree factorization of polynomials over finite fields |
| work_keys_str_mv | AT gaos deterministicdistinctdegreefactorizationofpolynomialsoverfinitefields AT kaltofene deterministicdistinctdegreefactorizationofpolynomialsoverfinitefields AT laudera deterministicdistinctdegreefactorizationofpolynomialsoverfinitefields |