perform a fraction-free version of right Euclidean algorithm (usual, half-extended, and extended) modulo a prime - Maple 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

OreTools[Modular][RightEuclidean] - perform right Euclidean algorithm (usual, half-extended, and extended)

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:

A:=SetOreRingx,'differential'

A:=UnivariateOreRingx,differential

(1)

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

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

(2)

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

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

(3)

U:=ModularRightEuclideanOre1,Ore2,11,A,'c1','c2'

U:=4,S

(4)

m:=U1;S:=U2

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.

foritomdoW1:=ModularMultiplyc1i,Ore1,11,A;W2:=ModularMultiplyc2i,Ore2,11,A;W:=ModularAddW1,W2,11;C:=ModularMinusW,Si,11;printCend do:

OrePoly0

OrePoly0

OrePoly0

OrePoly0

(7)

Check the LCLM.

W3:=ModularMultiplyc15,Ore1,11,A:

W4:=ModularMultiplyc25,Ore2,11,A:

ModularAddW3,W4,11

OrePoly0

(8)

Try fraction-free right Euclidean algorithm.

A:=SetOreRingx,'differential'

A:=UnivariateOreRingx,differential

(9)

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

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

(10)

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

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

(11)

U:=ModularFractionFreeRightEuclideanOre1,Ore2,11,A,'c1','c2'

U:=4,S

(12)

m:=U1;S:=U2

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.

foritomdoW1:=ModularMultiplyc1i,Ore1,11,A;W2:=ModularMultiplyc2i,Ore2,11,A;W:=ModularAddW1,W2,11;C:=ModularMinusW,Si,11;printCend do:

OrePoly0

OrePoly0

OrePoly0

OrePoly0

(15)

Check the LCLM.

W3:=ModularMultiplyc15,Ore1,11,A:

W4:=ModularMultiplyc25,Ore2,11,A:

ModularAddW3,W4,11

OrePoly0

(16)

See Also

OreTools, OreTools/Divisions, OreTools/Modular, OreTools/OreAlgebra, OreTools/OrePoly, OreTools[SetOreRing]

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.


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