OreTools[Modular] - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Algebra : Skew Polynomials : OreTools : OreTools/Modular/FractionFreeRightEuclidean

OreTools[Modular]

  

FractionFreeRightEucliean

  

perform a fraction-free version of right Euclidean algorithm (usual, half-extended, and extended) modulo a prime

  

RightEuclidean

  

perform right Euclidean algorithm (usual, half-extended, and extended)

 

Calling Sequence

Parameters

Description

Examples

References

Calling Sequence

Modular[FractionFreeRightEuclidean](Poly1, Poly2, p, A, 'c1', 'c2')

Modular[RightEuclidean](Poly1, Poly2, p, A, 'c1', 'c2')

Parameters

Poly1, Poly2

-

nonzero Ore polynomials; to define an Ore polynomial, use the OrePoly structure

p

-

prime

A

-

Ore algebra; to define an Ore algebra, use the SetOreRing command

'c1', 'c2'

-

(optional) unevaluated names

Description

• 

Modular[FractionFreeRightEuclidean](Poly1, Poly2, p, A, 'c1', 'c2') calling sequence returns a list [m, S] where m is a positive integer and S is an array with m elements storing the subresultant sequence of the first kind of Poly1 and Poly2.

  

The Modular[FractionFreeRightEuclidean] command requires that Poly1 and Poly2 be fraction-free, and that the commutation rule of the Ore algebra A also be fraction-free.

• 

If the optional fourth argument to the FractionFreeRightEuclidean command c1 is specified, it is assigned the first co-sequence of Poly1 and Poly2 so that:

c1iPoly2=Simod Poly1andp,i=1,2,...,m

  

and c1[m+1] Poly2 is a least common left multiple (LCLM) of Poly1 and Poly2.

• 

If the optional fifth argument to the FractionFreeRightEuclidean command c2 is specified, it is assigned the second co-sequence of Poly1 and Poly2 so that:

c1iPoly2+c2iPoly1=Simodpi=1,2,...,m

  

and c1[m+1] Poly2 = - c2[m+1] Poly1 mod p is an LCLM of Poly1 and Poly2.

• 

Modular[RightEuclidean](Poly1, Poly2, p, A, 'c1', 'c2') calling sequence returns a list [m, S] where m is a positive integer and S is an array with m elements storing the right Euclidean polynomial remainder sequence of Poly1 and Poly2.

• 

If the optional fourth argument to the FractionFreeRightEuclidean command c1 is specified, it is assigned the first co-sequence of Poly1 and Poly2 so that:

c1iPoly2=Simod Poly1andp,i=1,2,...,m

  

and c1[m+1] Poly2 is a least common left multiple (LCLM) of Poly1 and Poly2.

• 

If the optional fifth argument to the Modular[RightEuclidean] command c2 is specified, it is assigned the second co-sequence of Poly1 and Poly2 so that:

c1iPoly2+c2iPoly1=Simodpi=1,2,...,m

  

and c1[m+1] Poly2 = - c2[m+1] Poly1 mod p is an LCLM of Poly1 and Poly2.

Examples

withOreTools:

ASetOreRingx,'differential'

A:=UnivariateOreRingx,differential

(1)

Ore1OrePoly1,3x,x21+x,23x+1

Ore1:=OrePoly1,3x,x2x1,23x+1

(2)

Ore2OrePolyx,x,x2+x+1

Ore2:=OrePolyx,x,x2+x+1

(3)

UModular[RightEuclidean]Ore1,Ore2,11,A,'c1','c2'

U:=4,S

(4)

mU1;SU2

m:=4

S:=S

(5)

printS

OrePoly1,3x,x2+10x+10,1+xOrePolyx,x,x2+x+1OrePoly10x5+x4+5x3+7x2+2xx4+2x3+3x2+2x+1,2x5+5x4+10x3+8x2+2x+10x4+2x3+3x2+2x+1OrePoly3x12+4x11+5x10+x9+8x8+3x7+8x6+3x5+6x4+3x3+6x2+7x+6x10+5x9+8x8+3x6+7x4+3x3+8x2+10x+3

(6)

Check the co-sequences.

foritomdoW1Modular[Multiply]c1i,Ore1,11,A;W2Modular[Multiply]c2i,Ore2,11,A;WModular[Add]W1,W2,11;CModular[Minus]W,Si,11;printCend do:

OrePoly0

OrePoly0

OrePoly0

OrePoly0

(7)

Check the LCLM.

W3Modular[Multiply]c15,Ore1,11,A:

W4Modular[Multiply]c25,Ore2,11,A:

Modular[Add]W3,W4,11

OrePoly0

(8)

Try fraction-free right Euclidean algorithm.

ASetOreRingx,'differential'

A:=UnivariateOreRingx,differential

(9)

Ore1OrePoly1,3x,x21+x,23x+1

Ore1:=OrePoly1,3x,x2x1,23x+1

(10)

Ore2OrePolyx,x,x2+x+1

Ore2:=OrePolyx,x,x2+x+1

(11)

UModular[FractionFreeRightEuclidean]Ore1,Ore2,11,A,'c1','c2'

U:=4,S

(12)

mU1;SU2

m:=4

S:=S

(13)

printS

OrePoly1,3x,x2+10x+10,1+xOrePolyx,x,x2+x+1OrePoly10x5+x4+5x3+7x2+2x,2x5+5x4+10x3+8x2+2x+10OrePolyx8+3x7+4x5+6x4+7x3+3x2+2x+2

(14)

Check the co-sequences.

foritomdoW1Modular[Multiply]c1i,Ore1,11,A;W2Modular[Multiply]c2i,Ore2,11,A;WModular[Add]W1,W2,11;CModular[Minus]W,Si,11;printCend do:

OrePoly0

OrePoly0

OrePoly0

OrePoly0

(15)

Check the LCLM.

W3Modular[Multiply]c15,Ore1,11,A:

W4Modular[Multiply]c25,Ore2,11,A:

Modular[Add]W3,W4,11

OrePoly0

(16)

References

  

Li, Z. "A subresultant theory for Ore polynomials with applications." Proc. of ISSAC'98, pp.132-139. Edited by O. Gloor. ACM Press, 1998.

See Also

OreTools

OreTools/Divisions

OreTools/Modular

OreTools/OreAlgebra

OreTools/OrePoly

OreTools[SetOreRing]

 


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