一変数多項式の演算
=========

Univariate polynomials
======================

umul, umul_ff, usquare, usquare_ff, utmul, utmul_ff
---------------------------------------------------

umul(P1,P2)
umul_ff(P1,P2)
     :: 一変数多項式の高速乗算

     :: Fast multiplication of univariate polynomials

usquare(P1)
usquare_ff(P1)
     :: 一変数多項式の高速 2 乗算

     :: Fast squaring of a univariate polynomial

utmul(P1,P2,D)
utmul_ff(P1,P2,D)
     :: 一変数多項式の高速乗算 (打ち切り次数指定)

     :: Fast multiplication of univariate polynomials with truncation

return
     一変数多項式

     univariate polynomial

p1 p2
     一変数多項式

     univariate polynomial

d
     非負整数

     non-negative integer

  * 一変数多項式の乗算を, 次数に応じて決まるアルゴリズムを用いて高速に行う.

  * umul(), usquare(), utmul() は係数を整数と見なして, 整数係数の多項式として積を求める. 係数が有限体 GF(p) の元の場合には, 係数は 0 以上 p 未満の整数と見なされる.

  * umul_ff(), usquare_ff(), utmul_ff() は, 係数を有限体の元と見なして, 有限体上の多項式として積を求める. ただし, 引数の係数が整数の場合, 整数係数の多項式を返す場合もあるので, これらを呼び出した結果が有限体係数であることを保証するためにはあらかじめ simp_ff() で係数を有限体の元に変換しておくとよい.

  * umul_ff(), usquare_ff(), utmul_ff() は, GF(2^n) 係数の多項式を引数に取れない.

  * umul(), umul_ff() の結果は P1, P2 の積, usquare(), usquare_ff() の結果は P1 の 2 乗, utmul(), utmul_ff() の結果は P1, P2 の積の, D 次以下の部分となる.

  * いずれも, set_upkara() (utmul, utmul_ff については set_uptkara()) で返される値以下の次数に対しては通常の筆算形式の方法, set_upfft() で返される値以下の次数に対しては Karatsuba 法, それ以上では FFTおよび中国剰余定理が用いられる. すなわち, 整数に対する FFT ではなく, 十分多くの 1 ワード以内の法 MI を用意し, P1, P2 の係数を MI で割った余りとしたものの積を, FFT で計算し, 最後に中国剰余定理で合成する. その際, 有限体版の関数においては, 最後に基礎体を表す法で各係数の剰余を計算するが, ここでは Shoup によるトリック [Shoup] を用いて高速化してある.

  * These functions compute products of univariate polynomials by selecting an appropriate algorithm depending on the degrees of inputs.

  * umul(), usquare(), utmul() compute products over the integers. Coefficients in GF(p) are regarded as non-negative integers less than p.

  * umul_ff(), usquare_ff(), utmul_ff() compute products over a finite field. However, if some of the coefficients of the inputs are integral, the result may be an integral polynomial. So if one wants to assure that the result is a polynomial over the finite field, apply simp_ff() to the inputs.

  * umul_ff(), usquare_ff(), utmul_ff() cannot take polynomials over GF(2^n) as their inputs.

  * umul(), umul_ff() produce P1*P2. usquare(), usquare_ff() produce P1^2. utmul(), utmul_ff() produce P1*P2 MOD V^(D+1), where V is the variable of P1, P2.

  * If the degrees of the inputs are less than or equal to the value returned by set_upkara() (set_uptkara() for utmul, utmul_ff), usual pencil and paper method is used. If the degrees of the inputs are less than or equall to the value returned by set_upfft(), Karatsuba algorithm is used. If the degrees of the inputs exceed it, a combination of FFT and Chinese remainder theorem is used. First of all sufficiently many primes MI within 1 machine word are prepared. Then P1*P2 MOD MI is computed by FFT for each MI. Finally they are combined by Chinese remainder theorem. The functions over finite fields use an improvement by V. Shoup [Shoup].

     [176] load("fff")$
     [177] cputime(1)$
     0sec(1.407e-05sec)
     [178] setmod_ff(2^160-47);
     1461501637330902918203684832716283019655932542929
     0sec(0.00028sec)
     [179] A=randpoly_ff(100,x)$
     0sec(0.001422sec)
     [180] B=randpoly_ff(100,x)$
     0sec(0.00107sec)
     [181] for(I=0;I<100;I++)A*B;
     7.77sec + gc : 8.38sec(16.15sec)
     [182] for(I=0;I<100;I++)umul(A,B);
     2.24sec + gc : 1.52sec(3.767sec)
     [183] for(I=0;I<100;I++)umul_ff(A,B);
     1.42sec + gc : 0.24sec(1.653sec)
     [184] for(I=0;I<100;I++)usquare_ff(A);
     1.08sec + gc : 0.21sec(1.297sec)
     [185] for(I=0;I<100;I++)utmul_ff(A,B,100);
     1.2sec + gc : 0.17sec(1.366sec)
     [186] deg(utmul_ff(A,B,100),x);
     100

参照

References
     set_upkara set_uptkara set_upfft, kmul ksquare ktmul.

kmul, ksquare, ktmul
--------------------

kmul(P1,P2)
     :: 一変数多項式の高速乗算

     :: Fast multiplication of univariate polynomials

ksquare(P1)
     :: 一変数多項式の高速 2 乗算

     :: Fast squaring of a univariate polynomial

ktmul(P1,P2,D)
     :: 一変数多項式の高速乗算 (打ち切り次数指定)

     :: Fast multiplication of univariate polynomials with truncation

return
     一変数多項式

     univariate polynomial

p1 p2
     一変数多項式

     univariate polynomial

d
     非負整数

     non-negative integer

  * 一変数多項式の乗算を Karatsuba 法で行う.

  * 基本的には umul と同様だが, 次数が大きくなっても FFT を用いた高速化は行わない.

  * GF(2^n) 係数の多項式にも用いることができる.

     These functions compute products of univariate polynomials by Karatsuba algorithm.

  * These functions do not apply FFT for large degree inputs.

  * These functions can compute products over GF(2^n).

     [0] load("code/fff");
     1
     [34] setmod_ff(defpoly_mod2(160));
     x^160+x^5+x^3+x^2+1
     [35] A=randpoly_ff(100,x)$
     [36] B=randpoly_ff(100,x)$
     [37] umul(A,B)$
     umul : invalid argument
     return to toplevel
     [37] kmul(A,B)$

set_upkara, set_uptkara, set_upfft
----------------------------------

set_upkara([THRESHOLD])
set_uptkara([THRESHOLD])
set_upfft([THRESHOLD])
     :: 1 変数多項式の積演算における N^2 , Karatsuba, FFT アルゴリズムの切替えの閾値

     :: Set thresholds in the selection of an algorithm from N^2, Karatsuba, FFT algorithms for univariate polynomial multiplication.

return
     設定されている値

     value currently set

threshold
     非負整数

     non-negative integer

  * いずれも, 一変数多項式の積の計算における, アルゴリズム切替えの閾値を設定する.

  * 一変数多項式の積は, 次数 N が小さい範囲では通常の N^2 アルゴリズム, 中程度の場合 Karatsuba アルゴリズム, 大きい場合には FFT アルゴリズムで計算される. この切替えの次数を設定する.

  * 詳細は, それぞれの積関数の項を参照のこと.

  * These functions set thresholds in the selection of an algorithm from N^2, Karatsuba, FFT algorithms for univariate polynomial multiplication.

  * Products of univariate polynomials are computed by N^2, Karatsuba, FFT algorithms. The algorithm selection is done according to the degrees of input polynomials and the thresholds.

  * See the description of each function for details.

参照

References
     kmul ksquare ktmul, umul umul_ff usquare usquare_ff utmul utmul_ff.

utrunc, udecomp, ureverse
-------------------------

utrunc(P,D)
udecomp(P,D)
ureverse(P)
     :: 多項式に対する操作

     :: Operations on polynomials

return
     一変数多項式あるいは一変数多項式のリスト

     univariate polynomial or list of univariate polynomials

p
     一変数多項式

     univariate polynomial

d
     非負整数

     non-negative integer

  * P の変数を x とする. このとき P = P1+x^(d+1)P2 (P1 の次数は D 以下) と分解できる. utrunc() は P1 を返し, udecomp() は [P1,P2] を返す.

  * P の次数を E とし, I 次の係数を P[I] とすれば, ureverse() は P[E]+P[E-1]x+... を返す.

  * Let X be the variable of P. Then P can be decomposed as P = P1+x^(d+1)P2, where the degree of P1 is less than or equal to D. Under the decomposition, utrunc() returns P1 and  udecomp() returns [P1,P2].

  * Let E be the degree of P and P[I] the coefficient of P at degree I. Then ureverse() returns P[E]+P[E-1]x+....

     [132] utrunc((x+1)^10,5);
     252*x^5+210*x^4+120*x^3+45*x^2+10*x+1
     [133] udecomp((x+1)^10,5);
     [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]
     [134] ureverse(3*x^3+x^2+2*x);
     2*x^2+x+3

参照

References
     udiv urem urembymul urembymul_precomp ugcd.

uinv_as_power_series, ureverse_inv_as_power_series
--------------------------------------------------

uinv_as_power_series(P,D)
ureverse_inv_as_power_series(P,D)
     :: 多項式を冪級数とみて, 逆元計算

     :: Computes the truncated inverse as a power series.

return
     一変数多項式

     univariate polynomial

p
     一変数多項式

     univariate polynomial

d
     非負整数

     non-negative integer

  * uinv_as_power_series(P,D) は, 定数項が 0 でない多項式 P に対し, PR-1 の最低次数が D+1 以上になるような 高々 D 次の多項式 R を求める.

  * ureverse_inv_as_power_series(P,D) は P の次数を E とするとき, P1=ureverse(P,E) に対して uinv_as_power_series(P1,D) を計算する.

  * rembymul_precomp() の引数として用いる場合, ureverse_inv_as_power_series() の結果をそのまま用いることができる.

  * For a polynomial P with a non zero constant term, uinv_as_power_series(P,D) computes a polynomial R whose degree is at most D such that P*R = 1 MOD X^(D+1), where X is the variable of P.

  * Let E be the degree of P. ureverse_inv_as_power_series(P,D) computes uinv_as_power_series(P1,D) for P1=ureverse(P,E).

  * The output of ureverse_inv_as_power_series() can be used as the input of rembymul_precomp().

     [123] A=(x+1)^5;
     x^5+5*x^4+10*x^3+10*x^2+5*x+1
     [124] uinv_as_power_series(A,5);
     -126*x^5+70*x^4-35*x^3+15*x^2-5*x+1
     [126] A*R;
     -126*x^10-560*x^9-945*x^8-720*x^7-210*x^6+1
     [127] A=x^10+x^9;
     x^10+x^9
     [128] R=ureverse_inv_as_power_series(A,5);
     -x^5+x^4-x^3+x^2-x+1
     [129] ureverse(A)*R;
     -x^6+1

参照

References
     utrunc udecomp ureverse, udiv urem urembymul urembymul_precomp ugcd.

udiv, urem, urembymul, urembymul_precomp, ugcd
----------------------------------------------

udiv(P1,P2)

urem(P1,P2)

urembymul(P1,P2)

urembymul_precomp(P1,P2,INV)

ugcd(P1,P2)
     :: 一変数多項式の除算, GCD

     :: Division and GCD for univariate polynomials.

return
     一変数多項式

     univariate polynomial

p1,p2,inv
     一変数多項式

     univariate polynomial

  * 一変数多項式 P1, P2 に対し, udiv は商, urem, urembymul は剰余, ugcd は GCD を返す. これらは, 密な一変数多項式に対する高速化を図ったものである. urembymul は, P2 による剰余計算を, P2 の冪級数としての逆元計算および, 乗算 2 回に置き換えたもので, 次数が大きい場合に有効である.

  * urembymul_precomp は, 固定された多項式による剰余計算を多数行う場合などに効果を発揮する. 第 3 引数は, あらかじめ ureverse_inv_as_power_series() により計算しておく.

  * For univariate polynomials P1 and P2, there exist polynomials Q and R such that P1=Q*P2+R and the degree of R is less than that of P2. Then udiv returns Q, urem and urembymul return R. ugcd returns the polynomial GCD of P1 and P2. These functions are specially tuned up for dense univariate polynomials. In urembymul the division by P2 is replaced with the inverse computation of P2 as a power series and two polynomial multiplications. It speeds up the computation when the degrees of inputs are large.

  * urembymul_precomp is efficient when one repeats divisions by a fixed polynomial. One has to compute the third argument by ureverse_inv_as_power_series().

     [177] setmod_ff(2^160-47);
     1461501637330902918203684832716283019655932542929
     [178] A=randpoly_ff(200,x)$
     [179] B=randpoly_ff(101,x)$
     [180] cputime(1)$
     0sec(1.597e-05sec)
     [181] srem(A,B)$
     0.15sec + gc : 0.15sec(0.3035sec)
     [182] urem(A,B)$
     0.11sec + gc : 0.12sec(0.2347sec)
     [183] urembymul(A,B)$
     0.08sec + gc : 0.09sec(0.1651sec)
     [184] R=ureverse_inv_as_power_series(B,101)$
     0.04sec + gc : 0.03sec(0.063sec)
     [185] urembymul_precomp(A,B,R)$
     0.03sec(0.02501sec)

参照

References
     uinv_as_power_series ureverse_inv_as_power_series.