Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   

Поиск по указателям

Kaltofen E. — On the complexity of factoring polynomials with integer coefficients
Kaltofen E. — On the complexity of factoring polynomials with integer coefficients

Читать книгу

Скачать книгу с нашего сайта нельзя

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: On the complexity of factoring polynomials with integer coefficients

Автор: Kaltofen E.


The complexity of the Berlekamp-Hensel algorithm for factoring polynomials in one or more variables with integer coefficients can become exponential in the individual variable degrees of the input polynomial due 10 the fact that, after factoring the projected polynomial and lifting its factors to sufficiently large coefficients, one may need 10 combine exponentially many lifted factors to obtain the true integer factors. In the univariate case, where the projection is taking the coefficients modulo a prime number, we can find worst case polynomials by prescribing that their Galois groups consist only of permutations with short cycles. Using the Chebotarev density theorem we then are able 10 construct succinct certificates for our hard-to-factor polynomials. In the multivariate case the projection is evaluation of selected variables at integral points. By computing the minimal polynomial of the approximation for a root we are able 10 replace the factor combination process by solving a system of linear equations. The growth analysis for the size of the rational numbers involved shows that, provided the number of variables is fixed, our algorithm reduces the problem in polynomial time in the total degree and coefficient length to the problem of factoring univariate polynomials, which has recently been solved in polynomial lime as well. Therefore our algorithm can factor multivariate polynomials with a fixed number of variables in polynomial time in the total degrees and coefficient lengths, except for splitting a possible constant factor into its prime divisors. The evaluation process also leads us to the study of the Hilbert irreducibilily theorem, an effective version of which provides us with an alternate polynomial time reduction from multivariate to bivariate polynomial factorization and irreducibilily testing.

Язык: en

Рубрика: Математика/

Статус предметного указателя: Неизвестно

ed2k: ed2k stats

Год издания: 1982

Количество страниц: 101

Добавлена в каталог: 13.10.2012

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
Предметный указатель
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2019
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте