An algorithm that can be used to factor a polynomial  over the integers. The algorithm proceeds by first factoring modulo a suitable prime  via Berlekamp's method and then uses Hensel lifting to lift this to a factorization modulo , then , then , ..., up to some bound . This has quadratic convergence. After this procedure, the right subsets of these factors are chosen in order to obtain factors with integer coefficients. The worst-case complexity of this procedure is exponential in the number of factors, since there may be an exponential number of combinations to check. Bad examples are obtained by taking an irreducible polynomial  in  which has many different factors modulo every .

van Hoeij (2002) improved this algorithm by providing a better way of solving the combinatorial problem. His method uses lattice reduction (more specifically, the LLL algorithm), and it substantially reduces the time needed to choose the right subsets of mod  factors.

REFERENCES:

Berlekamp, E. R. "Factoring Polynomials over Finite Fields." Bell System Technical J. 46, 1853-1859, 1967.

Berlekamp, E. R. "Factoring Polynomials over Finite Fields." Math. Comput. 24, 713-735, 1970.

Cantor, D. G. and Zassenhaus, H. "A New Algorithm for Factoring Polynomials over Finite Fields." Math. Comput. 36, 587-592, 1981.

Geddes, K. O.; Czapor, S. R.; and Labahn, G. Algorithms for Computer Algebra. Amsterdam, Netherlands: Kluwer, 1992.

van Hoeij, M. "Factoring Polynomials and the Knapsack Problem." J. Number Th. 95, 167-189, 2002.

Zassenhaus, H. "On Hensel Factorization, I." J. Number Th. 1, 291-311, 1969.

اخر الاخبار

اخبار العتبة العباسية المقدسة

المجمع العلمي للقرآن الكريم يصدر الكتاب الثاني من سلسلة يخشى

قسم الشعائر يكرّم أصحاب المواكب المشاركة في إحياء ذكرى شهادة السيدة الزهراء (عليها السلام)

جامعة العميد تستقبل طلبة المراحل الأولى المقبولين ضمن كلياتها للعام الدراسي الجديد

سماحة السيد الصافي يكرّم طلبة حفظ القرآن الكريم المتفوّقين ويؤكّد دور التدبّر في الهداية والتكامل

المزيد

الآخبار الصحية

طبيب يكشف تأثير برودة الشتاء على النوم

دون أن تعلم.. 10 عادات يومية تسرع شيخوخة جسمك

تقرير: النيكوتين خطر على القلب مهما كانت الطريقة

أيهما أفضل لصحتك.. زبدة الفول السوداني أم النوتيلا؟

المزيد

الآخبار التكنلوجية

السعودية تدشن أكبر نظام لتخزين الكهرباء بالبطاريات في العالم !

بأمر تنفيذي.. ترامب يؤكد هدف عودة الأميركيين إلى القمر في عام 2028

بعيدا عن البشر.. "قتال جوي في الفضاء" بين أميركا والصين

كشف مذهل في قاع "برمودا" !

المزيد