OreTools[Modular] - Maple Programming Help

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 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:

${\mathrm{c1}}_{i}\mathrm{Poly2}={S}_{i}\mathrm{mod Poly}1\mathrm{and}p,\left(i=1,2,\mathrm{...},m\right)$

 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:

${\mathrm{c1}}_{i}\mathrm{Poly2}+{\mathrm{c2}}_{i}\mathrm{Poly1}={S}_{i}\mathrm{mod}p\left(i=1,2,\mathrm{...},m\right)$

 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:

${\mathrm{c1}}_{i}\mathrm{Poly2}={S}_{i}\mathrm{mod Poly}1\mathrm{and}p,\left(i=1,2,\mathrm{...},m\right)$

 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:

${\mathrm{c1}}_{i}\mathrm{Poly2}+{\mathrm{c2}}_{i}\mathrm{Poly1}={S}_{i}\mathrm{mod}p\left(i=1,2,\mathrm{...},m\right)$

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

Examples

 > $\mathrm{with}\left(\mathrm{OreTools}\right):$
 > $A≔\mathrm{SetOreRing}\left(x,'\mathrm{differential}'\right)$
 ${A}{≔}{\mathrm{UnivariateOreRing}}{}\left({x}{,}{\mathrm{differential}}\right)$ (1)
 > $\mathrm{Ore1}≔\mathrm{OrePoly}\left(1,3x,{x}^{2}-\left(1+x\right),23x+1\right)$
 ${\mathrm{Ore1}}{≔}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}{,}{{x}}^{{2}}{-}{x}{-}{1}{,}{23}{}{x}{+}{1}\right)$ (2)
 > $\mathrm{Ore2}≔\mathrm{OrePoly}\left(x,x,{x}^{2}+x+1\right)$
 ${\mathrm{Ore2}}{≔}{\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)$ (3)
 > $U≔\mathrm{Modular}[\mathrm{RightEuclidean}]\left(\mathrm{Ore1},\mathrm{Ore2},11,A,'\mathrm{c1}','\mathrm{c2}'\right)$
 ${U}{≔}\left[{4}{,}{S}\right]$ (4)
 > $m≔{U}_{1};$$S≔{U}_{2}$
 ${m}{≔}{4}$
 ${S}{≔}{S}$ (5)
 > $\mathrm{print}\left(S\right)$
 $\left[\begin{array}{cccc}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}{,}{{x}}^{{2}}{+}{10}{}{x}{+}{10}{,}{1}{+}{x}\right)& {\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)& {\mathrm{OrePoly}}{}\left(\frac{{10}{}{{x}}^{{5}}{+}{{x}}^{{4}}{+}{5}{}{{x}}^{{3}}{+}{7}{}{{x}}^{{2}}{+}{2}{}{x}}{{{x}}^{{4}}{+}{2}{}{{x}}^{{3}}{+}{3}{}{{x}}^{{2}}{+}{2}{}{x}{+}{1}}{,}\frac{{2}{}{{x}}^{{5}}{+}{5}{}{{x}}^{{4}}{+}{10}{}{{x}}^{{3}}{+}{8}{}{{x}}^{{2}}{+}{2}{}{x}{+}{10}}{{{x}}^{{4}}{+}{2}{}{{x}}^{{3}}{+}{3}{}{{x}}^{{2}}{+}{2}{}{x}{+}{1}}\right)& {\mathrm{OrePoly}}{}\left(\frac{{3}{}{{x}}^{{12}}{+}{4}{}{{x}}^{{11}}{+}{5}{}{{x}}^{{10}}{+}{{x}}^{{9}}{+}{8}{}{{x}}^{{8}}{+}{3}{}{{x}}^{{7}}{+}{8}{}{{x}}^{{6}}{+}{3}{}{{x}}^{{5}}{+}{6}{}{{x}}^{{4}}{+}{3}{}{{x}}^{{3}}{+}{6}{}{{x}}^{{2}}{+}{7}{}{x}{+}{6}}{{{x}}^{{10}}{+}{5}{}{{x}}^{{9}}{+}{8}{}{{x}}^{{8}}{+}{3}{}{{x}}^{{6}}{+}{7}{}{{x}}^{{4}}{+}{3}{}{{x}}^{{3}}{+}{8}{}{{x}}^{{2}}{+}{10}{}{x}{+}{3}}\right)\end{array}\right]$ (6)

Check the co-sequences.

 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}m\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{W1}≔\mathrm{Modular}[\mathrm{Multiply}]\left({\mathrm{c1}}_{i},\mathrm{Ore1},11,A\right);\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{W2}≔\mathrm{Modular}[\mathrm{Multiply}]\left({\mathrm{c2}}_{i},\mathrm{Ore2},11,A\right);\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}W≔\mathrm{Modular}[\mathrm{Add}]\left(\mathrm{W1},\mathrm{W2},11\right);\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}C≔\mathrm{Modular}[\mathrm{Minus}]\left(W,{S}_{i},11\right);\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{print}\left(C\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end do}:$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (7)

Check the LCLM.

 > $\mathrm{W3}≔\mathrm{Modular}[\mathrm{Multiply}]\left({\mathrm{c1}}_{5},\mathrm{Ore1},11,A\right):$
 > $\mathrm{W4}≔\mathrm{Modular}[\mathrm{Multiply}]\left({\mathrm{c2}}_{5},\mathrm{Ore2},11,A\right):$
 > $\mathrm{Modular}[\mathrm{Add}]\left(\mathrm{W3},\mathrm{W4},11\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (8)

Try fraction-free right Euclidean algorithm.

 > $A≔\mathrm{SetOreRing}\left(x,'\mathrm{differential}'\right)$
 ${A}{≔}{\mathrm{UnivariateOreRing}}{}\left({x}{,}{\mathrm{differential}}\right)$ (9)
 > $\mathrm{Ore1}≔\mathrm{OrePoly}\left(1,3x,{x}^{2}-\left(1+x\right),23x+1\right)$
 ${\mathrm{Ore1}}{≔}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}{,}{{x}}^{{2}}{-}{x}{-}{1}{,}{23}{}{x}{+}{1}\right)$ (10)
 > $\mathrm{Ore2}≔\mathrm{OrePoly}\left(x,x,{x}^{2}+x+1\right)$
 ${\mathrm{Ore2}}{≔}{\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)$ (11)
 > $U≔\mathrm{Modular}[\mathrm{FractionFreeRightEuclidean}]\left(\mathrm{Ore1},\mathrm{Ore2},11,A,'\mathrm{c1}','\mathrm{c2}'\right)$
 ${U}{≔}\left[{4}{,}{S}\right]$ (12)
 > $m≔{U}_{1};$$S≔{U}_{2}$
 ${m}{≔}{4}$
 ${S}{≔}{S}$ (13)
 > $\mathrm{print}\left(S\right)$
 $\left[\begin{array}{cccc}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}{,}{{x}}^{{2}}{+}{10}{}{x}{+}{10}{,}{1}{+}{x}\right)& {\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)& {\mathrm{OrePoly}}{}\left({10}{}{{x}}^{{5}}{+}{{x}}^{{4}}{+}{5}{}{{x}}^{{3}}{+}{7}{}{{x}}^{{2}}{+}{2}{}{x}{,}{2}{}{{x}}^{{5}}{+}{5}{}{{x}}^{{4}}{+}{10}{}{{x}}^{{3}}{+}{8}{}{{x}}^{{2}}{+}{2}{}{x}{+}{10}\right)& {\mathrm{OrePoly}}{}\left({{x}}^{{8}}{+}{3}{}{{x}}^{{7}}{+}{4}{}{{x}}^{{5}}{+}{6}{}{{x}}^{{4}}{+}{7}{}{{x}}^{{3}}{+}{3}{}{{x}}^{{2}}{+}{2}{}{x}{+}{2}\right)\end{array}\right]$ (14)

Check the co-sequences.

 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}m\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{W1}≔\mathrm{Modular}[\mathrm{Multiply}]\left({\mathrm{c1}}_{i},\mathrm{Ore1},11,A\right);\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{W2}≔\mathrm{Modular}[\mathrm{Multiply}]\left({\mathrm{c2}}_{i},\mathrm{Ore2},11,A\right);\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}W≔\mathrm{Modular}[\mathrm{Add}]\left(\mathrm{W1},\mathrm{W2},11\right);\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}C≔\mathrm{Modular}[\mathrm{Minus}]\left(W,{S}_{i},11\right);\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{print}\left(C\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end do}:$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (15)

Check the LCLM.

 > $\mathrm{W3}≔\mathrm{Modular}[\mathrm{Multiply}]\left({\mathrm{c1}}_{5},\mathrm{Ore1},11,A\right):$
 > $\mathrm{W4}≔\mathrm{Modular}[\mathrm{Multiply}]\left({\mathrm{c2}}_{5},\mathrm{Ore2},11,A\right):$
 > $\mathrm{Modular}[\mathrm{Add}]\left(\mathrm{W3},\mathrm{W4},11\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (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.