ＩＳＳＮ 1880 − 2818

数理解析研究所講究録 1652

Ｃｏｍｐｕｔｅｒ Ａｌｇｅｂｒａ 一一一 Ｄｅｓｉｇｎ ｏｆ Ａｌｇｏｒｉｔｈｍｓ,Ｉｍｐｌｅｍｅｎｔａｔｉｏｎｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ

京都大学数理解析研究所

2009 年 6 月

RZMS K6kyOroku Z652

Computer Aigebra —- Design ofAigorithms,lmplementations and Applications

Jtzne, 2009

Research instztute for Ml7thematzcal Sczences1¡yoto Unzverszty, K)2oto, lapan

This is a report of research done at the Research Institute fbr MathematicalSciences, Kyoto University The papers contamed herein are m final form
and will not be submitted for publication elsewhere

はじめに
福岡教育大学教育学部数学教育講座
藤本光史（Ｍｌｔｓｕｓｈｌ ＦＵＪＩＭＯＴＯ）
東京理科大学理学部数理情報科学科
佐藤洋祐（Ｙｂｓｕｋｅ ＳＡＴＯ）

本講究録は、2007 年 11 月 7 日〜9 日に、京都大学数理解析研究所て開催された研究集会「Ｃｏｍｐｕｔｅｒ Ａ 1 ｇｅｂｒａ 一一 Ｄｅｓユｇｎ. ｏｆ Ａｌｇｏｎｔｈｍｓ, Ｉｍｐｌｅｍｅｎｔａｔユｏｎｓ ａｎｄ Ａｐｐｈｃａｔｉｏｎｓ」の報告集である。本研究集会は、ｃｏｍｐｕｔｅｒ ａｌｇｅｂｒａ（計算機代数）の様々な側面に興味を持ち活動する研究者達が、最新の成果を発表し、討論やアイディアの交換を行うことで、新しいａｌｇｏｎｔｈｍ（算法）、1 ｍｐｌｅｍｅｎｔａｔｌｏｎ（実装）、 ａｐｐｈｃａｔｉｏｎ（応用）を創出していくことを目的としたものである。計算機代数は、数学的な対象を計算機上て表現し、さらに対象への数学的操作を計算機上で実現することを目指す分野てあり、アルゴリズムの研究、ノステムの実装、そしてその応用から構成されている。1960 年代に構築されたグレブナー基底理論をへ一ｄ一・…ｉスに発展を遂げ、代数幾何 代数解析なとの純粋数学と制御理論や暗号理論などの工学分野との接猷を与える分野に成長している。近年では、ＸＭＬを用いた数式表現や数学ソフトウェア間の通信プロトコルに関する研究なと、数学の普及にも貢献しており、今後のさらなる発展か期待されている。
本研究集会では、27 件の一般講演と、ユ・・…一一・ザインタフェー・・一・一スとインタラクノヨンの世界的権威てある五十嵐健夫氏（東京大学大学院 情報理工学系研究科）を招いた特別講演を行った。研究集会参加者数は 63 名であった。本講究録では、この内の 24 件の論文を掲載している。また、2006 年 12 月 18 日〜21 日に開催された同名の研究集会の 3 件の論文も巻末に掲載している。この 3 件の論文は、数理解析研究所講究録第 1568 巻に掲載される予定たったか、電子メールによる原稿受け取りの際にトラブルかあり掲載されなかったものてある。

様々な事情により、今回の講究録の発行か大幅に遅れたことをお詫びする。

Ｃｏｍｐｕｔｅｒ Ａｌｇｅｂｒａ

Ｄｅｓｉｇｎ ｏｆ Ａｌｇｏｎｔｈｍｓ, ｌｍｐｌｅｍｅｎｔａｔｉｏｎｓ ａｎｄ ＡｐｐｌｉｃａｔｉｏｎｓＲＩＭＳ研究集会報告集

2007 年 11 月 7 日〜11 月 9 日

研究代表者 藤本 光史（Ｍｉｔｓｕｓｈｉ ＦｕＪｌｍｏｔｏ）
副代表者 佐藤 洋祐（Ｙｏｓｕｋｅ Ｓａｔｏ）
目 次

1 係数ドメインを多項式環とする多項式環の簡約グレブナ基底について 一ｌ

ＪＳＴ／東大・情報理工学系（Ｕ Ｔｏｋｙｏ） 鍋島 克輔（Ｋａｔｓｕｓｕｋｅ Ｎａｂｅｓｈｌｍａ）
2 Ｃｏｍｐｒｅｈｅｎｓｌｖｅ Ｇｒ 6 ｂｎｅｒ ｓｙｓｔｅｍにおけるＮａｂｅｓｈｌｍａ ａｌｇｏｎｔｈｍの改良とその検証… 。 一 一一 一。 一。 一・一一 一 一 11

ＣＲＥＳＴ ＪＳＴ／立教大 理（Ｒｌｋｋｙｏ Ｕ） 篠原 直行（Ｎａｏｙｕｋｉ Ｓｈｍｏｈａｒａ）
3 グレブナー一ｗａｌｋアルゴリズムの実装と効率化について一 一一一・… 一一 19

神戸大 理学（Ｋｏｂｅ Ｕ） 野呂 正行（Ｍａｓａｙｕｋｉ Ｎｏｒｏ）
神戸大 自然科学（Ｋｏｂｅ Ｕ） 崎山 早手（Ｈｌｒｏｔａｋａ Ｓａｋｉｙａｍａ）
4 安定化理論に基づくＩｎｔｅｒｖａｌ Ｔｒａｃｅ Ｌｉｆｔｍｇについて 一一 一 一一 26
東海大 理（Ｔｏｋａｉ Ｕ） 白柳 潔（Ｋｌｙｏｓｈｌ Ｓｈｌｒａｙａｎａｇ 1）
ＮＴＴコミュニケーンヨン科学基礎研究所（ＮＴＴ Ｃｏｍｍｕｎｌｃａｔｌｏｎ Ｓｃｌ Ｌａｂ） 関川 浩（Ｈｌｒｏｓｈ 1 Ｓｅｋｉｇａｗａ）
5 悪条件性を推定する浮動小数グレブナー基底の計算法一一 一。一 一 33

筑波大 数学系（ＵＴｓｕ km ｂａ） 佐々木 建昭（Ｔａｔｅａｋｉ Ｓａｓａｋｉ）
奈良女子大 理（Ｎａｒａ・Ｗｏｍｅｎ ｓ Ｕ） 加古 富志雄（ＦｕＪ ｉｏ Ｋａｋｏ）
6 ｌｎｔｅｒｅｓｔｍｇ Ｖａｒｔａｎｔｓ ｏｆ ｔｈｅ Ｊｏｓｅｐｈｕｓ Ｐｒｏｂｌｅｍ
Ｈｏｗ ｈｉｇｈ ｓｈｏｏｌ ｓｔｕｄｅｎｔｓ ｃａｎ ｄｉｓｃｏｖｅｒ ｔｈｅｏｒｅｍｓ ｕｓｍｇ ｃｏｍｐｕｔｅｒ ａｌｇｅｂｒａ ｓｙｓｔｅｍｓ 一一 44

関西学院高等部（Ｋｗａｎｓｅｉ Ｇａｋｕｍ Ｈｉｇｈ Ｓｃｈｏｏｌ）宮寺 良平（Ｒｙｏｈｅｌ Ｍｌｙａｄｅｒａ）
関西学院大・理工（Ｋｗａｎｓｅ 1 Ｇａｋｕｉｎ Ｕ） 峰松 大介（Ｄａｌ ｓｕｋｅ Ｍｌｎｅｍａｔｓｕ）
関西学院高等部（Ｋｗａｎｓｅ 1 Ｇａｋｕｍ Ｈｉｇｈ Ｓｃｈｏｏｌ）松井 啓史（Ｈｌｒｏｓｈｌ Ｍａｔｓｕｌ）〃 山内 俊幸（Ｔｏｓｈｌｙｕｋ 1 Ｙａｍａｕｃｈｉ）〃 内藤 昌宗（Ｍａｓａｋａｚｕ・Ｎａｌｔｏ）〃 巽創（Ｓｏｈ Ｔａｔｓｕｍ 1）〃 井上 貴文（Ｔａｋａｈｕｍ 1 ｌｎｏｕｅ）
7 安定化剰余列算法の改良 ・…一一一ｎ一一一ｔ・一・…一一一一一一。一・・一・一・ｂ一一一一・・ｔｔ一・55

筑波大・数理物質科学（ＵＴｓｕｋｕｂａ） 讃岐 勝（Ｍａｓａｒｕ ＳａｎＵｋ 1）
8 Ｒｕｐｐｅｒｔ行列による近似ＧＣＤの算出 一一一 ・一一一一 ・一一一一・一一一……・63
神戸大 人間発達環境学（Ｋｏｂｅ Ｕ） 長坂 耕作（Ｋｏｓａｋｕ Ｎａｇａｓａｋａ）
9 係数の小さいＫ［ｘ］上格子基底一。 71
筑波大・数理物質科学（ＵＴｓｕｋｕｂａ） 大倉 安孝（Ｙａｓｕｔａｋａ・Ｏｏｋｕｒａ）

1 鱒

10 判別式と拡張Ｈｅｎｓｅｌ構成 一一一…一・一一一一一一一・一一一一一一一一一一一一一一一…一一一一一一一一 79

筑波大・数理物質科学（ＵＴｓｕ km ｂａ） 小副川 健（Ｔａｋｅｓｈｌ Ｏｓｏｅｋａｗａ）
11 多変数代数関数のＴａｙｌｏｒ＆Ｈｅｎｓｅ 1 級数の収束領域 85
筑波大・数学系（ＵＴｓｕｋｕｂａ） 佐々木 建昭（Ｔａｔｅａｋｉ Ｓａｓａｋｉ）
日本数学検定協会（Ｍａｔｈ Ｃｅｒｎｆｉｃａｔｌｏｎ ｌｎｓｔ） 稲葉 大樹（Ｄａ 1 Ｊｕ Ｉｎａｂａ）
12 傾きを用いた衣服記号記述基盤について 。一一一一…一一。.。一一一＿.. 一一一＿＿一. ＿一. 一一一一一..93

スタジオフオンス（ＳｔＵｄｉｏ Ｐｈｏｎｅｓ） 桐生 裕介（Ｙｕｓｕｋｅ Ｋｌｎｕ）

山口大・教育（Ｙａｍａｇｕｃｈｉ Ｕ） 北本 卓也（Ｔａｋｕｙａ Ｋｉｔａｍｏｔｏ）
サイバネノトシステム（Ｃｙｂｅｍｅｔ Ｓｙｓｔｅｍｓ Ｃｏ, Ｌｔｄ）

山口 哲（Ｔｅｔｓｕ Ｙａｍａｇｕｃｈｉ）
1 3 Ｃｏｍｐｕｔａｔｉｏｎｓ ｏｆ ｎｏｎｃｏｍｍｕｔａｔｉｖｅ Ａｌｅｘａｎｄｅｒ ｍｖａｎａｎｔｓ 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 102

東大・数理科学（ＵＴｏｋｙｏ） 逆井 卓也（Ｔａｋｕｙａ Ｓａｋａｓａｉ）
スタジオフォンズ（Ｓｔｕｄｌｏ Ｐｈｏｎｅｓ） 桐生 裕介（Ｙｕｓｕｋｅ Ｋｌｒｌｕ）
14 陰関数描画と区間数演算の効率化について一一一一一…一一一一一＿＿一,.. 一一..112

電通大・電気通信（ＵＥＩｅｃｔｒｏ−Ｃｏｍｍｕｎｌｃａｔｌｏｎｓ）

村尾 裕一（Ｈｌｒｏｋａｚｕ Ｍｕｒａｏ）

アルファオメガ（ＡｌｐｈａＯｍｅｇａ Ｉｎｃ） 齋藤 友克（Ｔｏｍｏｋａｔｓｕ Ｓａｌｔｏ）
徳山工業高専（Ｔｏｋｕｙａｍａ Ｎａｔ Ｃｏｌｌ Ｔｅｃｈ） 近藤 祐史（Ｙ叩Ｋｏｎｄｏｈ）
15 インタラクティブコンピューティングの世界 一・一一一一一一一一一一ｔ一・一・ｂ一一・一・・一一一一…一一…一一一・120

東大・情報理工学系（ＵＴｏｋｙｏ） 五十嵐 健夫（Ｔａ：ｋｅｏ Ｉｇａｒａｓｈ 1）
16 ＧＡＰを用いたＲｕｂｌｋ ｓ Ｃｕｂｅ解法表示ソフトについて一一一一一一。一一一. 一＿＿＿ 125

オービック（Ｏｂｌｃ Ｃｏ, Ｌｔｄ） 田崎 拓馬（Ｔａｋｕｍａ Ｔａｓａｋｌ）

福岡教育大（Ｆｕｋｕｏｋａ Ｕ Ｅｄｕ） 藤本 光史（Ｍｌｔｓｕｓｈｌ Ｆ叩ｍｏｔｏ）
17 一一般化ｖａｎ ｄｅｒ Ｍｏｎｄｅ行列の行列式について一一一一ｂ・. 一一・・一... 一一一一一＿一一一一＿一一＿一. 一.,.、一一 132

山口大・教育（Ｙａｍａｇｕｃｈｌ Ｕ） 北本 卓也（Ｔａ km ｙａ Ｋｌｔａｍｏｔｏ）
サイバネノトシステム（Ｃｙｂｅｍｅｔ Ｓｙｓｔｅｍｓ Ｃｏ, Ｌｔｄ）

山口 哲（Ｔｅｔｓｕ Ｙａｍａｇｕｃｈｉ）
18 数値代数方程式のフィルタ対角化法による解法ｉ・。一一一一・一一一一一一…一一一一…134

首都大・理工学（Ｔｏｋｙｏ Ｍｅｔｒｏｐｏｌｌｔａｎ Ｕ） 村上 弘（Ｈｉｒｏｓｈｉ Ｍｕｒａｋａｍｉ）
1 9 Ｔｈｅ ｐｒｅｓｕｐｐｏｓｅｄ ｌ ｓｔ ｐｎｍｉｔｉｖｅ ｐｏｌｙｎｏｍｉａｌｓ ｏｖｅｒ ａ ｆｉｎｉｔｅ ｆｉｅｌｄ 一一一一一一一一一一一一一一一一一一一一一一一一一一一 146
筑波大・数理物質科学（ＵＴｓｕｋｕｂａ） 太刀川 弘幸（Ｈｌｒｏｙｕｋｉ Ｔａｃｈｌｋａｗａ）〃 照井 章（Ａｋｉｒａ ＴｅｒＵｌ）
20 置換群の組合せ論的可移拡大からてきるデザインー ・ ・ 155

山梨大・医学工学総合（ＵＹａｍａｎａｓｈ 1） 宮本 泉（ｌｚｕｍｌ Ｍｌｙａｍｏｔｏ）
21 脆弱性のない代数曲面公開鍵暗号にむけて ｅ・一一一・一一一 ・一一一一…一一一・一・一一・・ｅ一一一一一ｍ一）一一一一一一一一。・ 一 162

大阪経済法科大・教養（Ｏｓａｋａ Ｕ Ｅｃｏｎ Ｌａｗ）岩見 真希（Ｍａｋｌ Ｉｗａｍ 1）

縣 11 一

22 グレフナ・一…基底による幾何定理の証明について（1）一イデアル成分の分解の利用一一一一一 一一…一一一・一一一一一晒・一一一・一一一一一一……一・一一一一一 173

筑波大・図書館情報メディア（ＵＴｓｕｋｕｂａ） 森継 修一（Ｓｈｕｌｃｈ 1 ＭｏｒｌｔｓｕｇＵ）〃 荒井 千里（Ｃｈｉｓａｔｏ Ａｒａ 1）
23 プール多項式環における消去イデアルの計算について 一一一・一一一一一一一一 182

東京理大・理学（Ｔｏｋｙｏ Ｕ Ｓｃ 1） 永井 彰（Ａｋｉｒａ Ｎａｇａ 1）〃 井上 秀太郎（Ｓｈｕｔａｒｏ Ｉｎｏｕｅ）
東京理大・理（Ｔｏｋｙｏ Ｕ Ｓｃ 1） 佐藤 洋祐（Ｙｏｓｕｋｅ Ｓａｔｏ）
2 4 Ａ ｎｅｗ ａｐｐｒｏａｃｈ ｔｏ Ｃａｌｃｕｌｕｓ ｏｆ Ｓｅｔ 一一一一一 一一一 一 一一一 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 一一 一一一一一 192

東京理大・理学（Ｔｏｋｙｏ Ｕ Ｓｃ 1）井上 秀太郎（Ｓｈｕｔａｒｏ Ｉｎｏｕｅ）

25 ｘｆｙにおけるＭａｔｈＭ：Ｌ編集機能の開発
愛媛大・理工学（Ｅｈｌｍｅ Ｕ）

一ｄ一一 一ｖ一一一一 ｔ−ｐ−ｅ−ｐ一一ｅｅｅｅｅ一一ｅｅｅ−ｅ一一一ｔｒ−ｅｅ−ｅｅ−ｎ一一一一一ｅ−ｔｅｔｔｉ）ｎｔ一一一一一 ｔｉ−ｅ−ｄｂ一 196

甲斐 博（Ｈｉｒｏｓｈｉ Ｋａｉ）
宮本 敦史（Ａｔｓｕｓｈｌ Ｍｌｙａｍｏｔｏ）
11
久米 正起（Ｍａｓａｋｌ Ｋｕｍｅ）
愛媛大・工学（Ｅｈｌｍｅ Ｕ）
河田 貴幸（Ｔａｋａｙｕｋｌ Ｋａｗａｔａ）
11
冨成 泰介（Ｔａｉｓｕｋｅ Ｔｏｍｌｎａｎ）
シャストシステム（Ｊｕｓｔｓｙｓｔｅｍｓ Ｃｏｒｐｏｒａｔｌｏｎ） 田村 恭士（Ｙａｓｕｓｈｌ Ｔａｍｕｒａ）
愛媛キャンパス情報サービス（Ｅｈｉｍｅ Ｃａｍｐｕｓ ｌｎｆｏ Ｓｅｒｖｌｃｅ, Ｃｏ,：Ｌｔｄ）
11

26

野田 松太郎（Ｍａｔｕ−Ｔａｒｏｗ Ｎｏｄａ）
パラメータを持つ有理関数のハイブリノト積分一一一一・一。一一一…一一・一。一一一一・一一一一ｂ・一一・ｐ一・・一一・一一・一 203

愛媛大・理工学（Ｅｈｌｍｅ Ｕ） 中川 干菜美（Ｎａｎａｍｌ Ｎａｋａｇａｗａ）
甲斐 博（Ｈｌｒｏｓｈｌ Ｋａ 1）
愛媛キャンパス情報サービス（Ｅｈｌｍｅ Ｃａｍｐｕｓ ｌｎｆｏ Ｓｅｒｖｌｃｅ, Ｃｏ,：Ｌｔｄ）
野田 松太郎（Ｍａｔｕ・Ｔａｒｏｗ Ｎｏｄａ）

27

複合数学Ｗｅｂサービスに関する研究 ＿＿＿. 一. 一＿一, 一＿＿一一＿一一..、. 一.、一一＿一＿ 211

愛媛大・理工学（Ｅｈｌｍｅ Ｕ） 中西 智美（Ｔｏｍｏｍｌ Ｎａｋａｎｌｓｈ 1）
馬田 理世（Ｒｌｙｏ Ｉｋｅｄａ）〃 甲斐 博（Ｈｌｒｏｓｈｌ Ｋａ 1）

一 皿 一