数理解析研究所講究録 1456 巻 2005 年 133-143

133

高速留数計算アルゴリズム
庄司 卓夢
TAKUMU SHOJI

新潟大学自然科学研究科
GRADUATE SCHOOL OF SCIENCE AND TECHNOLOGY, NIIGATA UNIVERSITY

田島慎一
SHINICHI TAJIMA

新潟大学工学部情報工学科
FACULTY OF ENGINEERING, NIIGATA UNIVERSITY
Abstract
留数は古典的な対象であるが, 計算機代数の分野ではその計算法についてそれほど注目されていなかっ加群の理論た. 本研究では, 代数解析の観点から, 有理関数が内部に隠しもつ数学的構造を明らかにし,を用いて効率的な留数計算アルゴリズムを導出する. そして, そのアルゴリズムを数式処理システムに実装し, 性能を評価する.
$\mathrm{D}$

1

はじめに
留数

${\rm Res}_{\alpha}( \frac{h}{f^{f}})=\frac{1}{2\pi \mathrm{i}}\oint\frac{h}{f^{\ell}}dx$を求める問題を$\text{考}\grave{\mathrm{x}}$る.

ただし, $f_{)}h\in K[x],$ $K=\mathbb{Q},$$\alpha\in Z=\{x\in \mathbb{C}|f(x)=0\}$とする.

Fact ([2, 4]) 有

i\partial Y‘‘^k める代数的局所コホモロジ$\mathrm{I}\mathrm{E}^{\mathrm{P}}\ovalbox{\tt\small REJECT}$数$\frac{1}{f^{\ell}}$$-^{\iota}\ovalbox{\tt\small REJECT}$$[ \frac{1}{f^{f}}]\in H_{[Z14}^{1}(K[x])$

$f$

は既約,

$\ell\in \mathrm{N}$,は, $\ell-1$ 階の微分作用

素 $T$ を用いて次のように表せる.
$[ \frac{1}{f^{\ell}}]=T[\frac{f^{J}}{f}1\rfloor,$

従って, $T$ の形式随伴を$T^{*}$$t_{i}\in K[x]/\langle f\rangle$$T= \sum_{i=0}^{l-1}(-\frac{d}{dx})^{l-1-i}t_{i},$

.

とおくと,

$\oint\frac{h}{f^{\ell}}dx=\oint h[\frac{1}{f^{\ell}}]dx=\oint hT[\frac{f’}{f}]dx=\oint hT(\frac{f’}{f})dx=\oint T^{*}h(\frac{f^{\mathit{1}}}{f})dx$となり, 次式が導かれる.

Theorem 11${\rm Res}_{\alpha}( \frac{h}{f^{p}})=(T^{*}h)(\alpha)$.

留数はこの式で exact に求まる.
本稿では, まず次節でこの $T$ の計算方法について解説する. 第 3 節では, 一般的な有理関数の場合にまで理論を拡張する. 第 4 節では, 留数計算アルゴリズムを具体的に与える. 第 5 節では, 具体例を紹介する. 第
6 節では, 計算機実験によって各アルゴリズムの計算効率を比較し, 性能を評価する.

134
2

微分作用素 $T$ の計算方法$T$を求める方法として, 次の 3 通りの方法が考えられる.

方法 1 と方法 2 については文献 [4] に概略が述べてある. 本稿は, 方法 3 を解説していく.

Fact ([1, 3, 4])$D_{X}=K_{\mathrm{L}}[x,.

.
.
.

\frac{d}{dx}]_{2}\sigma=[\frac{1}{f^{\ell}}]$$\mathrm{A}\mathrm{n}\mathrm{n}_{D\chi}(\sigma)=D_{X}\langle P_{j}$とおき高分作用素 $P$ を $P=f \frac{d}{dx}+\ell f’$ で定めると次力減り立つ,f 勺.

左 $D_{X}$ 加群 $M,$ $N$ を,$M=D_{X}/\mathrm{A}\mathrm{n}\mathrm{n}_{D_{X}}(\sigma),$$\dim_{K}\mathrm{H}\mathrm{o}\mathrm{m}_{D_{X}}(M, N)=\deg f$$\mathrm{H}\mathrm{o}\mathrm{m}_{D_{X}}(M, N)$は, 右加群の構造をもつ.

文献 [1] pp.52-53 によると, $T$ の各右係数$B_{i}=(- \frac{d}{dx})^{i}(f’)^{i}$$t_{i}$

は, to と $(f’)^{-1}$ のべきを共通因子としてもつ. それに注目す$\mathrm{H}\mathrm{o}\mathrm{m}_{D_{X}}(Dx/D_{X}\langle f^{\ell}\rangle, N)$$B= \sum_{i=0}^{\ell-1}B_{l-1-i^{\mathrm{C}}i},$なる$B\in \mathrm{H}\mathrm{o}\mathrm{m}_{D_{X}}(M, N)$

Lemma 21 各

$c_{i}$

は$B_{0},$ $B_{1},$$c_{i}\in K[x]/\{f\rangle,$$\ldots,$$B_{\ell-1}$で生成される. そこで,

$c_{0}=1$を考える.

は次の漸化式で求まる. $i=1,2,$$c_{0}=1,$で定めると次が成り立つ.

.

$K[x]/\langle f\rangle$

れば, 計算を効率化できる.
とおくと,$N=D_{X}/D_{X}\langle f\rangle$$\ldots,$$\ell-1$に対して,$c_{i}=- \frac{1}{i}\sum_{j=1}^{i}\{\prod_{k=1}^{j}(\ell-1-i+k)\}\frac{\langle lj+i-j)}{(j+1)!}f^{(j+1)}(f’)^{j-1}c_{i-j}$.

証明: PB—P \Sigma \el i 二 01 $B_{\ell-1-i}c_{\dot{x}}= \sum_{i=0}^{\ell-1}B_{l-1-i}w_{\ell-1-i}$ とおく. ここで,PB そ-l-i$=$$(-f)(- \frac{d}{dx}\rangle B_{\ell-1-i}+\ell f^{t}B_{l--1-i}$$=$$\sum_{k=0}^{l-1-i}B\ell-1-\mathrm{i}-k\{(\ell k-\mathrm{i})\frac{(\ell-1-\mathrm{i})!}{(\ell-1-\mathrm{i}-k)!(k+1\rangle!}\}f^{(k+1)}(f’)^{k}$を用いて $w_{\ell-1-i}$ を求めると,$w_{l-1-i}= \sum_{j=0}^{i}(\ell j+\mathrm{i}-j)\frac{(\ell-1-i+j)!}{\langle\ell-1-i)!(j\neg 11_{-})!}.f^{(j+1)}(f’)^{j}c_{i-j}$となる. $PB\in D_{X}f$ より各$i$に対し, $w_{l-1-i}\equiv 0$$(\mathrm{m}\mathrm{o}\mathrm{d} f)$が成り立つので,$ic_{i}+ \sum_{j=1}^{\mathrm{t}}(\ell j+i-j)\frac{(\ell-1-i+j)!}{(\ell-1-\mathrm{i})!(j+1)!}f^{(j+1)}(f’)^{j-1}\mathrm{q}_{-j}.=0$が得られる.

$\mathrm{I}$135
Lemma 22 $T=Bu$ となる$u\in K[x]/\langle f\rangle$

証明: $T=Bu$ とおく. $PT=PBu\equiv 0$

は, 条件 $(\ell-1)!(f’)^{2l-1}u=1$ で与えられる.
が成り立つので, 代数的局所コホモロジー類 $\tau=T[_{f}^{L’}]$$(\mathrm{m}\mathrm{o}\mathrm{d} D_{X}f)$は微分方程式系 $P\tau=0,$ $f^{\ell}\tau=0$ を満たす.
の両辺に $f’f^{l-1}$ をかけ, $f^{\ell-1}B\equiv(\ell-1)!(f’)^{2\ell-2}$
ここで,$[ \frac{1}{f^{\ell}}]=T[_{f}^{L’}]$$(\mathrm{m}\mathrm{o}\mathrm{d} D_{X}f)$

を用いて計算していくと,$\langle\ell-1)!(f’)^{2\ell-1}u\equiv 1$$(\mathrm{m}\mathrm{o}\mathrm{d} f)$が得られる. 従って, $f’(f^{l-1})\tau=[_{f}^{L’}]$ が成り立つ. $P\tau=0,$ $f^{\ell}\tau=0$ の解で, $f’(f^{l-1})\tau=[_{f}^{L’}]$ を満たすもが証明された]のはだけだから,$\tau=\sigma$$\sigma$Lemma 23 $T^{*}h=u(B^{*}h)$ が成り立つ.
証明: T*=(Bu 戸 $=u^{*}B^{*}=uB^{*}\mathrm{I}$

従って, Theorem 1.1 は次のように変形できる.

Theorem 2.4${\rm Res}_{\alpha}( \frac{h}{f^{\ell}})=(u(B^{*}h))(\alpha)$

3

.

一般化
$-\mathrm{k}^{\prime \mathrm{u}}\text{的}\backslash$なg関数

合を考える. ただし,$f_{1},$$\frac{h}{j_{1}^{l_{1}}\cdots f_{m}^{\ell_{\tau n}}}\text{の}\partial^{\mathrm{B}}$

まず, $Z=\{x\in \mathbb{C}|f1(x)\cdots f_{m}(x)=0\}$ に台$\text{を}\mathrm{t}_{3^{-}}^{\pm}\overline{\backslash }$$\ldots,$$f_{m}\in K[x]$は既約とする.

つ代数的局所コホモロジー類

る, $p=-f_{1}f_{2}\cdots f_{m},$ $q=\ell_{1}f_{1}’f_{2}\cdots f_{m}+\ell_{2}f_{1}f_{2}’\cdots f_{m}+\cdots+l_{m}f_{1}f_{2}\cdots f_{m}’$$P=p(- \frac{d}{dx})+q$

次に,$\sigma$で定めると,$\sigma$の満たす微分方程式系 $P\sigma=0,$$\sigma=[_{f_{1}^{1}\cdots f_{\mathrm{m}}^{l_{rn}}}^{1}\propto]$

を考えを用いて, 微分作用素 $P$ を$(f_{1}^{\ell_{1}}\cdots f_{m^{m}}^{\ell})\sigma=0$を得る,の直和分解を $\sigma=\sigma f_{1}+\cdots+\sigma f_{m},$ $\sigma f_{k}\in H_{[Z_{f_{k}}]}^{1}(K[x]),$ $Zfk=\{x|f_{k}(x)=0\}$ とおく.

–

般に, 微分作用素は local operator であるので, $P\sigma=0$ より $P\sigma fk=0$ が従う. また, $Dx$ 加群 $M=$
なる Tf、を求めることができる.
は各点で simple なので,$\sigma_{fk}=T_{fk}\acute{\mathrm{L}}^{\frac{f_{k}’}{f_{k}}]}$$D_{X}/D_{X}P+D_{X}\langle f_{1}^{\ell_{\iota}}\cdots f_{m^{m}}^{l}\rangle$(有$\text{理}\ovalbox{\tt\small REJECT} \mathscr{L}\mathrm{i}$数$\mathrm{I}_{1}^{---}f_{1}-\cdot\cdot\overline{f_{\mathrm{m}}^{p_{m}}}h$

今, $f=f_{k},$$\ell=$

前節と同様にLemma 31 各

乏

の部分分数

$k$

$\theta_{\grave{\mathrm{J}}}\text{解}$$\not\in\ovalbox{\tt\small REJECT}\not\equiv$

成できる), $a=f_{1}\cdots f_{k-1}f_{k+1}\cdots f_{m}$ とおく.

$B_{i}=(- \frac{d}{dx})^{i}(f’a)^{i}$$c_{i}$を求めずに直とおき, BJ=\Sigma i\ell 二 01Bl-l-i 果を考える.

は次の漸化式で求まる. $i=1,2,$$c_{0}.=1,$$\ldots,$$\ell-1$に対して,.

$c_{i}=- \frac{1}{i}\sum_{j=1}^{i}\{(^{\ell-i+j}j+1)p^{(j+1)}+(\begin{array}{ll}p-\mathrm{l}-i+ jj \end{array})q^{(j)} \}(f’a)^{j-1}c_{i-j}$

証明: Lemma 2.1 と同様, 1

Lemma 32

$g=f_{1}^{\ell_{1}}\cdots f_{k-1}^{l_{k-1}}f_{k+1}^{p_{\mathrm{k}+1}}\cdots f_{m^{m}}^{l}$

とおく. $Tf=Bfu$ となる $u\in K[x]/\langle f\rangle$ &よ,

条件 $(\ell-1)!(f’)^{2\ell-1}a^{\ell-1}gu=1$ で与えられる.
証明: Lemma 22 と同様. 塑1384

留数計算アルゴリズム
2 節での論述から,$;\mathrm{g}$\Phi 関$\text{数}\backslash \cdot\frac{h}{f^{l}}$に対して, 次の留数計算アルゴリズムを得る.

アルゴリズムの要点を簡単に述べる. 骨格は, Theorem 24 に基づいて設計され, $T$ の計算は Lemma 21,

22, 23 により効率化している.
で行えるため, 多項式の次数の増大を防ぎ, 逆元計算が利用
また, 各 step の計算は全て剰余体できる. この性質は, 高速化に強烈に効いてくる.
での計算に問題を帰着させると計算効率が上がる.
プログラムでは, できる限り$K[x]/\langle f\rangle$$\mathbb{Z}[x]$3 節での論述から, 一般的な有理関数に対して, 次の留数計算アルゴリズムを得る.

分母の各因子に対する留数計算は, 剰余体$K[x]/\langle f_{k}\rangle$

数分解されたデータをリストで渡すと stepO が楽になるで行うことができる, プログラムでは, 入力には因2各アルゴリズムに対する留数計算プログラムは次の通りである. 6 節でその性能を見ている.
$|$$\mathrm{A}1g$$\mathrm{A}1_{\mathrm{o}}\sigma$

$4.1$

$4.2$

$\overline{---}d^{\mathrm{t}}\mathfrak{M}$$|$$i \mathrm{g}\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT} \mathrm{g}\frac{h}{\ell}$$\emptyset \mathrm{J}^{\mathrm{i}}\ae.\ovalbox{\tt\small REJECT} 71\equiv-+\mathrm{p}\ovalbox{\tt\small REJECT}^{\mathrm{A}}$

$|$
$|$

$-\Re \mathfrak{W}$$7\subset \mathrm{I}$$p^{\backslash \backslash }$$\overline{7}\Delta$

residue$f_{\epsilon}\zeta k\Phi\ovalbox{\tt\small REJECT}.\ovalbox{\tt\small REJECT}.\Re \mathit{0})\mathrm{r}_{\ae^{\mathrm{Z}}\ovalbox{\tt\small REJECT}_{\mathrm{D}}^{-}}\overline{=}+\ovalbox{\tt\small REJECT}$$\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{u}\mathrm{e}_{-\epsilon}\sigma_{1}$

a

137
5

具体例

Example 51 $f=x^{3}-x-1,$ $\ell=3,$ $h=1$ の時, 次[$\frac{h}{f^{\ell}}\rfloor 1=L[\frac{f’}{f}.],$$\text{の^{}\prime}\dagger^{\mathrm{d}}\phi^{1}\mathrm{f}\mathrm{i}^{\mathrm{L}}\dagger T\mathrm{f}\mathrm{f}\mathrm{l}\text{素}L\text{を求めよ}$$L= \sum_{i=0}^{l-1}(-\frac{d}{dx})^{\ell-1-}$.

“果[156] laurent 1 $(\mathrm{x}^{-}3-\mathrm{x}-1,3,1)$ ;kenzan : ok$[9/529*\mathrm{x}^{\wedge}2-27/1058*\mathrm{x}+11/1058,$ $-81/529*\mathrm{x}^{-}2-9/529*\mathrm{x}+135/529,$ $-4905/12167*\mathrm{x}^{\wedge}2+4563/12$$167*\mathrm{x}+3270/12167]$[157] laurent2$\zeta \mathrm{x}^{\wedge}3-\mathrm{x}-1,3,1$);$[24334, [414*\mathrm{x}^{\wedge}2-621*\mathrm{x}+253,-3726*\mathrm{x}^{\wedge}2-414*\mathrm{x}+6210,-9810*\mathrm{x}^{\sim}2+9126*\mathrm{x}+6540]]$[158] snoether$(\mathrm{x}^{\wedge}3-\mathrm{x}-1,3,1)$;$[24334, [414*\mathrm{x}^{\wedge}2-621*\mathrm{x}+258,-3726*\mathrm{x}^{\wedge}2-414*\mathrm{x}+6210,-9810*\mathrm{x}^{\wedge}2+9126*\mathrm{x}+6540]]$

Exanple5.2 関数 $R(x)= \frac{1}{(x^{4}-3x^{3}+2x^{2}+x-7)^{3}}$ の留数を求めよ.
微分作用素 $B=B_{2}c_{0}+B_{1}c_{1}+B_{0}c_{2}$ を考え, Alg 41 に従って留数を求めていく.

Input $f=x^{4}-3x^{3}+2x^{2}+x-7,$ $\ell=3,$ $h=1$
Stepl $c0,$ $c1,$$c2$の計算 (Lemma 21)$c_{0}=1,$ $c_{1}=-36x^{2}+54x-12,$

Step2$c_{2}=330x^{2}-720x+2418$$B^{*}h= \sum_{i=0}^{\min\{\ell-1,\deg h\}}(f’)^{\overline{l}}c_{l-1-x}h^{(i)}$の計算$B^{*}h=(f’)^{0}c_{2}h^{(0)}=330x^{2}-720x+2418$$\underline{\mathrm{S}\mathrm{t}\mathrm{e}\mathrm{p}3}Q=(f’)^{-1}$の計算$(f’)^{-1}=- \frac{137}{33090}x^{3}+\frac{397}{33090}x^{2}+\frac{73}{2206}x-\frac{556}{16545}$$\underline{\mathrm{S}\mathrm{t}\mathrm{e}\mathrm{p}4}u=\frac{1}{(l-1\rangle!}Q^{2\ell-1}$の計算

分数計算はできるだけ避けたいので, 整数係数化処理を施す.
$u= \frac{1}{289854661032000}(-27289583x^{3}+86271673x^{2}+50233785x-132913868)$

Step5 ${\rm Res}=u(B^{*}.h)$ の計算${\rm Res}= \frac{1}{289864661032000}$$(-30209148384x^{3}+95377636704x^{2}+133022875680x-173675480064)$

138[109] residue$(\mathrm{x}4\wedge-3*\mathrm{x}^{\wedge}3+2*\mathrm{x}^{\sim}2+\mathrm{x}-7,3,1)$;$[289854661032000,-30209148384*\mathrm{x}^{\wedge}3+95377636704*\mathrm{x}^{\wedge}2+133022875680*\mathrm{x}-173675480064]$

とおくと, 留数は次のようになる.

$\alpha\in\{x|f(x)=0\}$${\rm Res}_{\alpha}(R)= \frac{\mathrm{s}^{1}}{18\cdot 5\cdot 1103}$

Example 53 関数$(-314678629\alpha^{3}+993517049\alpha^{2}+1385654955\alpha-1809119584)$$R(x)= \frac{x^{3}+1}{x^{18}-2x^{14}+x^{10}-x^{8}+2x^{4}-1}$の留数を求めよ.

簡約化すると, $R= \frac{44\underline{9}-22x^{2}-x+1-}{(x+x+x+x+1)(x-x+xx+1)(x+1)(x+1)(x1)}$ となる, Alg 42 によって, 部分分
数分解を行わずに留数を求めることができる.
[1181 residue-g$(\mathrm{x}^{\wedge}3+1,\mathrm{x}^{\sim}18-2*\mathrm{x}^{\wedge}14+\mathrm{x}^{\wedge}10-\mathrm{x}^{\sim}8+2*\mathrm{x}^{\wedge}4-1)$$\mathrm{x}^{\wedge}4+\mathrm{x}^{\wedge}3+\mathrm{x}^{\wedge}2+\mathrm{x}+1$:$[50, -2*\mathrm{x}^{\wedge}2-\mathrm{x}-2]$$\mathrm{x}^{\wedge}4-\mathrm{x}^{\wedge}3+\mathrm{x}^{\wedge}2-\mathrm{x}+1$:$[50, -2*\mathrm{x}^{\wedge}3+4*\mathrm{x}^{\wedge}2-\mathrm{x}-2]$$\mathrm{x}^{-}2+1$

:

:

$[$

$\mathrm{x}+1$

x-l :

;

$[128, 32*\mathrm{x}+20]$3200 -390

$]$

$,$

$[64000,13400]$$\alpha\in\{x|x^{4}+x^{3}+x^{2}+x+1=0\},$ $\beta\in\{x|x^{4}-x^{3}+x^{2}-x[perp]_{l}1=0\},$ $\gamma\in\{x|x^{2}+1=0\}$

とおくと, 乱数は次のようになる.
${\rm Res}_{\alpha}(R)=- \frac{1}{25}\alpha^{2}-\frac{1}{50}\alpha-\frac{1}{25},$ ${\rm Res}_{\beta}(R)=- \frac{1}{25}\beta^{3}+\frac{2}{25}\beta^{2}$${\rm Res}_{-1}(R)=- \frac{39}{320},$

6

一$\frac{1}{50}\beta$$- \frac{1}{25},$${\rm Res}_{\gamma}(R)= \frac{1}{4}\gamma+\frac{5}{32}$,${\rm Res}_{1}(R)= \frac{67}{s2- 0}$

計算機実験
CPU 時間 秒) を計測して, アルゴリズムの性能評価, 計算効率の比較を行う.
$\langle$

実験環境
CPU; Pentium4$2.6\mathrm{G}\mathrm{H}\mathrm{z}$, RAM: IGB,

, Software:$\mathrm{O}\mathrm{S}:\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{s}\mathrm{X}\mathrm{P}$$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$実験で使う既約多項式$fi=x+1,$ $f_{2}=x^{2}-3x+5,$ $f_{3}=x^{3}-x-1$ , $f_{4}=x^{4}+1,$ $f_{5}=x^{5}+3x^{4}+1,$ $f_{6}=x^{6}+5x^{4}+x^{2}+3$ ,$f_{8}=x^{8}+5x^{5}-x^{4}-x^{2}+1,$ $f10=x^{10}+x^{7}-x^{5}+3x^{4}+2x+1,$ $f_{25}=x^{25}+x^{12}+1,$ $f\mathrm{s}\mathrm{o}=x^{50}-4x^{11}+1$61

微分作用素の計算効率の比較

次のような微分作用素$L$を, 2 節で述べた 3 通りの方法で計算し, 計算効率を比較する.
$[ \frac{h}{f^{\ell}}]=L[\frac{f’}{f}],$$L= \sum_{i=0}^{\mathit{1}-1}(-\frac{d}{dx})^{\ell-1-\dot{\iota}}a_{i}$138snoether(2004) は, 文献 [1] pp.53-54 で述べてあるアルゴリズムである. それの Noether 作用素の構成方法を改良したものが snoether(2005) である.

62

有理関数

の脚数計算アルゴリズムの性能 ’ 価$—\overline{\mathrm{p}}\mp\backslash$$\frac{h}{f^{\ell}}$

留数計算プログラム residue の性能評価各 step ごとに計算時間を見る. 留数計算用に特化させた residue
は, snoether(2005) よりも高速であることが分かる.

63

有理関数

$\frac{1}{Den}$の部分分数分解の計算効率の比較. pfdl : 未定係数法 (線形代数). pfd2 : 拡張 Euclid 互除法. pfd3 : 微分方程式の理論を用いる (文献 [1] pp.55-56)

140
64

有理関数

$\frac{1}{Den}$の濡鼠計算アルゴリズムの性能評価

簡約計算が重いので, プログラムにはあらかじめ因数分解されたデータをリストで渡している.

. pfd3-res: 部分分数分解を$\mathrm{p}\mathrm{f}\mathrm{d}3$

で求め residue に渡す. residue.g :Alg 42(部分分数分解を行わない)

7

.
.
.

まとめ
留数計算の式を, 微分作用素を使って表現した.
有理関数の極における Laurent 展開の主要部の計算は, 微分方程式の理論で導出した漸化式で計算すると効率的に計算できる.

本稿で提案した素数計算アルゴリズムの特徴.

-exact な計算である.
-

-

-

剰余体

$K[x]/\langle f\rangle$

における四則演算のみで計算できる.

部分分数分解を行わずに直接計算できる.
高速である. (特に, 高い位数を持つ極における計算が速い)

参考文献[1] 加藤涼香, 田島慎一 : 有理関数のローラン展開アルゴリズムと代数的局所コホモロジー,
京都大学数理解析研究所講究録 1395 「Algebra-Design of Algorithms, Implementations and$\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{e}\mathrm{r}$Applications\rfloor (2004), 50-56.
[2] 田島慎一 : 代数的局所コホモロジー類のローラン展開と L.Ehrenpreis の Noether 作用素,
京都大学数理解析研究所講究録 1138 「数式処理における理論と応用の研究」 (2000), 87-95.
[3] 田島慎一 : 確定特異点型ホロノミック系の零次元代数的局所コホモロジー解,
京都大学数理解析研究所講究録 1336 「双曲形方程式と非正則度」 (2003), 121-132.

[4] 田島慎一 :Holonomic な定数係数線形偏微分方程式系と Grothendieck
京都大学数理解析研究所講究録「積分核の代数解析的研究」 掲載予定.
[5] 田島慎一 : 一変数留数計算アルゴリズムについて,
京都大学数理解析研究所講究録 「積分核の代数解析的研究」掲載予定$\mathrm{d}\mathrm{u}.\mathrm{a}$

lity,

141
付録プログラム
数式処理システムは($\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$$\mathrm{h}\mathrm{t}\mathrm{t}\mathrm{p}://\mathrm{w}\mathrm{w}\mathrm{w}.\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{h}$sci.kobe-u.

) を使用しました.

$\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}/$1. snoether$/*\mathrm{F}$:分母 (既約多項式},def snoether (F.
$\mathrm{X}=\mathrm{v}\mathrm{a}\mathrm{r}(\mathrm{F})$$\mathrm{M}=$($\mathrm{L}<\deg$$\mathrm{L},\mathrm{H}$)$\mathrm{L}$$\mathrm{K}=1$

;
(F.

)

$\mathrm{X})+1$$=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}$;$7\mathrm{L}:\deg(\mathrm{F},\mathrm{X})+1$$(\mathrm{L}, [1] )i^{\mathrm{f}}$$\mathrm{C}\mathrm{O}=\mathrm{n}\mathrm{e}\mathrm{l}\iota \mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}$$\mathrm{C}=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}(\mathrm{L},$for($\mathrm{M}$$[1]\}$or ($\mathrm{J}=1$$(\mathrm{I}=1;\mathrm{I}<\mathrm{I}4+1;\mathrm{I}+\dagger)\mathrm{D}\mathrm{F}[\mathrm{I}]=\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}(\mathrm{D}\mathrm{F}[\mathrm{I}-1],\mathrm{X})i$$\mathrm{D}\mathrm{F}\mathrm{P}\zeta \mathrm{I}]=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{D}\mathrm{F}\mathrm{P}[\mathrm{I}-1]*\mathrm{D}\mathrm{F}[1]\prime \mathrm{F})$$(\mathrm{I}=1;\mathrm{I}<\mathrm{L};\mathrm{I}++)$, [tl ) ; for ( I$\overline{-}1$;I$<\mathrm{M};\mathrm{I}++$);$\{\mathrm{K}*=\mathrm{I}\tau 1 ;\mathrm{C}\mathrm{O}[\mathrm{I}]=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{D}\mathrm{F}[\mathrm{I}+1]*\mathrm{D}\mathrm{F}\mathrm{P}[\mathrm{I}-1]/\mathrm{K}, \mathrm{F}) ; \}$;:;J<I+I&&J$\mathrm{C}1*=\mathrm{K}+\mathrm{J}$

or

or

;

$\{$

$(\mathrm{I}=1j\mathrm{I}<\mathrm{L};\mathrm{I}++)$$\mathrm{K}=\mathrm{L}-1-\mathrm{I}_{j}\mathrm{C}1=1$$\mathrm{f}$

$*/$

$\{$

$\mathrm{D}\mathrm{F}=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}(\mathrm{M}+1_{\mathrm{s}}\zeta \mathrm{F}]):\mathrm{f}$DFP:極の位数 (自然数), H:分子 (多項式)$<\mathrm{M};\mathrm{J}++$

)

$\{$

;

;

$\mathrm{C}[\mathrm{I}]+=\mathrm{C}1*\zeta \mathrm{L}*\mathrm{J}+\mathrm{I}-\mathrm{J})*\mathrm{C}\mathrm{O}[\mathrm{J}]*\mathrm{C}[\mathrm{I}-\mathrm{J}]$$\}$$\mathrm{C}$

[工]

$=$

-srem

$(\mathrm{C}[\mathrm{I}],\mathrm{F})/\mathrm{I}j$

$\}$

for
if(

$(\mathrm{I}=0;\mathrm{I}<\mathrm{L}j\mathrm{I}++)\mathrm{C}[\mathrm{I}]=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}\langle \mathrm{C}[\mathrm{I}]*\mathrm{D}\mathrm{F}\mathrm{P}[\mathrm{L}-1-\mathrm{I}], \mathrm{F}\rangle$$\tau \mathrm{y}\mathrm{p}\mathrm{e}(\mathrm{H})==\mathrm{I}||$$\mathrm{C}*=\mathrm{H}$

type

;

$(\mathrm{H}\}==0)$ $\{$;$\}\mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}\{$$\mathrm{X}$$\mathrm{N}=(\mathrm{L}<\deg(\mathrm{H}, \mathrm{X})+1)7\mathrm{L}:\deg(\mathrm{H},$$\mathrm{D}\mathrm{H}=\eta \mathrm{l}\mathrm{e}\mathrm{w}\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}(\mathrm{N}, [\mathrm{H}])$; or$\mathrm{f}$or J=l.
$\cdot$$\mathrm{f}$$\langle$;$\mathrm{K}=\mathrm{L}-1-\mathrm{I};\mathrm{C}1\overline{\sim}1$$\mathrm{J}<\mathrm{I}+1\ \ \mathrm{J}<\mathrm{N};\mathrm{J}++$$.\mathrm{C}1*=\mathrm{K}+\mathrm{J}$[ 工]$=\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}(\mathrm{D}\mathrm{H}[\mathrm{I}-13.\mathrm{X})/\mathrm{I};\mathrm{D}\mathrm{H}=\mathrm{m}\mathrm{a}\mathrm{p}$$\{$$\langle \mathrm{I}=1;\mathrm{I}<\mathrm{L};\mathrm{I}++\rangle$$1l=\mathrm{C}[\mathrm{I}]*\mathrm{D}\mathrm{H}[0]$$\mathrm{D}\mathrm{H}$;$\mathrm{L}\mathrm{C}=\mathrm{n}\mathrm{e}\mathrm{b}\mathfrak{l}\mathrm{V}\mathrm{e}\mathrm{c}\mathrm{t}(\mathrm{L}, [\mathrm{C}[\mathrm{O}1*\mathrm{D}\mathrm{H}[0]])$for} $+1$ ;$(\mathrm{I}=1j\mathrm{I}<\mathrm{N};\mathrm{I}++)$

)

;

$\{$

;

$\mathrm{U}+=\mathrm{C}1*\mathrm{C}[\mathrm{I}-\mathrm{J}]*\mathrm{D}\mathrm{H}[\mathrm{J}]j$$\}$$\mathrm{L}\mathrm{C}[\mathrm{I}]=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{U},\mathrm{F})$

;

$\}$

$\mathrm{C}=\mathrm{L}\mathrm{C}$

;

$\}$

$\mathrm{Q}=\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{e}\mathrm{P}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{n}(\mathrm{D}\mathrm{F}[1]\prime \mathrm{F});\mathrm{Q}\mathrm{N}=\mathrm{p}\mathrm{t}\mathrm{o}\mathrm{z}\mathrm{p}(\mathrm{Q})j$;$\mathrm{A}=\mathrm{Q}\mathrm{N}i\mathrm{L}\mathrm{P}=2*\mathrm{L}-1;\mathrm{K}=1;\mathrm{U}\mathrm{N}=1;\mathrm{Z}\mathrm{D}=1$

while {1)if$\{$$(\mathrm{L}\mathrm{P}^{\cdot}/.2==1l\{\mathrm{Z}=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{U}\mathrm{N}*\mathrm{A},\mathrm{F})i\mathrm{U}\mathrm{N}=\mathrm{p}\mathrm{t}\mathrm{o}\mathrm{z}\mathrm{p}\mathrm{t}\mathrm{Z}];\mathrm{Z}\mathrm{D}*=\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{v}(\mathrm{U}\mathrm{N}_{s}\mathrm{Z})*\mathrm{K};\}$$\mathrm{L}\mathrm{P}=\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{v}(\mathrm{L}\mathrm{P},$$2$} ; if$\mathrm{B}=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{A}*\mathrm{A},\mathrm{F})$:$(\mathrm{L}\mathrm{P}==0)$$\mathrm{A}=\mathrm{p}\mathrm{t}\mathrm{o}\mathrm{z}\mathrm{p}(\mathrm{B})$break;;$\mathrm{K}=\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{v}(\mathrm{A},\mathrm{B})*\mathrm{K}*\mathrm{K}$$\}$$\mathrm{U}\mathrm{D}=\mathrm{f}\mathrm{a}\mathrm{c}(\mathrm{L}-1)*\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{v}(\mathrm{Q}\mathrm{N}, \mathrm{Q})^{-}(2*\mathrm{L}-1)*\mathrm{Z}\mathrm{D}$$\mathrm{C}=\alpha \mathrm{a}\mathrm{p}$(srem,

return [$\mathrm{U}\mathrm{D},$

$\}$

end$

$\mathrm{C}^{\tau}*\mathrm{U}\mathrm{N},\mathrm{F}$):vtol (C)];:;(Srem,$\mathrm{D}\mathrm{H},$$\mathrm{F}$

) ;

142
2.

$\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{u}\mathrm{e}_{-}\mathrm{g}$.

:多項式, DEN:多項式 または 因数分解されたリスト. [[因子, 重複度], . .] の形. $*/$
(リストで入力する場合の注意) 既約チェック, 有理式の約分, 整数係数化は行わない. 呼び出し側が責任を持つ.

$/*\mathrm{N}\mathrm{U}\mathrm{b}1$$/*$

def residue-g(NUM,DEN)$/*$ 簡約化 $*/$
if (tyPe (DEN) $==4$ )$\mathrm{D}=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}$

$\}$

else

:

( [1, 1]. DEN)$\{$$\mathrm{G}\mathrm{c}\mathrm{d}=\mathrm{g}\mathrm{c}\mathrm{d}$(HUM,DEN) ;(NUM,Gcd) ;Num$=\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{v}$Den$=\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{v}$$\mathrm{D}=\mathrm{f}$

$\{$

:

$\mathrm{N}\mathrm{u}\mathrm{m}=\mathrm{K}\mathfrak{P}\mathrm{N}$$\{$(DEN ,Gcd) ;ctr (Den) :$\}$$\mathrm{X}=\mathrm{v}\mathrm{a}\mathrm{r}(\mathrm{D}[1][0])$;:$\mathrm{L}\mathrm{e}\mathrm{n}=\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(\mathrm{D})$$\mathrm{P}^{-}--1;\mathrm{Q}=0$for;$(\mathrm{I}--1:\mathrm{I}<\mathrm{L}\mathrm{e}\mathrm{n};\mathrm{I}++)\{$$\mathrm{p}*=\mathrm{D}[\mathrm{I}][0]$;$\tau \mathrm{m}_{\mathrm{P}^{=\mathrm{D}[\mathrm{I}][1]}:}$$\mathrm{f}$

Or

丁皿 p*

$(\mathrm{J}=1;\mathrm{J}<\mathrm{L}\mathrm{e}\mathrm{n}:\mathrm{J}++)$$\mathrm{Q}+=\mathrm{T}\mathrm{m}\mathrm{p}$::$=(\mathrm{I}\text{ }=\mathit{1})?\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}(\mathrm{D}[\mathrm{J}][0], \mathrm{X})$$\mathrm{D}[\mathrm{J}][0]$

;

$\}$

$\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{L}=0$

;for

or

DQwewve ct (MaxL , [Q] ) ; or$\mathrm{f}$;DHwewvect$\mathrm{H}=\mathrm{N}\mathrm{u}\mathrm{m}$$\mathrm{f}$or ($\mathrm{D}\mathrm{e}\mathrm{g}\mathrm{H}=\deg\{\mathrm{H}$$\mathrm{I}\mathrm{I}=1$$\mathrm{F}=\mathrm{D}$if$(\mathrm{I}=1 ;\mathrm{I}<\mathrm{L}\mathrm{e}\mathrm{n};\mathrm{I}++)$$\mathrm{D}\mathrm{P}=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}(\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{L}\star 1, [\mathrm{p}]);\mathrm{f}$$\langle$$\mathrm{N},$;II く Len;

[I 工] [0]$\mathrm{L}=\mathrm{D}[\mathrm{I}\mathrm{I}][1]$, X) +1 ;$[\mathrm{H}])j\mathrm{f}$or$\mathrm{I}\mathrm{I}+*$)($(\mathrm{I}=1 ; \mathrm{I}<\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{L}j\mathrm{I}++)\mathrm{D}\mathrm{Q}[\mathrm{I}]=\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}$$\mathrm{N}=(\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{L}<\mathrm{D}\mathrm{e}\mathrm{g}\mathrm{H})7\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{L}$$\zeta \mathrm{I}=1;\mathrm{I}<\mathrm{N}$:: or$\mathrm{f}$; for$\mathrm{D}\mathrm{P}2=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}(\mathrm{L}+1)$:[I-1$\mathrm{X}$.

$\mathrm{D}\mathrm{e}\mathrm{g}\mathrm{H}_{*}$$\mathrm{D}\mathrm{H}[\mathrm{I}]=\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}$:$(\mathrm{I}=1 ;\mathrm{I}<\mathrm{L}:\mathrm{I}++)$$(\mathrm{I}=2;\mathrm{I}<\mathrm{L}+1;\mathrm{I}++)$

or I=l; I く L;$\mathrm{D}\mathrm{Q}2=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}(\mathrm{L});\mathrm{f}$$\mathrm{C}=\mathrm{n}\mathrm{e}\mathfrak{m}r\mathrm{e}\mathrm{c}\mathrm{t}(\mathrm{L}, [1])$;I く L;$\mathrm{I}++$)$\langle$($\mathrm{D}\mathrm{H}$[I-1],X) ;$\mathrm{I}++$)$\mathrm{R}\mathrm{P}$[工]$\mathrm{D}\mathrm{P}2$$=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{R}\mathrm{P}[\mathrm{I}-11*\mathrm{R},\mathrm{F}]$[Il$=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{D}\mathrm{P}[\mathrm{I}],$ $\mathrm{F}\rangle$$\mathrm{D}\mathrm{Q}2[\mathrm{I}]=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{D}\mathrm{Q}[\mathrm{I}].\mathrm{F})$

;

:

;
$\{$

$1\mathrm{t}=\mathrm{L}-1-\mathrm{I};\mathrm{K}\mathrm{K}=\mathrm{L}-\mathrm{I};\mathrm{C}1=1$or)$\mathrm{D}\mathrm{P}$;$\mathrm{R}\mathrm{P}=\mathrm{n}\mathrm{e}\prime \mathrm{r}\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}(\mathrm{L}, [1])$$\mathrm{f}$$\mathrm{I}++$([I-1], )$\{$$\mathrm{R}=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{n}(\mathrm{D}\mathrm{F}*\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{v}(-\mathrm{P},\mathrm{F}),\mathrm{F})$$\mathrm{I}=1$;$\mathrm{D}\mathrm{Q}$$j$$\mathrm{O}\mathrm{F}=\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}(\mathrm{F},\mathrm{X})$

for(

;

$(\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{L}<\mathrm{D}[\mathrm{I}][1])\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{L}=\mathrm{D}[\mathrm{I}][1]$$(\mathrm{I}=1;\mathrm{I}<V‘ \mathrm{a}\mathrm{x}\mathrm{L}+1;\mathrm{I}++)\mathrm{D}\mathrm{P}[\mathrm{I}]=\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}$$(\mathrm{J}=1;\mathrm{J}<\mathrm{I}+1;\mathrm{J}++)$

;

$\{$

$\mathrm{C}1*=\mathrm{K}+\mathrm{J}_{i}$[1-J1;$\mathrm{C}[\mathrm{I}]+=((\mathrm{K}\mathrm{K}+\mathrm{J})*\mathrm{D}\mathrm{P}2[\mathrm{J}+1]+\mathrm{D}\mathrm{Q}2[\mathrm{J}]\}*\mathrm{C}1*\mathrm{R}\mathrm{P}[\mathrm{J}-1]*\mathrm{C}$$\}$$\mathrm{C}[\mathrm{I}]=-\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{C}[\mathrm{I}].\mathrm{F})/\mathrm{I}i$$\}$$\mathrm{N}=(\mathrm{L}<\mathrm{D}\mathrm{e}\mathrm{g}\mathrm{H})7\mathrm{L}$$\mathrm{s}=0_{i^{\mathrm{f}}}$or: DegH :$(\mathrm{I}=0;\mathrm{I}<\mathrm{N};\mathrm{I}++)\mathrm{S}+=\mathrm{R}\mathrm{P}[\mathrm{I}]*\mathrm{D}\mathrm{H}[\mathrm{I}]*\mathrm{C}[\mathrm{L}-1-\mathrm{I}]$$\mathrm{K}=\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{e}\mathrm{P}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{n}(\mathrm{D}\mathrm{F},\mathrm{F})$$\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{D}\mathrm{F}\mathrm{D}=\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{v}$$\mathrm{I}\mathrm{n}\mathrm{v}=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}$for ($\mathrm{I}=1$

;置

;

;
( InvDF , K) ;$\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{D}\mathrm{F}=\mathrm{p}\mathrm{t}\mathrm{o}\mathrm{z}\mathrm{p}(\mathrm{K})$(Len);$<\mathrm{L}\mathrm{e}\mathrm{n}:\mathrm{I}++$

)

$\{$

;

$\mathrm{S}=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{S},\mathrm{F})$:;$].\mathrm{X}$$/\mathrm{I}$;)$/\mathrm{I}$

:

$*/$

143
Inv

:

$[\mathrm{I}]\triangleleft \mathrm{l}\mathrm{e}\mathrm{w}\mathrm{v}\mathrm{e}\mathrm{c}\mathrm{t}(2)$if (I$!=\mathrm{I}\mathrm{I}$

)

$\{$

$\mathrm{K}=\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{e}\mathrm{P}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{n}$Inv [I] [($\mathrm{D}$[Il [0] , F) ;$01=\mathrm{p}\mathrm{t}\mathrm{o}\mathrm{z}\mathrm{p}(\mathrm{K})$Inv [I] Ell;$=\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{v}(\mathrm{I}\mathrm{n}\mathrm{v}[\mathrm{I}][0],\mathrm{K})$

;

$\}$

$\}$

工 nvA $=1$ ;

for (
if (I

$\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{A}\mathrm{D}=1$$\mathrm{I}=1\mathrm{j}\mathrm{I}<\mathrm{L}\mathrm{e}\mathrm{n}$$!=\mathrm{I}\mathrm{I}$);;I 十+)$\{$$\mathrm{A}=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{A}*\mathrm{I}\mathrm{n}\mathrm{v}[\mathrm{I}][0],\mathrm{F})$$\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{A}=\mathrm{p}\mathrm{t}\mathrm{o}\mathrm{z}\mathrm{p}(\mathrm{A}$$\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{A}\mathrm{D}*=\mathrm{I}\mathrm{n}\mathrm{v}$

;

};

[IJ

$[1]*\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{v}$(InvA, ):$\mathrm{A}$$\}$$\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{G}=1$

for;$\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{G}\mathrm{D}=1$;$(\mathrm{I}=1\cdot, \mathrm{I}<\mathrm{L}\mathrm{e}\mathrm{n};\mathrm{I}++)$

if (I$!=\mathrm{I}\mathrm{I}$工 nvG*

Inv

)

$\{$

(Inv[I][01,$\mathrm{G}\mathrm{P}=\mathrm{r}\mathrm{s}$$=\mathrm{G}\mathrm{P}[0\mathit{1}$$\mathrm{D}$;$\mathrm{G}=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{G}_{2}\mathrm{F})$[Il Ell ,$\mathrm{F}$

};

;
[Il

$\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{G}\mathrm{D}*=\mathrm{I}\mathrm{n}\mathrm{v}[\mathrm{I}]\zeta 1]\wedge \mathrm{D}$;$[1]*\mathrm{G}\mathrm{P}[1]$$\}$$\mathrm{A}\mathrm{P}=\mathrm{r}\mathrm{s}$DFP(InvA,(InvDF,$\mathrm{L}-1,$$=\mathrm{r}\mathrm{s}$$\mathrm{U}\mathrm{N}=\mathrm{s}$$\mathrm{U}\mathrm{D}=\mathrm{f}$rem (DFPac ($\mathrm{F}$)$j$$2*\mathrm{L}-1_{*}\mathrm{F}$) ;$[\mathrm{O}]*\mathrm{A}\mathrm{P}[\mathrm{O}\mathrm{l}*\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{G},$$\mathrm{L}-1\rangle*\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{D}\mathrm{F}\mathrm{D}^{\wedge}$$\mathrm{R}\mathrm{N}=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{S}*\mathrm{U}\mathrm{N}, \mathrm{F}):\mathrm{R}\mathrm{D}=\mathrm{U}\mathrm{D}$;${\rm Res}=[\mathrm{R}\mathrm{D},\mathrm{R}\mathrm{N}]$print (rtostr$\mathrm{F}$(2$L- 1 )) ;$*\mathrm{D}\mathrm{F}\mathrm{P}[1]*\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{A}\mathrm{D}^{\wedge}$$(\mathrm{L}-1 )$ $*\mathrm{A}\mathrm{P}[11*\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{G}\mathrm{D}$;:$/*{\rm Re} \mathrm{s}=\mathrm{R}\mathrm{N}/\mathrm{R}\mathrm{D}i*/$$(\mathrm{p})+^{t\mathrm{t}}$:$’|+\mathrm{r}\mathrm{t}\mathrm{o}\mathrm{s}\mathrm{t}\tau({\rm Res})$

);

$\}$

$\}$

剰余同上での多項式の顔師計算 (繰り返し 2 乗法

$/*$

def

$+$

整数係数化処理)$\mathrm{r}\mathrm{s}(\mathrm{A},\mathrm{L}\mathrm{P},\mathrm{F})$ $\{$$\mathrm{X}=1;\mathrm{P}\mathrm{N}=1:\mathrm{Z}\mathrm{D}=1j$while (1)$\{$if (LPZ2 $==1$ )$\{\mathrm{P}=\mathrm{s}\mathrm{r}\mathrm{e}\mathrm{m}(\mathrm{P}\mathrm{N}*\mathrm{A},\mathrm{F}) ; \mathrm{P}\mathrm{N}=\mathrm{p}\mathrm{t}\mathrm{o}\mathrm{z}\mathrm{p}(\mathrm{P}) ; \mathrm{Z}\mathrm{D}*=\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{v}(\mathrm{P}\mathrm{N}, \mathrm{P})*\mathrm{K}j\}$;lf, F) ;$\mathrm{L}\mathrm{P}=\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{v}(\mathrm{L}\mathrm{P}, 2)$$\mathrm{B}$-srem ($\mathrm{A}*\mathrm{A}$$(\mathrm{L}\mathrm{P}==0)$$\mathrm{A}=\mathrm{p}\mathrm{t}\mathrm{o}\mathrm{z}\mathrm{p}(\mathrm{B})$break;(A , );$\mathrm{K}=\mathrm{s}\mathrm{d}\mathrm{i}\mathrm{v}$$\mathrm{B}$$*\mathrm{K}*\mathrm{K}$

;

$\}$

return [PN,];$\mathrm{Z}\mathrm{D}$

$\}$

$/*$

逆元計算 $*/$のライブラリファイル sp を使うので load しておく.
def inversePolyn(Poly. F)
;
;
Alg
(
(Poly , ,Alg));Invorat (Inv) ;(IJIVR). X) ;(InvR,)(InvR)
if (return InvR;$/*\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$$\{$$\mathrm{X}=\mathrm{v}\mathrm{a}\mathrm{r}(\overline{\mathrm{r}})$$=\mathrm{n}\mathrm{e}\mathrm{w}\mathrm{a}(\mathrm{F})$$1/\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{s}\mathrm{t}$$\mathrm{X}$$=\mathrm{s}\mathrm{i}\mathrm{m}\mathrm{p}\mathrm{a}$$\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{R}=\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{t}$$\mathrm{v}\mathrm{a}\mathrm{r}$

$\}$

end$

$\iota=0$$\mathrm{I}\mathrm{n}\mathrm{v}\mathrm{R}=\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{s}\mathrm{t}$$\mathrm{v}\mathrm{a}\mathrm{r}$$*/$$*/$