限定されたデイオファンタス不定方程式の解を効率的に算出するアルゴリズム

概要

論文の詳細を見る
よく知られているように,Matijasevicはデイオファンタスの不定方程式の一般的解法が不可能であることを証明している.しかし,ある特定の形式を持つ不定方程式に限っては,その整数解を求めることが可能であるBakerは,「f(x,y)を有理整係数の既約なs次同次式(s≧3)とすればf(x,y)=m(m≠0)を満たす整数解(x,y)は,有限の範囲に存在する」ことを示している.しかし,その解を具体的に求める効率的なアルゴリズムを提示していない.このような,解の存在する限界が実効的に求められる数値で規定されたデイオファンタスの不定方程式の整数解を求める効率的なアルゴリズムを提案する.Rを十分大きな素数としたときGF(R)上で,与えられた不定方程式をモジュラ変換し,変換後の係数が超増加数列をなすようにLenstra-Lenstra-Lovaszのアルゴリズム(LLLアルゴリズム)を適用する.超増加数列が得られれば,その性質を利用することにより,その整数解を効率良く求めることが可能となる.しかし,整数解の施囲は,数値的にかなり大きな値となるため,この解法の適用例では,扱う数値の小さいもののみを示した.
1991-10-15