FractionFreeRightEuclidean - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.
Our website is currently undergoing maintenance, which may result in occasional errors while browsing. We apologize for any inconvenience this may cause and are working swiftly to restore full functionality. Thank you for your patience.

Online Help

All Products    Maple    MapleSim


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

AUnivariateOreRingx,differential

(1)

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

Ore1OrePoly1,3x,x2x1,23x+1

(2)

Ore2OrePolyx,x,x2+x+1

Ore2OrePolyx,x,x2+x+1

(3)

UModularRightEuclideanOre1,Ore2,11,A,c1,c2

U4,S

(4)

mU1;SU2

m4

SS

(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.

foritomdoW1ModularMultiplyc1i,Ore1,11,A;W2ModularMultiplyc2i,Ore2,11,A;WModularAddW1,W2,11;CModularMinusW,Si,11;printCenddo:

OrePoly0

OrePoly0

OrePoly0

OrePoly0

(7)

Check the LCLM.

W3ModularMultiplyc15,Ore1,11,A:

W4ModularMultiplyc25,Ore2,11,A:

ModularAddW3,W4,11

OrePoly0

(8)

Try fraction-free right Euclidean algorithm.

ASetOreRingx,differential

AUnivariateOreRingx,differential

(9)

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

Ore1OrePoly1,3x,x2x1,23x+1

(10)

Ore2OrePolyx,x,x2+x+1

Ore2OrePolyx,x,x2+x+1

(11)

UModularFractionFreeRightEuclideanOre1,Ore2,11,A,c1,c2

U4,S

(12)

mU1;SU2

m4

SS

(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.

foritomdoW1ModularMultiplyc1i,Ore1,11,A;W2ModularMultiplyc2i,Ore2,11,A;WModularAddW1,W2,11;CModularMinusW,Si,11;printCenddo:

OrePoly0

OrePoly0

OrePoly0

OrePoly0

(15)

Check the LCLM.

W3ModularMultiplyc15,Ore1,11,A:

W4ModularMultiplyc25,Ore2,11,A:

ModularAddW3,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]