Исторические замечания и литература

1. Существует также (представленная ниже) теорема Штикелъбергера, позволяющая нам определить, четное или нечетное число неприводимых сомножителей имеет данный полином в если — нечетное простое число.

Теорема Штикелъбергера. Пусть — нечетное простое число, — нормированный свободный от квадратов что его дискриминант отличен от полином степени в и пусть — число неприводимых сомножителей полинома . Тогда в том и только том случае, когда дискриминант является квадратом в

[Доказательство ее можно найти в (Childs, 1979).]

2. Мак-Элис описывает простой для программирования алгоритм определения множества полиномов которые разделяют сомножители полинома это множество полиномов может быть вычислено без матричной диагонализации, и каждый полином этого множества имеет вид для некоторых значений , так что Недостатокэтого метода состоит в том, что время его работы зависит от степеней сомножителей полинома в то время как алгоритм Берлекэмпа зависит от и числа сомножителей.

3. Следует заметить, что теорема 6.3.2 соответствует теореме 1 в статье Миньотта 1974 г. В действительности эта теорема впервые упоминалась Ландау в 1905 г., а затем Шпехтом в 1949 г. В

сочетании с хорошо известной теоремой 6.3.1 получается граница для коэффициентов сомножителей полинома.

Панкратьев Е.В. Компьютерная алгебра. Факторизация многочленов. — М.: Изд-во МГУ, 1988.

Bender Е.А., Goldman J.R. On the application of Moebius inversion in combinatorial analysis. American Mathematical Monthly 82, 789-802, 1975.

Berlekamp E.R. Factoring polynomials over finite fields. The Bell System Technical Journal 46, 1853-1859, 1967.

Berlekamp E.R. Algebraic coding theory. McGraw-Hill, New York, 1968. [Имеется перевод: Верлекэмп Э. Алгебраическая теория кодирования. — М.: Мир, 1974.]

Berlekamp E.R. Factoring polynomials over large finite fields. Mathematics of Computation 24, 713-735, 1970.

Butler M.C.R. On the reducibility of polynomials over a finite field. The Quarterly Journal of Mathematics Oxford Second Series 5, 102-107, 1954.

Calmet J., Loos R. An improvement of Rabin’s probabilistic algorithm for generating irreducible polynomials over GF(p). Information Processing Letters 11, 94-95, 1980.

Calmet J., Loos R. Deterministic versus probabilistic factorization of integral polynomials. In Computer Algebra, EUROCAM 1982 Lecture Notes in Computer Science, Springer-Verlag, New York, 1982, pp. 117-125.

Camion P. Un algorithm de construction des idempotents primitifs d’ideaux d’algebressur Fq. Comptes Rendus des Seances de VAcademie des Sciences 291, 479-482, 1980.

Cantor D.G., Zassenhaus H. A new algorithm for factoring polynomials over finite fields. Mathematics of Computation 36, 587-592, 1981.

Cantor M. Geschichte der Mathematik, Vol. 4. Teubner Verlag, Leipzig, 1908.

Childs L. A concrete introduction to higher algebra. Springer Verlag, New York, 1979.

Gunji H., Arnon D. On polynomial factorization over finite fields. Mathematics of Computation 36, 281-287, 1981.

Hensel K. Theorie der algebraischen Zahlen. Teubner Verlag, Leipzig, 1908.

Kaltofen E. Factorization of polynomials. Computing (Suppi. 4) 95-113, 1982.

Knuth D.E. The art of computer programming, Vol. 2, 2nd ed. Seminu-merical Algorithms. Addison-Wesley, Reading, MA 1981. [Имеется перевод первого издания: Кнут Д. Искусство программирования для ЭВМ. Т. 2. — М.: Мир, 1977.]

Landau Е. Sui quelques theoremes de M. Petiovitch ielatifs aux zeros des fonctions analytiques. Bulletin de la Societe Maihematique de France 33, 251-261, 1905.

Lauer M. Computing by homomorphic images. Computing (Suppl. 4), 139-168, 1982.

Lazard D. On polynomial factorization. In Computer Algebra, EURO-CAM 1982 Lecture Notes in Computer Science, Springer-Verlag, New York, 1982, pp. 126-134.

Lenstra A. K. Lattices and factorization of polynomials. Technical Report 190/81, Department of Computer Science, Mathematisch Centrum, Amsterdam 1981.

Lenstra A.K. Factoring polynomials over algebraic number fields. Technical Report 213/82, Department of Computer Science, Mathematisch Centrum, Amsterdam, 1982a.

Lenstra A.K. Factorization of polynomials. In Computational methods in number theory. H.W. Lenstra, Jr and R. Tydeman, eds. Mathematical Centre Tracts, Vol. 154, Amsterdam, 1982b, j>p, 169-198.

Lenstra A.K., Lenstra H.W. Jr., Lovasz L. Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515-534, 1982.

Lidl R., Pilz G. Applied abstract algebra. Springer-Verlag, New York, 1984.

McEliece R.J. Factorization of polynomials over finite fields. Mathematics of Computation 23 861-867, 1969.

Mignotte M. An inequality about factors of polynomials. Mathematics of Computation 28, 1153-1157, 1974.

Miola A., Yun D.Y.Y. Computational aspects of Hensel-type univariate polynomial greatest common divisor algorithms. Proceedings of EUROSAM ’74, 46-54, 1974.

Moenck R.T. On the efficiency of algorithms for polynomial factoring. Mathematics of Computation 31, 235-250, 1977.

Musser D.R. Algorithms for polynomial factorization. Ph.D. Thesis, University of Wisconsin-Madison, Department of Computer Science, 1971.

Musser D.R. Multivariate polynomial factorization. Journal of the Association for Computing Machinery 22, 291-308, 1975.

Musser D.R. On the efficiency of a polynomial irreducibility test. Journal of the Association for Computing Machinery 25, 271-282, 1978.

Petr K. Ueber die Reduzibilitaet eines Polynoms mit ganzzahligen Koef-fmenten nach einem Primzahlmodul. Casopis pro Pestovani Matem-atiky a Fysiky 66, 85-94, 1936.

Rabin M.O. Probabilistic algorithms in finite fields. SIAM Journal of Computing 9, 273-280, 1980.

Schwarz S. Sur le nombre des racines et des facteurs irreductibles d’une congruence donne. Casopis pro Pestovani Matematiky a Fysiky 69, 128-145, 1939.

Schwarz S. On the reducibility of polynomials over a finite field. The Quarterly Journal of Mathematics Oxford, Second Series 7, 110-124, 1956.

Sims C.C. Algebra, a computational approach. Wiley, New York, 1984.

Simmons G. On the number of irreducible polynomials of degree d over GF(p). American Mathematical Monthly 77, 743-745, 1970.

Smith S. On the value of a certain arithmetical determinant. Proceedings of the London Mathematical Society 7, 208-212, 1876.

Specht W. Abschaetzungen der Wurzeln algebraischer Gleichungen. Mathematische Zeitschrift 52, 310-321, 1949.

Swinnerton-Dyer H.P.F. Cited in Berlekamp’s article «Factoring polynomials over large finite fields». Mathematics of Computation 24, 733-734, 1970.

Wang P.S. An improved multivariate polynomial factoring algorithm. Mathematics of Computation 32, 1215-1231, 1978.

Yun D.Y.Y. The Hensel lemma in algebraic manipulation. Ph.D. Thesis, Department of Mathematics, M.I.T., 1973.

Zassenhaus H. On Hensel factorization. Journal of Number Theory 1, 291-311, 1969.

Zassenhaus H. A remark on the Hensel factorization method. Mathematics of Computation 32, 287-292, 1978.