計算機代数の諸算法

点击翻译按钮获取中文摘要

本年度は研究の基礎として、文献の収集及び整理をまず行った。その結果既に19世紀にいくたの有用な算法が知られていたことを確認した。例えば連立代数方程式系を式の形で解くにはグレブナー基底を作れば、消去が機械的にできるが、しばしば記憶容量あふれで計算できなくなる。このときグレブナー基底そのものを完成しなくても、適当な順序で高次の項から順に消去する方法で成功することが多い。順序は伝統的な変数の辞書式順序よりも、項の全次数を第一とするほうが成功率が高い。簡単な場合には中間式が因数分解でき、意外に容易に解けることがあった。また有限体上の多項式の因数分解にはバールカンプの算法が有用なことを以前に確認しているが、バールカンプ行列の固有多項式を計算すれば因子の次数がわかること、及び固有多項式の計算には適当な値を代入した行列式の値から補間法の手順で効率よく計算できることを再発見した(故高橋秀俊教授が六年余り前に注意していたが、これまで注目をひいていなかった)。その他、大きな整数の素数判定及び素因数分解に関する楕円曲線法の実現と公開鍵暗号への応用に関しても、著るしい進展を見た。全般的に今年度の研究により、数学と計算機科学の界面の一つとしての計算機代数の研究方向とあるべき姿が、明確に把握できたと思う。