Электронная библиотека Попечительского советамеханико-математического факультета Московского государственного университета
 Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум
 Авторизация Поиск по указателям
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. Язык: Рубрика: Математика/ Статус предметного указателя: Неизвестно ed2k: ed2k stats Год издания: 1982 Количество страниц: 101 Добавлена в каталог: 13.10.2012 Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
Предметный указатель
Реклама
 © Электронная библиотека попечительского совета мехмата МГУ, 2004-2020 | | О проекте