modp1 - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Group Theory : Numbers : Integer Functions : modp1

modp1

univariate polynomial arithmetic modulo n

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

modp1(e, n)

Parameters

e

-

algebraic expression

n

-

positive integer

Description

• 

The modp1 function provides very efficient arithmetic and other operations in the domain of univariate polynomials over the integers modulo n, written Zn[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.

Add

Chrem

Coeff

Constant

ConvertIn

ConvertOut

Degree

Det

Diff

Divide

Embed

Eval

Factors

Gcd

Gcdex

Indeterminate

Interp

Irreduc

IsConstant

IsOne

IsZero

Lcm

Lcoeff

Ldegree

Modulus

Monomial

Multiply

One

Power

Powmod

Prem

Prime

Quo

Randpoly

Rem

Resultant

Roots

Smith

Shift

Sqrfree

Subtract

Tcoeff

Translate

UNormal

Zero

• 

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 a0+a1x+...+akxk 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.

Examples

p11

p:=11

(1)

ax4x2+2 mod p

a:=x4+10x2+2 mod 11

(2)

modp1IsZeroa,p

false

(3)

modp1Degreea,p

4

(4)

modp1Coeffa,2,p

10

(5)

b1,2,3,4 mod p

b:=4x3+3x2+9x+1 mod 11

(6)

modp1Multiplya,b,p

4x7+3x6+5x5+9x4+10x3+5x2+7x+2 mod 11

(7)

modp1Rema,b,p

9x2+9x+7 mod 11

(8)

modp1ConvertOutb,x,p

4x3+3x2+9x+1

(9)

modp1ConvertOutb,p

1,9,3,4

(10)

zeromodp1Zerox,p

zero:=0 mod 11

(11)

evalbzero=0

false

(12)

amodp1Randpoly10,x,p

a:=6x10+9x9+5x8+x7+10x6+3x5+5x4+4x3+10x2+7 mod 11

(13)

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)

modp1MultiplyConstant3,x,b,p

x3+9x2+5x+3 mod 11

(14)

modp1Rootsa,p

6,1,8,1

(15)

modp1Factorsa,p

6,x+3 mod 11,1,x+5 mod 11,1,x3+10x2+x+8 mod 11,1,x5+2x3+9x2+5x+8 mod 11,1

(16)

bmodp1Randpoly9,x,p

b:=9x9+10x8+x7+x6+3x5+7x4+10x3+2x2+8x+9 mod 11

(17)

gmodp1Gcdexa,b,'s','t',p

g:=x+5 mod 11

(18)

modp1AddMultiplys,a,Multiplyt,b,p

x+5 mod 11

(19)

modp1RemMultiplys,a,b,p

x+5 mod 11

(20)

See Also

mod

modp2

type,zppoly

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam