Symbolic processings of polynomia matrices using finite field transforms (Polynomial matrix-processor system design)

Abstract

A new representation of the rational polynomials with integral coefficients over a finite field by expressing each of their coefficients in a suitable prime base is outlined. A modified form of this representation using the mantissa–exponent form facilitates the algebraic manipulation of symbolic processing of non-numeric problems. The four basic arithmetical algorithms that use the code for the rational operands proceed in one direction, giving rise to an exact result having the same code-word length as the two operands. In particular, the divisional algorithm is deterministic (free from trial and error). As a result, arithmetic can be carried out exactly and much faster, using the same hardware meant for p-ary systems. Basic principles of residue arithmetic with a single modulus and multiple moduli are outlined. Procedures based on the Chinese Remainder Theorem as well as other methods are described for obtaining the residue of a number with respect to a large composite number, given the residue with respect to each of its component primes.