Polynomial Greatest Common Divisor as a Solution of System of Linear Equations
- Authors: Dolgov D.A.1
-
Affiliations:
- Department of System Analysis and Information Technologies, Institute of Computational Mathematics and Information Technologies
- Issue: Vol 39, No 7 (2018)
- Pages: 985-991
- Section: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/202769
- DOI: https://doi.org/10.1134/S1995080218070090
- ID: 202769
Cite item
Abstract
In this article we present a new algebraic approach to the greatest common divisor (GCD) computation of two polynomials based on Bezout’s identity. This approach is based on the solution of system of linear equations. Also we introduce the dmod operation for polynomials. This operation on polynomials f, g is used to reduce the degree of the larger polynomial f in a finite field Fp. This operation saves GCD(f, g). Also we present some ideas how to reduce spurious factors that arise at the procedure.
About the authors
D. A. Dolgov
Department of System Analysis and Information Technologies, Institute of Computational Mathematics and Information Technologies
Author for correspondence.
Email: Dolgov.kfu@gmail.com
Russian Federation, ul. Kremlevskaya 18, Kazan, Tatarstan, 420008