拡張Hensel構成の効率化 - 疎な多変数多項式の因数分解を念頭に - (Computer Algebra --Theory and its Applications)

Abstract

拡張Hensel梢成とは、多変数多項式のGCD計算や因数分解で絶大な威力を発揮する一般Hensel構成を、算法が破綻する場合にも成立するように拡張したものである。発表時(2000年)には、主係数特異な多変数多項式の因数分解では他の追随を許さなかった。近年、欧米でZippelやBen-Or/Tiwariの疎補間法に基づく因数分解法が開発され、拡張Hensel法の優位が脅かされている。そのため、筆者らは数年前から拡張Hensel法の効率化に取り組んできた。本稿ではそれらの成果の上に、多項式因数分解への応用に限定した一つの効率化法を呈示する。拡張Hensel因子は従変数に関して有理式となるのが特徴だが、従変数の一つを除き他を2倍に重み付けることにより、有理式の分母因子を小さくするとともに、計算全体が分割される可能性を持つ方法である。研究は緒についたばかりだが、本報告では簡単な例によりアイデアの有用性を示す。