{'fraction_non_alphanumeric': 0.028179190751445087, 'fraction_numerical': 0.004335260115606936, 'mean_word_length': 5.048034934497816, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A parallel algorithm to compute the greatest common divisor of sparse multivariate polynomials

Efficient algorithms for computing greatest common divisors (GCD) of multivariate polynomials have been developed over the last 40 years. Many of the general purpose computer algebra systems are using either Zippel’s GCD Algorithm [5] or the EEZ-GCD [4] Algorithm or both. Both algorithms sequentially interpolate variables one at a time which limits parallel speedup. Since multi-core processors are now widely available, parallel algorithms are desirable. In this poster, we present a first multivariate GCD computation algorithm over Z which is based on the Ben-Or/Tiwari interpolation [1]. By using BenOr/Tiwari interpolation, we reduce the number of points needed to interpolate the GCD and improve parallelism. Our algorithm considers multivariate GCD problems with at least three variables. The structure of the algorithm is similar to Zippel’s GCD Algorithm except the way we determine the first modular image which determines all the monomials. Once this correct form is obtained with those monomials, we use Zippel’s sparse interpolation with this form to compute more modular images and apply Chinese remaindering to reconstruct the true GCD over Z. Our algorithm determines the first modular image as follows: Suppose a, b ∈ Z[x1, . . . , xn] are the input polynomials and let