On computation of the greatest common divisor of several polynomials over a finite field. (Q1414018): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: MaRDI profile type (P1460): MaRDI publication profile (Q5976449), #quickstatements; #temporary_batch_1710541407615 |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:20, 16 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On computation of the greatest common divisor of several polynomials over a finite field. |
scientific article |
Statements
On computation of the greatest common divisor of several polynomials over a finite field. (English)
0 references
19 November 2003
0 references
The author proposes a probabilistic algorithm for computing the greatest common divisor (gcd) of several polynomials over a finite field. The method is based on the work of \textit{G. Cooperman} et al. [Lect. Notes Comput. Sci. 1627, 310--317 (1999; Zbl 0977.11055)] on the gcd calculation of many integers. The idea consists in reducing the problem to determine the gcd of a pair of polynomials: Given \(m\) non-zero polynomials \(a_1,\ldots,a_m\in\mathbb{F}_q[X]\), choose \(2m\) random polynomials \(u_1,\dots,u_m\), \(v_1,\dots,v_m\in\mathbb{F}_q[X]\) of same degree and determine \[ D=\gcd\left(\sum_{j=1}^m u_ja_j,\sum_{j=1}^m v_ja_j\right). \] It is proved that with high probability \(D\) is exactly the gcd of \(a_1,\ldots,a_m\). Moreover, a detailed comparision of other reduction approaches is presented.
0 references
polynomials over finite fields
0 references
greatest common divisor
0 references
probabilistic algorithm
0 references