A p-adic division with remainder algorithm
- 1 November 1974
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGSAM Bulletin
- Vol. 8 (4) , 27-32
- https://doi.org/10.1145/1088288.1088293
Abstract
A new algorithm for division with remainder of univariate and multivariate polynomials over the integers is reported. This division algorithm relies on a p-adic construction which is closely related to the Hensel-type constructions used for polynomial factorization and greatest common divisor computations. It furnishes a new and systematic way of looking at the classical problem of division (with or without remainder). Due to the sparseness-preserving property of p-adic constructions, it appears useful as an alternative division algorithm in suitable cases when the polynomials are sparse. Detailed discussion and a more complete computing time analysis will be deferred until a later time as the work progresses further. An hope, in the meantime, is to attract comments and criticism on the algorithm and its significance.Keywords
This publication has 11 references indexed in Scilit:
- Sparse polynomial arithmeticACM SIGSAM Bulletin, 1974
- Computational aspects of Hensel-type univariate polynomial greatest common divisor algorithmsACM SIGSAM Bulletin, 1974
- On the Computation of Powers of Sparse PolynomialsStudies in Applied Mathematics, 1974
- Factoring multivariate polynomials over the integersACM SIGSAM Bulletin, 1973
- The EZ GCD algorithmPublished by Association for Computing Machinery (ACM) ,1973
- On the substitution of polynomial formsPublished by Association for Computing Machinery (ACM) ,1973
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common DivisorsJournal of the ACM, 1971
- Subresultants and Reduced Polynomial Remainder SequencesJournal of the ACM, 1967
- Polynomial Remainder Sequences and DeterminantsThe American Mathematical Monthly, 1966
- ZahlentheoriePublished by Walter de Gruyter GmbH ,1913