On degrees of modular common divisors and the Big prime gcd algorithm

2014/07/22 by Vahagn H. Mikaelian, Mikaelian, Vahagn H.
Computer Science · Mathematics · #Analytic Number Theory Research #Coding theory and cryptography #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #Rings and Algebras (math.RA) #math.NT #math.RA

paper · pdf · doi:10.48550/arxiv.1407.5898

arxiv created 2014/07/22 · openalex publication_date 2014/07/22 · arxiv updated 2014/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a few modifications of the Big prime modular gcd algorithm for polynomials in \Z[x]. Our modifications are based on bounds of degrees of modular common divisors of polynomials, on estimates of the number of prime divisors of a resultant and on finding preliminary bounds on degrees of common divisors using auxiliary primes. These modifications are used to suggest improved algorithms for gcd calculation and for coprime polynomials detection. To illustrate the ideas we apply the constructed algorithms on certain polynomials, in particular, on polynomials from Knuth's example of intermediate expression swell.

Related

• A Modular Algorithm for Computing Polynomial GCDs over Number Fields presented with Multiple Extensions
• Computing Modular Polynomials
• Computing Congruences of Modular Forms and Galois Representations Modulo Prime Powers
• Prime and coprime values of polynomials
• On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors