The modp1 function provides very efficient arithmetic and other operations in the domain of univariate polynomials over the integers modulo n, written $Z_n$[x]. The mod function, which supports operations in the domain of multivariate polynomials over the integers modulo n, uses modp1 for the univariate case.  Hence, interactive calculations can be performed using mod.

To achieve a high level of efficiency, modp1 uses a special representation. Explicit conversions are provided for converting the Maple "sum of products" representation to and from this representation and also from a list of integers representing a polynomial to and from this representation. Knowledge of this representation is not required by the user to use modp1. If the modulus n is sufficiently small, arithmetic in Zn is performed directly by the hardware instead of using multi-precision integer arithmetic and the data representation is an array of machine integers. The modp1(Prime(1)) command returns the largest prime for which arithmetic is done in the hardware.  On a 32-bit machine, this is the prime 46327. On a 64-bit machine, this is the prime 3037000453.

A typical use of modp1 is modp1(Eval(a, x), n), which evaluates the modp1 polynomial a at the value x (an integer) modulo n. The modp1 function accepts the following functions, whose names are also protected global names.

The Add function is n-ary.  The Subtract function is unary or binary. The Zero and One nullary functions create the $0$ and 1 modp1 polynomials. (The One and Zero functions require one argument, the indeterminate variable.) The Constant function creates a modp1 polynomial for the given integer constant. (The Constant function requires a second argument, the indeterminate variable.) The Multiply function is binary. Note that scalar multiplication requires explicit conversion using the Constant function.

The Degree function computes the degree.  The Ldegree function computes the low degree.  The Coeff function computes the coefficient. The Lcoeff function computes the leading coefficient.  The Tcoeff function computes the trailing Coefficient. The Diff function computes the derivative.  The UNormal function computes the monic part or unit normal part. Note that Degree returns 0 and Ldegree returns 1 for the zero modp1 polynomial. The Randpoly function takes a degree as an argument and generates a polynomial of the given degree with random coefficients modulo n.

The ConvertIn and ConvertOut functions convert to and from the modp1 representation. The modp1(ConvertIn(b, x), n) command converts from a univariate polynomial b in x over the integers to a modp1 polynomial modulo n. The modp1(ConvertIn([a0, a1, ..., ak], x), n) command converts from the given list of integers representing the polynomial $\mathrm{a0}+\mathrm{a1}x+...+\mathrm{ak}{x}^k$ to a modp1 polynomial. The ConvertOut function does the reverse of ConvertIn.

Note that unlike the mod function, modp1 arithmetic operations do not take the variable as an argument.  For example, the calling sequences of the Rem operation are  Rem(a, b) and Rem(a, b, 'q').  Calling sequences are similar for Coeff, Degree, Diff, Discrim, Gcdex, Interp, Lcoeff, Ldegree, Powmod, Prem, Quo, Resultant, Smith, and Tcoeff.

The Constant, Interp, Monomial, One, Randpoly, and Zero functions all expect their last argument to be the indeterminate variable.  The indeterminate of an existing modp1 polynomial can be queried using the Indeterminate function.  The modulus can be queried using Modulus.

The IsZero, IsOne, and IsConstant boolean functions must be used to check against an integer constant value.  The zero polynomial is not the same as the zero modp1 polynomial.

Separate help exists for most of the remaining functions.

$p≔11$

$p≔11$

$a≔\mathrm{modp1}\left(\mathrm{ConvertIn}\left(x^4-x^2+2\,x\right)\,p\right)$

$a≔\left(x^4+10x^2+2\right)\mathbf{mod}11$

$\mathrm{modp1}\left(\mathrm{IsZero}\left(a\right)\,p\right)$

$\mathrm{false}$

$\mathrm{modp1}\left(\mathrm{Degree}\left(a\right)\,p\right)$

$4$

$\mathrm{modp1}\left(\mathrm{Coeff}\left(a\,2\right)\,p\right)$

$10$

$b≔\mathrm{modp1}\left(\mathrm{ConvertIn}\left(\left[1\,-2\,3\,4\right]\,x\right)\,p\right)$

$b≔\left(4x^3+3x^2+9x+1\right)\mathbf{mod}11$

$\mathrm{modp1}\left(\mathrm{Multiply}\left(a\,b\right)\,p\right)$

$\left(4x^7+3x^6+5x^5+9x^4+10x^3+5x^2+7x+2\right)\mathbf{mod}11$

$\mathrm{modp1}\left(\mathrm{Rem}\left(a\,b\right)\,p\right)$

$\left(9x^2+9x+7\right)\mathbf{mod}11$

$\mathrm{modp1}\left(\mathrm{ConvertOut}\left(b\,x\right)\,p\right)$

$4x^3+3x^2+9x+1$

$\mathrm{modp1}\left(\mathrm{ConvertOut}\left(b\right)\,p\right)$

$\left[1\,9\,3\,4\right]$

$\mathrm{zero}≔\mathrm{modp1}\left(\mathrm{Zero}\left(x\right)\,p\right)$

$\mathrm{zero}≔0\mathbf{mod}11$

$\mathrm{evalb}\left(\mathrm{zero}=0\right)$

$\mathrm{false}$

$a≔\mathrm{modp1}\left(\mathrm{Randpoly}\left(10\,x\right)\,p\right)$

$a≔\left(6x^{10}+9x^9+5x^8+x^7+10x^6+3x^5+5x^4+4x^3+10x^2+7\right)\mathbf{mod}11$

$3a$

Error, invalid terms in product: modp1(ConvertIn(6*x^10+9*x^9+5*x^8+x^7+10*x^6+3*x^5+5*x^4+4*x^3+10*x^2+7,x),11)

$\mathrm{modp1}\left(\mathrm{Multiply}\left(\mathrm{Constant}\left(3\,x\right)\,b\right)\,p\right)$

$\left(x^3+9x^2+5x+3\right)\mathbf{mod}11$

$\mathrm{modp1}\left(\mathrm{Roots}\left(a\right)\,p\right)$

$\left[\left[6\,1\right]\,\left[8\,1\right]\right]$

$\mathrm{modp1}\left(\mathrm{Factors}\left(a\right)\,p\right)$

$\left[6\,\left[\left[\left(x^3+10x^2+x+8\right)\mathbf{mod}11\,1\right]\,\left[\left(x+3\right)\mathbf{mod}11\,1\right]\,\left[\left(x^5+2x^3+9x^2+5x+8\right)\mathbf{mod}11\,1\right]\,\left[\left(x+5\right)\mathbf{mod}11\,1\right]\right]\right]$

$b≔\mathrm{modp1}\left(\mathrm{Randpoly}\left(9\,x\right)\,p\right)$

$b≔\left(9x^9+10x^8+x^7+x^6+3x^5+7x^4+10x^3+2x^2+8x+9\right)\mathbf{mod}11$

$g≔\mathrm{modp1}\left(\mathrm{Gcdex}\left(a\,b\,'s'\,'t'\right)\,p\right)$

$g≔\left(x+5\right)\mathbf{mod}11$

$\mathrm{modp1}\left(\mathrm{Add}\left(\mathrm{Multiply}\left(s\,a\right)\,\mathrm{Multiply}\left(t\,b\right)\right)\,p\right)$

$\left(x+5\right)\mathbf{mod}11$

$\mathrm{modp1}\left(\mathrm{Rem}\left(\mathrm{Multiply}\left(s\,a\right)\,b\right)\,p\right)$

$\left(x+5\right)\mathbf{mod}11$