Return to upoly.texi CVS log

Up to [local] / OpenXM / src / asir-doc / parts / builtin

Annotation of OpenXM/src/asir-doc/parts/builtin/upoly.texi, Revision 1.2

1.2     ! noro        1: @comment $OpenXM$
        !             2: \BJP
1.1       noro        3: @node $B0lJQ?tB?9`<0$N1i;;(B,,, $BAH$_9~$_H!?t(B
                      4: @section $B0lJQ?tB?9`<0$N1i;;(B
1.2     ! noro        5: \E
        !             6: \BEG
        !             7: @node Univariate polynomials,,, Built-in Function
        !             8: @section Univariate polynomials
        !             9: \E
1.1       noro       10:
                     11: @menu
                     12: * umul umul_ff usquare usquare_ff utmul utmul_ff::
                     13: * kmul ksquare ktmul::
                     14: * utrunc udecomp ureverse::
                     15: * set_upkara set_uptkara set_upfft::
                     16: * uinv_as_power_series ureverse_inv_as_power_series::
                     17: * udiv urem urembymul urembymul_precomp ugcd::
                     18: @end menu
                     19:
1.2     ! noro       20: \JP @node umul umul_ff usquare usquare_ff utmul utmul_ff,,, $B0lJQ?tB?9`<0$N1i;;(B
        !            21: \EG @node umul umul_ff usquare usquare_ff utmul utmul_ff,,, Univariate polynomials
1.1       noro       22: @subsection @code{umul}, @code{umul_ff}, @code{usquare}, @code{usquare_ff}, @code{utmul}, @code{utmul_ff}
                     23: @findex umul
                     24: @findex umul_ff
                     25: @findex usquare
                     26: @findex usquare_ff
                     27: @findex utmul
                     28: @findex utmul_ff
                     29:
                     30: @table @t
                     31: @item umul(@var{p1},@var{p2})
                     32: @itemx umul_ff(@var{p1},@var{p2})
1.2     ! noro       33: \JP :: $B0lJQ?tB?9`<0$N9bB.>h;;(B
        !            34: \EG :: Fast multiplication of univariate polynomials
1.1       noro       35: @item usquare(@var{p1})
                     36: @itemx usquare_ff(@var{p1})
1.2     ! noro       37: \JP :: $B0lJQ?tB?9`<0$N9bB.(B 2 $B>h;;(B
        !            38: \EG :: Fast squaring of a univariate polynomial
1.1       noro       39: @item utmul(@var{p1},@var{p2},@var{d})
                     40: @itemx utmul_ff(@var{p1},@var{p2},@var{d})
1.2     ! noro       41: \JP :: $B0lJQ?tB?9`<0$N9bB.>h;;(B ($BBG$A@Z$j<!?t;XDj(B)
        !            42: \EG :: Fast multiplication of univariate polynomials with truncation
1.1       noro       43: @end table
                     44:
                     45: @table @var
                     46: @item return
1.2     ! noro       47: \JP $B0lJQ?tB?9`<0(B
        !            48: \EG univariate polynomial
1.1       noro       49: @item p1 p2
1.2     ! noro       50: \JP $B0lJQ?tB?9`<0(B
        !            51: \EG univariate polynomial
1.1       noro       52: @item d
1.2     ! noro       53: \JP $BHsIi@0?t(B
        !            54: \EG non-negative integer
1.1       noro       55: @end table
                     56:
                     57: @itemize @bullet
1.2     ! noro       58: \BJP
1.1       noro       59: @item
                     60: $B0lJQ?tB?9`<0$N>h;;$r(B, $B<!?t$K1~$8$F7h$^$k%"%k%4%j%:%`$rMQ$$$F(B
                     61: $B9bB.$K9T$&(B.
                     62: @item
                     63: @code{umul()}, @code{usquare()}, @code{utmul()} $B$O(B
                     64: $B78?t$r@0?t$H8+$J$7$F(B, $B@0?t78?t$NB?9`<0$H$7$F@Q$r5a$a$k(B.
                     65: $B78?t$,M-8BBN(B GF(p) $B$N85$N>l9g$K$O(B, $B78?t$O(B 0 $B0J>e(B p $BL$K~$N@0?t$H8+$J$5$l$k(B.
                     66: @item
                     67: @code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()} $B$O(B,
                     68: $B78?t$rM-8BBN$N85$H8+$J$7$F(B, $BM-8BBN>e$NB?9`<0$H$7$F(B
1.2     ! noro       69: $B@Q$r5a$a$k(B. $B$?$@$7(B, $B0z?t$N78?t$,@0?t$N>l9g(B,
1.1       noro       70: $B@0?t78?t$NB?9`<0$rJV$9>l9g$b$"$k$N$G(B, $B$3$l$i$r8F$S=P$7$?7k2L(B
                     71: $B$,M-8BBN78?t$G$"$k$3$H$rJ]>Z$9$k$?$a$K$O(B
                     72: $B$"$i$+$8$a(B @code{simp_ff()} $B$G78?t$rM-8BBN$N85$KJQ49$7$F$*$/$H$h$$(B.
                     73: @item
                     74: @code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()} $B$O(B,
                     75: GF(2^n) $B78?t$NB?9`<0$r0z?t$K<h$l$J$$(B.
                     76: @item
                     77: @code{umul()}, @code{umul_ff()} $B$N7k2L$O(B @var{p1}, @var{p2} $B$N@Q(B,
                     78: @code{usquare()}, @code{usquare_ff()} $B$N7k2L$O(B @var{p1} $B$N(B 2 $B>h(B,
                     79: @code{utmul()}, @code{utmul_ff()} $B$N7k2L$O(B @var{p1}, @var{p2} $B$N@Q(B
                     80: $B$N(B, @var{d} $B<!0J2<$NItJ,$H$J$k(B.
                     81: @item
                     82: $B$$$:$l$b(B, @code{set_upkara()} (@code{utmul}, @code{utmul_ff} $B$K$D$$$F$O(B
                     83: @code{set_uptkara()}) $B$GJV$5$l$kCM0J2<$N<!?t$KBP$7$F$ODL>o$NI.;;(B
1.2     ! noro       84: $B7A<0$NJ}K!(B, @code{set_upfft()} $B$GJV$5$l$kCM0J2<$N<!?t$KBP$7$F$O(B Karatsuba
1.1       noro       85: $BK!(B, $B$=$l0J>e$G$O(B FFT$B$*$h$SCf9q>jM>DjM}$,MQ$$$i$l$k(B. $B$9$J$o$A(B,
                     86: $B@0?t$KBP$9$k(B FFT $B$G$O$J$/(B, $B==J,B?$/$N(B 1 $B%o!<%I0JFb$NK!(B @var{mi} $B$rMQ0U$7(B,
                     87: @var{p1}, @var{p2} $B$N78?t$r(B @var{mi} $B$G3d$C$?M>$j$H$7$?$b$N$N@Q$r(B,
                     88: FFT $B$G7W;;$7(B, $B:G8e$KCf9q>jM>DjM}$G9g@.$9$k(B. $B$=$N:](B, $BM-8BBNHG$N4X?t$K(B
                     89: $B$*$$$F$O(B, $B:G8e$K4pACBN$rI=$9K!$G3F78?t$N>jM>$r7W;;$9$k$,(B, $B$3$3$G$O(B
1.2     ! noro       90: Shoup $B$K$h$k%H%j%C%/(B @code{[Shoup]} $B$rMQ$$$F9bB.2=$7$F$"$k(B.
        !            91: \E
        !            92: \BEG
        !            93: @item
        !            94: These functions compute products of univariate polynomials
        !            95: by selecting an appropriate algorithm depending on the degrees
        !            96: of inputs.
        !            97: @item
        !            98: @code{umul()}, @code{usquare()}, @code{utmul()}
        !            99: compute products over the integers.
        !           100: Coefficients in GF(p) are regarded as non-negative integers
        !           101: less than p.
        !           102: @item
        !           103: @code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()}
        !           104: compute products over a finite field. However, if some of
        !           105: the coefficients of the inputs are integral,
        !           106: the result may be an integral polynomial. So if one wants
        !           107: to assure that the result is a polynomial over the finite field,
        !           108: apply @code{simp_ff()} to the inputs.
        !           109: @item
        !           110: @code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()}
        !           111: cannot take polynomials over GF(2^n) as their inputs.
        !           112: @item
        !           113: @code{umul()}, @code{umul_ff()} produce @var{p1*p2}.
        !           114: @code{usquare()}, @code{usquare_ff()} produce @var{p1^2}.
        !           115: @code{utmul()}, @code{utmul_ff()} produce @var{p1*p2 mod v^(d+1)},
        !           116: where @var{v} is the variable of @var{p1}, @var{p2}.
        !           117: @item
        !           118: If the degrees of the inputs are less than or equal to the
        !           119: value returned by @code{set_upkara()} (@code{set_uptkara()} for
        !           120: @code{utmul}, @code{utmul_ff}), usual pencil and paper method is
        !           121: used. If the degrees of the inputs are less than or equall to
        !           122: the value returned by @code{set_upfft()}, Karatsuba algorithm
        !           123: is used. If the degrees of the inputs exceed it, a combination
        !           124: of FFT and Chinese remainder theorem is used.
        !           125: First of all sufficiently many primes @var{mi}
        !           126: within 1 machine word are prepared.
        !           127: Then @var{p1*p2 mod mi} is computed by FFT for each @var{mi}.
        !           128: Finally they are combined by Chinese remainder theorem.
        !           129: The functions over finite fields use an improvement by V. Shoup @code{[Shoup]}.
        !           130: \E
1.1       noro      131: @end itemize
                    132:
                    133: @example
                    134: [176] load("fff")$
                    135: [177] cputime(1)$
                    136: 0sec(1.407e-05sec)
                    137: [178] setmod_ff(2^160-47);
                    138: 1461501637330902918203684832716283019655932542929
                    139: 0sec(0.00028sec)
                    140: [179] A=randpoly_ff(100,x)$
                    141: 0sec(0.001422sec)
                    142: [180] B=randpoly_ff(100,x)$
                    143: 0sec(0.00107sec)
                    144: [181] for(I=0;I<100;I++)A*B;
                    145: 7.77sec + gc : 8.38sec(16.15sec)
                    146: [182] for(I=0;I<100;I++)umul(A,B);
                    147: 2.24sec + gc : 1.52sec(3.767sec)
                    148: [183] for(I=0;I<100;I++)umul_ff(A,B);
                    149: 1.42sec + gc : 0.24sec(1.653sec)
                    150: [184] for(I=0;I<100;I++)usquare_ff(A);
                    151: 1.08sec + gc : 0.21sec(1.297sec)
                    152: [185] for(I=0;I<100;I++)utmul_ff(A,B,100);
                    153: 1.2sec + gc : 0.17sec(1.366sec)
                    154: [186] deg(utmul_ff(A,B,100),x);
                    155: 100
                    156: @end example
                    157:
                    158: @table @t
1.2     ! noro      159: \JP @item $B;2>H(B
        !           160: \EG @item References
1.1       noro      161: @fref{set_upkara set_uptkara set_upfft},
                    162: @fref{kmul ksquare ktmul}.
                    163: @end table
                    164:
1.2     ! noro      165: \JP @node kmul ksquare ktmul,,, $B0lJQ?tB?9`<0$N1i;;(B
        !           166: \EG @node kmul ksquare ktmul,,, Univariate polynomials
1.1       noro      167: @subsection @code{kmul}, @code{ksquare}, @code{ktmul}
                    168: @findex kmul
                    169: @findex ksquare
                    170: @findex ktmul
                    171:
                    172: @table @t
                    173: @item kmul(@var{p1},@var{p2})
1.2     ! noro      174: \JP :: $B0lJQ?tB?9`<0$N9bB.>h;;(B
        !           175: \EG :: Fast multiplication of univariate polynomials
1.1       noro      176: @item ksquare(@var{p1})
1.2     ! noro      177: \JP :: $B0lJQ?tB?9`<0$N9bB.(B 2 $B>h;;(B
        !           178: \EG :: Fast squaring of a univariate polynomial
1.1       noro      179: @item ktmul(@var{p1},@var{p2},@var{d})
1.2     ! noro      180: \JP :: $B0lJQ?tB?9`<0$N9bB.>h;;(B ($BBG$A@Z$j<!?t;XDj(B)
        !           181: \EG :: Fast multiplication of univariate polynomials with truncation
1.1       noro      182: @end table
                    183:
                    184: @table @var
                    185: @item return
1.2     ! noro      186: \JP $B0lJQ?tB?9`<0(B
        !           187: \EG univariate polynomial
1.1       noro      188: @item p1 p2
1.2     ! noro      189: \JP $B0lJQ?tB?9`<0(B
        !           190: \EG univariate polynomial
1.1       noro      191: @item d
1.2     ! noro      192: \JP $BHsIi@0?t(B
        !           193: \EG non-negative integer
1.1       noro      194: @end table
                    195:
                    196: @itemize @bullet
1.2     ! noro      197: \BJP
1.1       noro      198: @item
                    199: $B0lJQ?tB?9`<0$N>h;;$r(B Karatsuba $BK!$G9T$&(B.
                    200: @item
                    201: $B4pK\E*$K$O(B @code{umul} $B$HF1MM$@$,(B, $B<!?t$,Bg$-$/$J$C$F$b(B
                    202: FFT $B$rMQ$$$?9bB.2=$O9T$o$J$$(B.
                    203: @item
                    204: GF(2^n) $B78?t$NB?9`<0$K$bMQ$$$k$3$H$,$G$-$k(B.
1.2     ! noro      205: \E
        !           206: \BEG
        !           207: These functions compute products of univariate polynomials by Karatsuba
        !           208: algorithm.
        !           209: @item
        !           210: These functions do not apply FFT for large degree inputs.
        !           211: @item
        !           212: These functions can compute products over GF(2^n).
        !           213: \E
1.1       noro      214: @end itemize
                    215:
                    216: @example
                    217: [0] load("code/fff");
                    218: 1
                    219: [34] setmod_ff(defpoly_mod2(160));
                    220: x^160+x^5+x^3+x^2+1
                    221: [35] A=randpoly_ff(100,x)$
                    222: [36] B=randpoly_ff(100,x)$
                    223: [37] umul(A,B)$
                    224: umul : invalid argument
                    225: return to toplevel
                    226: [37] kmul(A,B)$
                    227: @end example
                    228:
1.2     ! noro      229: \JP @node set_upkara set_uptkara set_upfft,,, $B0lJQ?tB?9`<0$N1i;;(B
        !           230: \EG @node set_upkara set_uptkara set_upfft,,, Univariate polynomials
1.1       noro      231: @subsection @code{set_upkara}, @code{set_uptkara}, @code{set_upfft}
                    232: @findex set_upkara
                    233: @findex set_uptkara
                    234: @findex set_upfft
                    235:
                    236: @table @t
                    237: @item set_upkara([@var{threshold}])
                    238: @itemx set_uptkara([@var{threshold}])
                    239: @itemx set_upfft([@var{threshold}])
1.2     ! noro      240: \JP :: 1 $BJQ?tB?9`<0$N@Q1i;;$K$*$1$k(B N^2 , Karatsuba, FFT $B%"%k%4%j%:%`$N@ZBX$($NogCM(B
        !           241: \BEG
        !           242: :: Set thresholds in the selection of an algorithm from N^2, Karatsuba,
        !           243: FFT algorithms for univariate polynomial multiplication.
        !           244: \E
1.1       noro      245: @end table
                    246:
                    247: @table @var
                    248: @item return
1.2     ! noro      249: \JP $B@_Dj$5$l$F$$$kCM(B
        !           250: \EG value currently set
1.1       noro      251: @item threshold
1.2     ! noro      252: \JP $BHsIi@0?t(B
        !           253: \EG non-negative integer
1.1       noro      254: @end table
                    255:
                    256: @itemize @bullet
1.2     ! noro      257: \BJP
1.1       noro      258: @item
                    259: $B$$$:$l$b(B, $B0lJQ?tB?9`<0$N@Q$N7W;;$K$*$1$k(B, $B%"%k%4%j%:%`@ZBX$($NogCM$r(B
                    260: $B@_Dj$9$k(B.
                    261: @item
                    262: $B0lJQ?tB?9`<0$N@Q$O(B, $B<!?t(B N $B$,>.$5$$HO0O$G$ODL>o$N(B N^2 $B%"%k%4%j%:%`(B, $BCfDxEY(B
                    263: $B$N>l9g(B Karatsuba $B%"%k%4%j%:%`(B, $BBg$-$$>l9g$K$O(B FFT $B%"%k%4%j%:%`$G7W;;(B
                    264: $B$5$l$k(B. $B$3$N@ZBX$($N<!?t$r@_Dj$9$k(B.
                    265: @item
                    266: $B>\:Y$O(B, $B$=$l$>$l$N@Q4X?t$N9`$r;2>H$N$3$H(B.
1.2     ! noro      267: \E
        !           268: \BEG
        !           269: @item
        !           270: These functions set thresholds in the selection of an algorithm from N^2,
        !           271: Karatsuba, FFT algorithms for univariate polynomial multiplication.
        !           272: @item
        !           273: Products of univariate polynomials are computed by N^2, Karatsuba,
        !           274: FFT algorithms. The algorithm selection is done according to the degrees of
        !           275: input polynomials and the thresholds.
        !           276: @item
        !           277: See the description of each function for details.
        !           278: \E
1.1       noro      279: @end itemize
                    280:
                    281: @table @t
1.2     ! noro      282: \JP @item $B;2>H(B
        !           283: \EG @item References
1.1       noro      284: @fref{kmul ksquare ktmul},
                    285: @fref{umul umul_ff usquare usquare_ff utmul utmul_ff}.
                    286: @end table
                    287:
1.2     ! noro      288: \JP @node utrunc udecomp ureverse,,, $B0lJQ?tB?9`<0$N1i;;(B
        !           289: \EG @node utrunc udecomp ureverse,,, Univariate polynomials
1.1       noro      290: @subsection @code{utrunc}, @code{udecomp}, @code{ureverse}
                    291: @findex utrunc
                    292: @findex udecomp
                    293: @findex ureverse
                    294:
                    295: @table @t
                    296: @item utrunc(@var{p},@var{d})
                    297: @itemx udecomp(@var{p},@var{d})
                    298: @itemx ureverse(@var{p})
1.2     ! noro      299: \JP :: $BB?9`<0$KBP$9$kA`:n(B
        !           300: \EG :: Operations on polynomials
1.1       noro      301: @end table
                    302:
                    303: @table @var
                    304: @item return
1.2     ! noro      305: \JP $B0lJQ?tB?9`<0$"$k$$$O0lJQ?tB?9`<0$N%j%9%H(B
        !           306: \EG univariate polynomial or list of univariate polynomials
1.1       noro      307: @item p
1.2     ! noro      308: \JP $B0lJQ?tB?9`<0(B
        !           309: \EG univariate polynomial
1.1       noro      310: @item d
1.2     ! noro      311: \JP $BHsIi@0?t(B
        !           312: \EG non-negative integer
1.1       noro      313: @end table
                    314:
                    315: @itemize @bullet
1.2     ! noro      316: \BJP
1.1       noro      317: @item
                    318: @var{p} $B$NJQ?t$r(B x $B$H$9$k(B. $B$3$N$H$-(B @var{p} = @var{p1}+x^(d+1)@var{p2}
                    319: (@var{p1} $B$N<!?t$O(B @var{d} $B0J2<(B) $B$HJ,2r$G$-$k(B. @code{utrunc()} $B$O(B
                    320: @var{p1} $B$rJV$7(B, @code{udecomp()} $B$O(B [@var{p1},@var{p2}] $B$rJV$9(B.
                    321: @item
                    322: @var{p} $B$N<!?t$r(B @var{e} $B$H$7(B, @var{i} $B<!$N78?t$r(B @var{p[i]} $B$H$9$l$P(B,
                    323: @code{ureverse()} $B$O(B @var{p[e]}+@var{p[e-1]}x+... $B$rJV$9(B.
1.2     ! noro      324: \E
        !           325: \BEG
        !           326: @item
        !           327: Let @var{x} be the variable of @var{p}. Then @var{p} can be decomposed
        !           328: as @var{p} = @var{p1}+x^(d+1)@var{p2}, where the degree of @var{p1}
        !           329: is less than or equal to @var{d}.
        !           330: Under the decomposition, @code{utrunc()} returns
        !           331: @var{p1} and  @code{udecomp()} returns [@var{p1},@var{p2}].
        !           332: @item
        !           333: Let @var{e} be the degree of @var{p} and @var{p[i]} the coefficient
        !           334: of @var{p} at degree @var{i}. Then
        !           335: @code{ureverse()} returns @var{p[e]}+@var{p[e-1]}x+....
        !           336: \E
1.1       noro      337: @end itemize
                    338:
                    339: @example
                    340: [132] utrunc((x+1)^10,5);
                    341: 252*x^5+210*x^4+120*x^3+45*x^2+10*x+1
                    342: [133] udecomp((x+1)^10,5);
                    343: [252*x^5+210*x^4+120*x^3+45*x^2+10*x+1,x^4+10*x^3+45*x^2+120*x+210]
                    344: [134] ureverse(3*x^3+x^2+2*x);
                    345: 2*x^2+x+3
                    346: @end example
                    347:
                    348: @table @t
1.2     ! noro      349: \JP @item $B;2>H(B
        !           350: \EG @item References
1.1       noro      351: @fref{udiv urem urembymul urembymul_precomp ugcd}.
                    352: @end table
                    353:
1.2     ! noro      354: \JP @node uinv_as_power_series ureverse_inv_as_power_series,,, $B0lJQ?tB?9`<0$N1i;;(B
        !           355: \EG @node uinv_as_power_series ureverse_inv_as_power_series,,, Univariate polynomials
1.1       noro      356: @subsection @code{uinv_as_power_series}, @code{ureverse_inv_as_power_series}
                    357: @findex uinv_as_power_series
                    358: @findex ureverse_inv_as_power_series
                    359:
                    360: @table @t
                    361: @item uinv_as_power_series(@var{p},@var{d})
                    362: @itemx ureverse_inv_as_power_series(@var{p},@var{d})
1.2     ! noro      363: \JP :: $BB?9`<0$rQQ5i?t$H$_$F(B, $B5U857W;;(B
        !           364: \EG :: Computes the truncated inverse as a power series.
1.1       noro      365: @end table
                    366:
                    367: @table @var
                    368: @item return
1.2     ! noro      369: \JP $B0lJQ?tB?9`<0(B
        !           370: \EG univariate polynomial
1.1       noro      371: @item p
1.2     ! noro      372: \JP $B0lJQ?tB?9`<0(B
        !           373: \EG univariate polynomial
1.1       noro      374: @item d
1.2     ! noro      375: \JP $BHsIi@0?t(B
        !           376: \EG non-negative integer
1.1       noro      377: @end table
                    378:
                    379: @itemize @bullet
1.2     ! noro      380: \BJP
1.1       noro      381: @item
                    382: @code{uinv_as_power_series(@var{p},@var{d})} $B$O(B, $BDj?t9`$,(B 0 $B$G$J$$(B
                    383: $BB?9`<0(B @var{p} $B$KBP$7(B, @var{p}@var{r}-1 $B$N:GDc<!?t$,(B @var{d}+1
                    384: $B0J>e$K$J$k$h$&$J(B $B9b!9(B @var{d} $B<!$NB?9`<0(B @var{r} $B$r5a$a$k(B.
                    385: @item
                    386: @code{ureverse_inv_as_power_series(@var{p},@var{d})} $B$O(B
                    387: @var{p} $B$N<!?t$r(B @var{e} $B$H$9$k$H$-(B, @var{p1}=@code{ureverse(@var{p},@var{e})}
                    388: $B$KBP$7$F(B @code{uinv_as_power_series(@var{p1},@var{d})} $B$r7W;;$9$k(B.
                    389: @item
                    390: @code{rembymul_precomp()} $B$N0z?t$H$7$FMQ$$$k>l9g(B, @code{ureverse_inv_as_power_series()} $B$N7k2L$r$=$N$^$^MQ$$$k$3$H$,$G$-$k(B.
1.2     ! noro      391: \E
        !           392: \BEG
        !           393: @item
        !           394: For a polynomial @var{p} with a non zero constant term,
        !           395: @code{uinv_as_power_series(@var{p},@var{d})} computes
        !           396: a polynomial @var{r} whose degree is at most @var{d}
        !           397: such that @var{p*r = 1 mod x^(d+1)}, where @var{x} is the variable
        !           398: of @var{p}.
        !           399: @item
        !           400: Let @var{e} be the degree of @var{p}.
        !           401: @code{ureverse_inv_as_power_series(@var{p},@var{d})} computes
        !           402: @code{uinv_as_power_series(@var{p1},@var{d})} for
        !           403: @var{p1}=@code{ureverse(@var{p},@var{e})}.
        !           404: @item
        !           405: The output of @code{ureverse_inv_as_power_series()} can be used
        !           406: as the input of @code{rembymul_precomp()}.
        !           407: \E
1.1       noro      408: @end itemize
                    409:
                    410: @example
                    411: [123] A=(x+1)^5;
                    412: x^5+5*x^4+10*x^3+10*x^2+5*x+1
                    413: [124] uinv_as_power_series(A,5);
                    414: -126*x^5+70*x^4-35*x^3+15*x^2-5*x+1
                    415: [126] A*R;
                    416: -126*x^10-560*x^9-945*x^8-720*x^7-210*x^6+1
                    417: [127] A=x^10+x^9;
                    418: x^10+x^9
                    419: [128] R=ureverse_inv_as_power_series(A,5);
                    420: -x^5+x^4-x^3+x^2-x+1
                    421: [129] ureverse(A)*R;
                    422: -x^6+1
                    423: @end example
                    424:
                    425: @table @t
1.2     ! noro      426: \JP @item $B;2>H(B
        !           427: \EG @item References
1.1       noro      428: @fref{utrunc udecomp ureverse},
                    429: @fref{udiv urem urembymul urembymul_precomp ugcd}.
                    430: @end table
                    431:
1.2     ! noro      432: \JP @node udiv urem urembymul urembymul_precomp ugcd,,, $B0lJQ?tB?9`<0$N1i;;(B
        !           433: \EG @node udiv urem urembymul urembymul_precomp ugcd,,, Univariate polynomials
1.1       noro      434: @subsection @code{udiv}, @code{urem}, @code{urembymul}, @code{urembymul_precomp}, @code{ugcd}
                    435: @findex udiv
                    436: @findex urem
                    437: @findex urembymul
                    438: @findex urembymul_precomp
                    439: @findex ugcd
                    440:
                    441: @table @t
                    442: @item udiv(@var{p1},@var{p2})
                    443: @item urem(@var{p1},@var{p2})
                    444: @item urembymul(@var{p1},@var{p2})
                    445: @item urembymul_precomp(@var{p1},@var{p2},@var{inv})
                    446: @item ugcd(@var{p1},@var{p2})
1.2     ! noro      447: \JP :: $B0lJQ?tB?9`<0$N=|;;(B, GCD
        !           448: \EG :: Division and GCD for univariate polynomials.
1.1       noro      449: @end table
                    450:
                    451: @table @var
                    452: @item return
1.2     ! noro      453: \JP $B0lJQ?tB?9`<0(B
        !           454: \EG univariate polynomial
1.1       noro      455: @item p1,p2,inv
1.2     ! noro      456: \JP $B0lJQ?tB?9`<0(B
        !           457: \EG univariate polynomial
1.1       noro      458: @end table
                    459:
                    460: @itemize @bullet
1.2     ! noro      461: \BJP
1.1       noro      462: @item
                    463: $B0lJQ?tB?9`<0(B @var{p1}, @var{p2} $B$KBP$7(B,
                    464: @code{udiv} $B$O>&(B, @code{urem}, @code{urembymul} $B$O>jM>(B,
                    465: @code{ugcd} $B$O(B GCD $B$rJV$9(B.
                    466: $B$3$l$i$O(B, $BL)$J0lJQ?tB?9`<0$KBP$9$k9bB.2=$r?^$C$?$b$N$G$"$k(B.
                    467: @code{urembymul} $B$O(B, @var{p2} $B$K$h$k>jM>7W;;$r(B, @var{p2} $B$N(B
                    468: $BQQ5i?t$H$7$F$N5U857W;;$*$h$S(B, $B>h;;(B 2 $B2s$KCV$-49$($?$b$N$G(B,
                    469: $B<!?t$,Bg$-$$>l9g$KM-8z$G$"$k(B.
1.2     ! noro      470: @item
        !           471: @code{urembymul_precomp} $B$O(B, $B8GDj$5$l$?B?9`<0$K$h$k>jM>(B
1.1       noro      472: $B7W;;$rB??t9T$&>l9g$J$I$K8z2L$rH/4x$9$k(B.
1.2     ! noro      473: $BBh(B 3 $B0z?t$O(B, $B$"$i$+$8$a(B @code{ureverse_inv_as_power_series()} $B$K(B
        !           474: $B$h$j7W;;$7$F$*$/(B.
        !           475: \E
        !           476: \BEG
        !           477: @item
        !           478: For univariate polynomials @var{p1} and @var{p2},
        !           479: there exist polynomials @var{q} and @var{r} such that
        !           480: @var{p1=q*p2+r} and the degree of @var{r} is less than that of @var{p2}.
        !           481: Then @code{udiv} returns @var{q}, @code{urem} and @code{urembymul} return
        !           482: @var{r}. @code{ugcd} returns the polynomial GCD of @var{p1} and @var{p2}.
        !           483: These functions are specially tuned up for dense univariate polynomials.
        !           484: In @code{urembymul} the division by @var{p2} is replaced with
        !           485: the inverse computation of @var{p2} as a power series and
        !           486: two polynomial multiplications. It speeds up the computation
        !           487: when the degrees of inputs are large.
        !           488: @item
        !           489: @code{urembymul_precomp} is efficient when one repeats divisions
        !           490: by a fixed polynomial.
        !           491: One has to compute the third argument by @code{ureverse_inv_as_power_series()}.
        !           492: \E
1.1       noro      493: @end itemize
                    494:
                    495: @example
                    496: [177] setmod_ff(2^160-47);
                    497: 1461501637330902918203684832716283019655932542929
                    498: [178] A=randpoly_ff(200,x)$
                    499: [179] B=randpoly_ff(101,x)$
                    500: [180] cputime(1)$
                    501: 0sec(1.597e-05sec)
                    502: [181] srem(A,B)$
                    503: 0.15sec + gc : 0.15sec(0.3035sec)
                    504: [182] urem(A,B)$
                    505: 0.11sec + gc : 0.12sec(0.2347sec)
                    506: [183] urembymul(A,B)$
                    507: 0.08sec + gc : 0.09sec(0.1651sec)
                    508: [184] R=ureverse_inv_as_power_series(B,101)$
                    509: 0.04sec + gc : 0.03sec(0.063sec)
                    510: [185] urembymul_precomp(A,B,R)$
                    511: 0.03sec(0.02501sec)
                    512: @end example
                    513:
                    514: @table @t
1.2     ! noro      515: \JP @item $B;2>H(B
        !           516: \EG @item References
1.1       noro      517: @fref{uinv_as_power_series ureverse_inv_as_power_series}.
                    518: @end table