NDLI: Yet another practical implementation of polynomial factorization over finite fields

Please wait, while we are loading the content...

Applicability of Zeilberger's algorithm to hypergeometric terms

Fraction-free row reduction of matrices of skew polynomials

Towards better simplification of elementary functions

Solutions of linear ordinary differential equations in terms of special functions

On the efficiency and optimality of Dixon-based resultant methods

A geometric-numeric algorithm for absolute factorization of multivariate polynomials

Multihomogeneous resultant matrices

Editing mathematical content and presentation markup in interactive mathematical documents

Finite field linear algebra subroutines

A new efficient algorithm for computing Gröbner bases without reduction to zero $(F_{5})$

Partial solvability by radicals

Computing the topology of real algebraic surfaces

Algorithms for computing the sparsest shifts of polynomials via the Berlekamp/Massey algorithm

A modular GCD algorithm over number fields presented with multiple extensions

A new zero-test for formal power series

Sparsity issues in the computation of Jacobian matrices

A reduced form for perturbed matrix polynomials

An output-sensitive variant of the baby steps/giant steps determinant algorithm

Determinantal formula for the chow form of a toric surface

Computation of canonical forms for ternary cubics

Simplification of definite sums of rational functions by creative symmetrizing method

Factoring zero-dimensional ideals of linear partial differential operators

Polynomial-time normalizers for permutation groups with restricted composition factors

The differential Hilbert function of a differential rational mapping can be computed in polynomial time

Towards certified irreducibility testing of bivariate approximate polynomials

Yet another practical implementation of polynomial factorization over finite fields

Acceleration of Euclidean algorithm and extensions

Some observations on familiar numbers

Towards faster real algebraic numbers

Simplification of surface parametrizations

Degree bounds and lifting techniques for triangular sets

High-order lifting

An alternative approach to comprehensive Gröbner bases

Numerical stability and stabilization of Groebner basis computation

Canonical comprehensive Gröbner bases

Yet another practical implementation of polynomial factorization over finite fields

Content Provider	ACM Digital Library
Author	Yokoyama, Kazuhiro Noro, Masayuki
Abstract	Polynomial factorization plays a significant role in computational mathematics and its application to engineering, since it forms a fundamental part of algorithms for higher algebraic computations. Multivariate polynomial factorization over finite fields is very important for computations of mathematical object over positive characteristic fields, which will help mathematical studies in various area. For example, primary ideal decomposition over finite fields is very useful for study of pure mathematics (algebraic geometry over positive characteristic fields) and also for study of coding theory (design of algebraic geometric codes). To make primary decomposition efficient, practical method of multivariate polynomial factorization and its implementation are essential. (This is the authors' motivation for this study. )Since, multivariate factorization over finite fields can be reduced efficiently to bivariate factorization, we focus on bivariate factorization over small finite fields here, and we propose a practically efficient combination of two methods: one is the well-known method by trial division and the other is a new polynomial-time method.As to polynomial factorization, many of computer algebra systems employ trial-division type algorithms which are non polynomial-time but efficient in many cases. However, as polynomial-time algorithms work well in the worst cases, good combination with practical algorithms should be very useful to improve the performance of the computer algebra system, provided that we have their practical implementation and we know their good usages. Moreover, if we can incorporate those with certain knowledge on the input, (we may call these heuristics), their practicality shall be much improved. In this paper we propose a polynomial-time algorithm for bivariate factorization over finite fields, which can be implemented efficiently and in which some heuristics can be incorporated. The new algorithm is obtained by reviewing existing algorithms from the ideal theoretical point of view, and based on the change of ordering algorithm of zero-dimensional Gröbner basis [6, 17].As to practical implementation of bivariate factorization, finding evaluation points and Hensel lifting are very important. When we factorize a polynomial over a small finite field, we often have to extend the ground field because of shortage of evaluation points. However, if the extension field is small enough, a primitive root representation of the field can reduce the cost of field operations over the extension field. Under this situation we implement Hensel lifting and trial division, and we examine its performance by various benchmark problems. We also implement the new polynomial-time algorithm and we show its advantage for hard-to-factor polynomials.
Starting Page	200
Ending Page	206
Page Count	7
File Format	PDF
ISBN	1581134843
DOI	10.1145/780506.780532
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-07-10
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Practical factorization of univariate polynomials over finite fields

Fast polynomial factorization over high algebraic extensions of finite fields

Efficient multivariate factorization over finite fields (1997).

Efficient multivariate factorization over finite fields (1997)

On polynomial factorization over finite fields

Factoring Polynomials over Finite Fields using Balance Test

On Polynomial Factorization Over Finite Fields

A New Algorithm for Factoring Polynomials Over Finite Fields *

Factorization Statistics of Restricted Polynomial Specializations over Large Finite Fields

Yet another practical implementation of polynomial factorization over finite fields

Similar Documents

Practical factorization of univariate polynomials over finite fields

Fast polynomial factorization over high algebraic extensions of finite fields

Efficient multivariate factorization over finite fields (1997).

Efficient multivariate factorization over finite fields (1997)

On polynomial factorization over finite fields

Factoring Polynomials over Finite Fields using Balance Test

On Polynomial Factorization Over Finite Fields

A New Algorithm for Factoring Polynomials Over Finite Fields *

Factorization Statistics of Restricted Polynomial Specializations over Large Finite Fields

Yet another practical implementation of polynomial factorization over finite fields