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:
|
|
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:
|
|
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:
|
|
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:
|
|
and c1[m+1] Poly2 = - c2[m+1] Poly1 mod p is an LCLM of Poly1 and Poly2.
|
|
|
Examples
|
|
>
|
|
>
|
|
| (1) |
>
|
|
| (2) |
>
|
|
| (3) |
>
|
|
| (4) |
>
|
![m := U[1]](/support/helpjp/helpview.aspx?si=7373/file06380/math268.png)
|
| (5) |
>
|
|
![vector([OrePoly(1, 3*x, x^2+10+10*x, 1+x), OrePoly(x, x, x^2+x+1), OrePoly((2*x+7*x^2+5*x^3+x^4+10*x^5)/(1+2*x+3*x^2+2*x^3+x^4), (2*x+8*x^2+10*x^3+5*x^4+2*x^5+10)/(1+2*x+3*x^2+2*x^3+x^4)), OrePoly((7*x+6*x^2+3*x^3+6*x^4+3*x^5+3*x^7+x^9+5*x^10+4*x^11+6+8*x^6+8*x^8+3*x^12)/(3+10*x+8*x^2+3*x^3+7*x^4+3*x^6+8*x^8+5*x^9+x^10))])](/support/helpjp/helpview.aspx?si=7373/file06380/math282.png)
| (6) |
Check the co-sequences.
>
|
; W2 := Modular[Multiply](c2[i], Ore2, 11, A); W := Modular[Add](W1, W2, 11); C := Modular[Minus](W, S[i], 11); print(C) end do](/support/helpjp/helpview.aspx?si=7373/file06380/math288.png)
|
| (7) |
Check the LCLM.
>
|
|
>
|
|
>
|
|
| (8) |
Try fraction-free right Euclidean algorithm.
>
|
|
| (9) |
>
|
|
| (10) |
>
|
|
| (11) |
>
|
|
| (12) |
>
|
![m := U[1]](/support/helpjp/helpview.aspx?si=7373/file06380/math351.png)
|
| (13) |
>
|
|
![vector([OrePoly(1, 3*x, x^2+10+10*x, 1+x), OrePoly(x, x, x^2+x+1), OrePoly(2*x+7*x^2+5*x^3+x^4+10*x^5, 2*x+8*x^2+10*x^3+5*x^4+2*x^5+10), OrePoly(x^8+3*x^7+4*x^5+6*x^4+7*x^3+3*x^2+2*x+2)])](/support/helpjp/helpview.aspx?si=7373/file06380/math365.png)
| (14) |
Check the co-sequences.
>
|
; W2 := Modular[Multiply](c2[i], Ore2, 11, A); W := Modular[Add](W1, W2, 11); C := Modular[Minus](W, S[i], 11); print(C) end do](/support/helpjp/helpview.aspx?si=7373/file06380/math371.png)
|
| (15) |
Check the LCLM.
>
|
|
>
|
|
>
|
|
| (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.
|
|
|