(57)【要約】【課題】既約多項式ｐに最も近い可約多項式を求める。【解決手段】ｄｅｇ（・）を多項式・の全次数、ｐを既約多項式、ｄｅｇ（ｐ）＝ｎ、ｆ０を多項式として、第一演算部１が多項式ｆ０ｇ１がｄｅｇ（ｆ０ｇ１）≦ｎを満たし既約多項式ｐに最も近くなるような多項式ｇ１を求め、第二演算部２が多項式ｆ２’ｇ１がｄｅｇ（ｆ２’ｇ１）≦ｎを満たし既約多項式ｐに最も近くなるような多項式ｆ２’を求め、ｆ２＝ｆ２’／‖ｆ２’‖２として、第三演算部３が多項式ｆ２ｇ２がｄｅｇ（ｆ２ｇ２）≦ｎを満たし既約多項式ｐに最も近くなるような多項式ｇ２を求め、多項式ｇ２で多項式ｇ１を置き換えて、第二演算部２及び第三演算部３の処理を繰り返す。【選択図】図１
2011118806.tif 000002
【特許請求の範囲】
【請求項１】
ｄｅｇ（・）を多項式・の全次数、ｐを既約多項式、ｄｅｇ（ｐ）＝ｎ、ｆ０を多項式として、
上記既約多項式ｐ及び上記多項式ｆ０についての正規方程式を解くことにより、多項式ｆ０ｇ１がｄｅｇ（ｆ０ｇ１）≦ｎを満たし上記既約多項式ｐに最も近くなるような多項式ｇ１を求める第一演算部と、
上記既約多項式ｐ及び上記多項式ｇ１についての正規方程式を解くことにより、多項式ｆ２’ｇ１がｄｅｇ（ｆ２’ｇ１）≦ｎを満たし上記既約多項式ｐに最も近くなるような多項式ｆ２’を求める第二演算部と、
ｆ２＝ｆ２’／‖ｆ２’‖２として、上記既約多項式ｐ及び上記多項式ｆ２についての正規方程式を解くことにより、多項式ｆ２ｇ２がｄｅｇ（ｆ２ｇ２）≦ｎを満たし既約多項式ｐに最も近くなるような多項式ｇ２を求める第三演算部と、を含み、
上記第三演算部で求められた多項式ｇ２で上記多項式ｇ１を置き換えて、上記第二演算部の処理及び上記第三演算部の処理を繰り返す、
ことを特徴とする最近多項式算出装置。
【請求項２】
請求項１の最近多項式算出装置において、
多項式ｆ１＝ｆ０とし、εを定数とし、‖ｆ２−ｆ１‖２＜ε、‖ｇ２−ｇ１‖２＜ε、‖ｆ２’ｇ１−ｆ２ｇ２‖２＜εの少なくとも１つを終了条件として、その終了条件を満たすかどうかを判定する終了条件判定部を更に含み、
上記終了条件判定部において終了条件を満たすと判定されるまで、上記多項式ｆ２で上記多項式ｆ１を、上記多項式ｇ２で上記多項式ｇ１を置き換えて上記第二演算部の処理及び上記第三演算部の処理を繰り返す、
ことを特徴とする最近多項式算出装置。
【請求項３】
請求項１又は２の最近多項式算出装置において、
異なる複数の多項式ｆ０のそれぞれについて上記第一演算部、上記第二演算部及び上記第三演算部の処理を行うことにより求まった複数の多項式ｆ２’ｇ１又は多項式ｆ２ｇ２の内、上記既約多項式ｐに最も近い多項式を出力する最近判定部を更に含む、
ことを特徴とする最近多項式算出装置。
【請求項４】
ｄｅｇ（・）を多項式・の全次数、ｐを既約多項式、ｄｅｇ（ｐ）＝ｎ、ｆ０を多項式として、
第一演算部が、上記既約多項式ｐ及び上記多項式ｆ０についての正規方程式を解くことにより、多項式ｆ０ｇ１がｄｅｇ（ｆ０ｇ１）≦ｎを満たし上記既約多項式ｐに最も近くなるような多項式ｇ１を求める第一演算ステップと、
第二演算部が、上記既約多項式ｐ及び上記多項式ｇ１についての正規方程式を解くことにより、多項式ｆ２’ｇ１がｄｅｇ（ｆ２’ｇ１）≦ｎを満たし上記既約多項式ｐに最も近くなるような多項式ｆ２’を求める第二演算ステップと、
第三演算部が、ｆ２＝ｆ２’／‖ｆ２’‖２として、上記既約多項式ｐ及び上記多項式ｆ２についての正規方程式を解くことにより、多項式ｆ２ｇ２がｄｅｇ（ｆ２ｇ２）≦ｎを満たし既約多項式ｐに最も近くなるような多項式ｇ２を求める第三演算ステップと、を含み、
上記第三演算ステップで求められた多項式ｇ２で上記多項式ｇ１を置き換えて、上記第二演算ステップの処理及び上記第三演算ステップの処理を繰り返す、
ことを特徴とする最近多項式算出方法。
【請求項５】
請求項１から３の何れかの最近多項式算出装置の各部としてコンピュータを機能させるための最近多項式算出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、与えられた多項式ｐから、可約かつｐに近い多項式を求める技術に関する。
【背景技術】
【０００２】
多変数多項式ｐは、全次数、すなわち、
【０００３】
【数１】
2011118806.tif 000003
【０００４】
と書いたときの、ｊ１＋…＋ｊｓの最大値（ｊ１，…，ｊｓは、ａｊ１…ｊｓ≠０の範囲を動く）が２以上であっても既約な場合が存在する。
【０００５】
今、多項式ｐの係数が観測により得られたため、あるいは、何らかの近似計算による処理を行った結果得られたため誤差を含むものとする。すると、本来は既約であったｐが誤差のために可約となる場合が生じる。したがって、既約な多項式ｐに対し、どの程度の誤差なら既約性が保たれるか、を知りたい場合が生じる。
【０００６】
以下、２つの多項式ｆとｇの距離を、ｆ−ｇの２−ノルム‖ｆ−ｇ‖２、すなわち、
【０００７】
【数２】
2011118806.tif 000004
【０００８】
として、
【０００９】
【数３】
2011118806.tif 000005
【００１０】
で計るものとする。ただし、複素数ｃに対し、ｃの上付きバーはｃの複素共役を表す。
【００１１】
与えられた既約な多項式ｐに対しどの程度の誤差なら既約性が保たれるかを知る最新及び今までの代表的な手法は、例えば非特許文献１に記載されている。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】K. Nagasaka, “Towards More Accurate Separation Bounds of Empirical Poly-nomials II”, Lecture Notes in Computer Science 3718, pp.318-329, 2005.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
非特許文献１に記載された手法は、与えられた既約な多項式から一番近い可約な多項式までの距離を下から評価することはできるが、実際にはどれくらいの距離のところに可約な多項式があるのか、については解答を与えることができないという課題がある。
【課題を解決するための手段】
【００１４】
上記の課題を解決するために、この発明では、ｄｅｇ（・）を多項式・の全次数、ｐを既約多項式、ｄｅｇ（ｐ）＝ｎ、ｆ０を多項式として、多項式ｆ０ｇ１がｄｅｇ（ｆ０ｇ１）≦ｎを満たし既約多項式ｐに最も近くなるような多項式ｇ１を求め、多項式ｆ２’ｇ１がｄｅｇ（ｆ２’ｇ１）≦ｎを満たし既約多項式ｐに最も近くなるような多項式ｆ２’を求め、ｆ２＝ｆ２’／‖ｆ２’‖２として、多項式ｆ２ｇ２がｄｅｇ（ｆ２ｇ２）≦ｎを満たし既約多項式ｐに最も近くなるような多項式ｇ２を求め、多項式ｇ２で多項式ｇ１を置き換えて、上記の多項式ｆ２’を求める処理及び多項式ｇ２を求める処理を繰り返す。
【発明の効果】
【００１５】
与えられた既約多項式ｐから、可約かつｐに近い多項式を求めることができる。
【図面の簡単な説明】
【００１６】
【図１】最近多項式算出装置の例の機能ブロック図。
【図２】最近多項式算出方法の例の流れ図。
【図３】最近多項式算出方法の例の流れ図。
【発明を実施するための形態】
【００１７】
［理論的背景］
この発明の実施形態の説明に先立って、この発明の理論的背景を説明する。
【００１８】
Ｋを実数全体の集合、または複素数全体の集合とする。ｘ１，…，ｘｓを変数とするＫ係数の多項式の全体の集合をＫ［ｘ１，…，ｘｓ］と書く。Ｖを｛ｈ∈Ｋ［ｘ１，…，ｘｓ］｜ｄｅｇ（ｈ）≦ｎ｝（ｎ＜∞）とする。ただし、ｄｅｇ（ｈ）はｈの全次数，すなわち、
【００１９】
【数４】
2011118806.tif 000006
【００２０】
と書いたときの、ｊ１＋…＋ｊｓの最大値（ｊ１，…，ｊｓは、ａｊ１…ｊｓ≠０の範囲を動く）である。Ｖは有限次元のＫ−線形空間となる。ｐ，ｆ∈Ｋ［ｘ１，…，ｘｓ］の全次数をそれぞれｎ，ｄ（１≦ｄ＜ｎ）とし、Ｗを｛ｈ∈Ｖ｜ｆはｈの因子｝とする。ＷはＶのＫ−部分空間である。
【００２１】
ｐのＷへの正射影をｑとすると、ｑはｆを因子とし、ｄｅｇ（ｑ）≦ｄｅｇ（ｐ）を満たす多項式の中で‖ｑ−ｐ‖２が最小となる唯一の多項式であるので、最近多項式と呼ぶことにする。
【００２２】
Ｗ’＝｛ｈ∈Ｖ｜ｄｅｇ（ｈ）≦ｎ−ｄ｝とすると、ｈ∈Ｗ’にｆを掛ける操作はＷ’からＷへの線形写像なので、行列Ｍ（ｆ）で記述できる。例えば、ｓ＝２、ｎ＝２、ｄ＝１、ｆ＝ｘ−ｙの場合、
【００２３】
【数５】
2011118806.tif 000007
【００２４】
である。ただし、ｈ＝ａｘ＋ｂｙ＋ｃ∈Ｗ’（ａ，ｂ，ｃ∈Ｋ）に対し、
【００２５】
【数６】
2011118806.tif 000008
【００２６】
（ｈの係数を成分とするベクトル）として、
【００２７】
【数７】
2011118806.tif 000009
【００２８】
の成分が上から順にｆｈのｘ２，ｘｙ，ｙ２，ｘ，ｙの係数、定数項、を表す。
【００２９】
例えば、各多項式をいわゆる次数付き辞書式順序に基づいて記載し、ベクトルｖ（・）の第ｍ行の成分が多項式・の第ｍ項の係数に対応しており、Ｍ（ｆ）ｖ（ｈ）の第ｍ行の成分が多項式ｆｈの第ｍ項の係数に対応しているとする。このとき、行列Ｍ（ｆ）の第ｍ行第ｋ列の成分は、多項式ｆに全次数がｎ−ｄ以下であって係数が１の単項式の中で順序がｋ番目のものをかけることにより求まった多項式の第ｍ項の係数である。
【００３０】
ｆｇが最近多項式であることは、定義より、Ｘ＝ｖ（ｇ）が‖ｖ（ｐ）−Ｍ（ｆ）Ｘ‖２を最小化することである。よって、参考文献１の定理２．１．２にある通り、ｖ（ｇ）は、方程式
Ｍ（ｆ）＊Ｍ（ｆ）Ｘ＝Ｍ（ｆ）＊Ｘ  …  （１）
の解となっている。ここで、Ｍ（ｆ）＊はＭ（ｆ）の随伴行列（各成分を複素共役に置き換えた上で転置した行列）である。なお、方程式（１）は正規方程式と呼ばれる。上記の通り、ｆｇはｐのＷへの正射影であるから一意に決まり、よってｇも一意に決まるから、方程式（１）の解は一意となる。
【００３１】
〔参考文献１〕S. L. Campbell and C. D. Meyer, Jr., “Generalized Inverses of Linear Trans-formations”, Pitman Publ. Ltd., London, 1979.
多項式列｛ｐｊ｝，｛ｆｊ｝，｛ｇｊ｝及び数列｛ｃｊ｝を以下のように定義する。
【００３２】
ｐ，ｆ０∈Ｋ［ｘ１，…，ｘｓ］の全次数をそれぞれｎ，ｄ（１≦ｄ＜ｎ）とし、さらに‖ｆ０‖２＝１とする。ｊ＝１，２，…に対し、ｐ２ｊ−１＝ｆｊ−１ｇｊを、ｆｊ−１を因子として持ち、ｄｅｇ（ｐ２ｊ−１）≦ｄｅｇ（ｐ）を満たすｐに一番近い多項式、ｐ２ｊ＝ｃｊｆｊｇｊを、ｇｊを因子として持ち、条件ｄｅｇ（ｐ２ｊ）≦ｄｅｇ（ｐ），‖ｆｊ‖２＝１，ｃｊ＞０を満たすｐに一番近い多項式とする。
【００３３】
ｐ，ｆ０が実係数多項式の場合、すべてのｊに対してｐｊ，ｆｊ，ｇｊも実係数となることに注意。
【００３４】
≪注意１≫ｇ１，ｐ１は０となることがある。例えば、ｓ＝２，ｐ＝ｘ１２＋ｘ１ｘ２＋ｘ２２，ｆ０＝（ｘ１−ｘ２）／（２（１／２））のとき、以下に示す通りｇ１＝ｐ１＝０である。
【００３５】
ｇ１＝ａｘ＋ｂｙ＋ｃとすると、
【００３６】
【数８】
2011118806.tif 000010
【００３７】
の２−ノルムを最小化することになる。
【００３８】
【数９】
2011118806.tif 000011
【００３９】
なので、正規方程式は、
【００４０】
【数１０】
2011118806.tif 000012
【００４１】
である。よって、解はａ＝ｂ＝ｃ＝０となるから、ｇ１＝０、よって、ｐ１＝０である。
【００４２】
≪命題１≫ｐ１≠０のとき、以下が成り立つ。
【００４３】
１．‖ｐｊ‖２は単調非減少である。
【００４４】
２．ｊ→∞のとき、‖ｐｊ＋１−ｐｊ‖２，‖ｆｊ＋１−ｆｊ‖２，‖ｇｊ＋１−ｇｊ‖２は０に収束し、ｃｊは１に収束する。
【００４５】
命題１の証明のために補題を一つ準備する。
【００４６】
≪補題１≫ｆ，ｇ∈Ｋ［ｘ１，…，ｘｓ］に対し、
【００４７】
【数１１】
2011118806.tif 000013
【００４８】
を成り立たせるような、ｆｇの全次数のみに依存する正の定数ｍ，Ｍが存在する。
【００４９】
≪証明≫まず、ｓ＝１の場合を示す。ｆｇ＝ａｎｘ１ｎ＋…＋ａ１ｘ１＋ａ０（ａｎ≠０）とすると、ｍとして２−ｎを取ることができる。これは、例えば以下の参考文献２に系６．３３として記述されている。
【００５０】
〔参考文献２〕J. von zur Gathen and J. Gerhard, “Modern Computer Algebra, 2nd ed.”, Cambridge University Press, Cambridge, New York, Melbourne, Madrid, Cape Town, 2003.
すべてのｊ（０≦ｊ≦ｎ）に対して不等式｜ａｊ｜≦‖ｆ‖２・‖ｇ‖２が成り立つので、Ｍとして（ｎ＋１）１／２を取ることができる。
【００５１】
次にｓ≧２の場合を示す。写像σ：Ｋ［ｘ１，…，ｘｓ］→Ｋ［ｘ］を
【００５２】
【数１２】
2011118806.tif 000014
【００５３】
と定義する。任意のｆ，ｇ∈Ｋ［ｘ１，…，ｘｓ］、ただし、ｄｅｇ（ｆｇ）≦ｎに対し、σ（ｆｇ）＝σ（ｆ）σ（ｇ）及び‖ｆ‖２＝‖σ（ｆ）‖２が成立することから、ｓ＝１の場合に帰着できる（証明終）。
【００５４】
命題１の証明は以下の通り。
【００５５】
≪証明≫ｒｊ＝ｐ−ｐｊとする。
【００５６】
‖ｒｊ‖２は単調非増加かつ非負だから収束する。ｐｊはｐの正射影として得られるので、ｐｊとｐ−ｐｊ＝ｒｊは直交する。よって、‖ｐｊ‖２２＝‖ｐ‖２２−‖ｒｊ‖２２だから、‖ｒｊ‖２が収束することより‖ｐｊ‖２は収束する。
【００５７】
ｊ  が奇数の場合、
Ｗ＝｛ｈ∈Ｋ［ｘ１，…，ｘｓ］｜ｈはｇ（ｊ＋１）／２を因子として持ち、ｄｅｇ（ｈ）≦ｄｅｇ（ｐ）｝，
ｊ  が偶数の場合、
Ｗ＝｛ｈ∈Ｋ［ｘ１，…，ｘｓ］｜ｈはｆｊ／２を因子として持ち、ｄｅｇ（ｈ）≦ｄｅｇ（ｐ）｝
とする。ｐｊ，ｐｊ＋１∈Ｗであり、ｐｊ＋１はｐのＷへの正射影であるから、ｐ−ｐｊ＋１とｐｊ＋１−ｐｊは直交する。ｒｊ＋１＝ｐ−ｐｊ＋１及びｐｊ＋１−ｐｊ＝ｒｊ−ｒｊ＋１に注意すれば、‖ｐｊ＋１−ｐｊ‖２２＝‖ｒｊ‖２２−‖ｒｊ＋１‖２２である。よって、‖ｐｊ＋１−ｐｊ‖２は０に収束する。
【００５８】
補題１より、ｊによらず以下を満たす定数Ｍ＞０が存在する。
【００５９】
‖ｐ１‖２≦‖ｐ２ｊ−１‖２＝‖ｆｊ−１ｇｊ‖２≦Ｍ‖ｆｊ−１‖２・‖ｇｊ‖２＝Ｍ‖ｇｊ‖２
ｐ２ｊ＋２−ｐ２ｊ＋１＝ｇｊ＋１（ｃｊ＋１ｆｊ＋１−ｆｊ）より、ｊによらず以下を満たす定数ｍ＞０が存在する。
‖ｐ２ｊ＋２−ｐ２ｊ＋１‖２＝‖ｇｊ＋１（ｃｊ＋１ｆｊ＋１−ｆｊ）‖２≧ｍ‖ｇｊ＋１‖２・‖ｃｊ＋１ｆｊ＋１−ｆｊ‖２
よって、
【００６０】
【数１３】
2011118806.tif 000015
【００６１】
が成り立ち、‖ｃｊ＋１ｆｊ＋１−ｆｊ‖２は０に収束する。
【００６２】
三角不等式より、
‖ｃｊ＋１ｆｊ＋１−ｆｊ‖２≧｜‖ｃｊ＋１ｆｊ＋１‖２−‖ｆｊ‖２｜＝｜ｃｊ＋１−１｜
が成り立つ。よって、ｌｉｍｊ→∞ｃｊ＝１である。これより、ｌｉｍｊ→∞‖ｆｊ＋１−ｆｊ‖２＝０が成り立つ。なぜなら、
‖ｆｊ＋１−ｆｊ‖２＝‖ｆｊ＋１−ｃｊ＋１ｆｊ＋１＋ｃｊ＋１ｆｊ＋１−ｆｊ‖２≦｜１−ｃｊ＋１｜＋‖ｃｊ＋１ｆｊ＋１−ｆｊ‖２
が成り立つからである。等式ｐ２ｊ＋１−ｐ２ｊ＝ｆｊ（ｇｊ＋１−ｃｊｇｊ）より、‖ｐ２ｊ＋１−ｐ２ｊ‖２＝‖ｇｊ＋１−ｃｊｇｊ‖２だから‖ｇｊ＋１−ｃｊｇｊ‖２→０。よって，
‖ｇｊ＋１−ｇｊ‖２＝‖ｇｊ＋１−ｃｊｇｊ＋ｃｊｇｊ−ｇｊ‖２≦‖ｇｊ＋１−ｃｊｇｊ‖２＋｜ｃｊ−１｜・‖ｇｊ‖２
及び｛‖ｇｊ‖２｝が有界であることより、‖ｇｊ＋１−ｇｊ‖２→０がいえる（証明終）。
【００６３】
前章の結果を用いたアルゴリズムの一例を以下に示す。
【００６４】
≪アルゴリズム≫
入力：多項式ｐ，ｆ０∈Ｋ［ｘ１，…，ｘｓ］（１≦ｄｅｇ（ｆ０）＜ｄｅｇ（ｐ），‖ｆ０‖２＝１）及びε＞０。
出力：（ｆ，ｇ，ｑ，‖ｑ−ｐ‖２）あるいは「不適」。
１．ｄｅｇ（ｐ）をｎと置く。
【００６５】
・ｆ０ｇ１がｄｅｇ（ｆ０ｇ１）≦ｎを満たすｐの最近多項式となるようなｇ１を求める（ステップＳ１１）。
【００６６】
・ｇ１が定数の場合、「不適」を返して終了（ステップＳ１３）。
【００６７】
・ｇ１が定数ではない場合、ｆ１＝ｆ０，ｑ＝ｆ０ｇ１として（ステップＳ１４）、次のステップへ。
２．ｆ２’ｇ１がｄｅｇ（ｆ２’ｇ１）≦ｎを満たすｐの最近多項式となるようなｆ２’を求める（ステップＳ２１）。
【００６８】
・ｆ２’が定数の場合、あるいは、‖ｆ２’ｇ１‖２＜‖ｑ‖２が成り立つ場合、（ｆ１，ｇ１，ｑ，‖ｑ−ｐ‖２）を返して終了（ステップＳ２３）。
【００６９】
・それ以外の場合、ｑをｆ２’ｇ１で置き換え、ｆ２＝ｆ２’／‖ｆ２’‖２として（ステップＳ２４）、次のステップへ。
３．ｆ２ｇ２がｄｅｇ（ｆ２ｇ２）≦ｎを満たすｐの最近多項式となるようなｇ２を求める（ステップＳ３１）。
【００７０】
・ｇ２が定数の場合、あるいは、‖ｆ２ｇ２‖２＜‖ｑ‖２が成り立つ場合、（ｆ２’，ｇ１，ｑ，‖ｑ−ｐ‖２）を返して終了（ステップＳ３３）。
【００７１】
・それ以外の場合、ｑをｆ２ｇ２で置き換え（ステップＳ３４）、次のステップへ。
４．‖ｆ２−ｆ１‖２＜εかつ‖ｇ２−ｇ１‖２＜εなら、（ｆ２，ｇ２，ｑ，‖ｑ−ｐ‖２）を返して終了（ステップＳ４２）。
【００７２】
そうでないなら、ｆ１をｆ２で、ｇ１をｇ２で置き換え（ステップＳ４３）、ステップＳ２へ。
【００７３】
≪注意２≫ステップＳ１でｇ１が定数の場合、そのまま処理を続けると、以下に書くように自明な分解（ｐ／‖ｐ‖２，‖ｐ‖２，ｐ，０）を返すことになるので、「不適」を返すこととしている。
【００７４】
実際、ステップＳ１でｇ１が定数の場合、そのまま処理を続けると、ステップＳ２でｆ２＝ｐ／‖ｐ‖２、ステップＳ３でｇ２＝‖ｐ‖２となり、ステップＳ４で結果を返す場合は、自明な分解（ｐ／‖ｐ‖２，‖ｐ‖２，ｐ，０）を返すことになる。もう一度ステップＳ２に戻る場合も、ｆ２＝ｐ／‖ｐ‖２、ステップＳ３でｇ２＝‖ｐ‖２となり、‖ｆ２−ｆ１‖＝‖ｇ２−ｇ１‖２＝０が成立して、やはり（ｐ／‖ｐ‖２，‖ｐ‖２，ｐ，０）を返すことになる。
【００７５】
また、ステップＳ２では、命題１より必ず‖ｆ２ｇ１‖２≧‖ｑ‖２が成立するはずである。これが逆向きの不等号になったのは、誤差のため計算の信頼性が失われ始めたためと判断し、一つ前の結果を出力して終了としている。ステップＳ３でも同様である。
【００７６】
≪注意３≫アルゴリズム１では、‖ｆ２−ｆ１‖２＜εかつ‖ｇ２−ｇ１‖２＜εのとき終了としたが、そのほかにもいろいろな終了条件が考えられる。例えば、ステップＳ２で‖ｆ２−ｆ１‖２＜εが成立するとき、あるいは、ステップＳ３で‖ｇ２−ｇ１‖２＜εが成立するとき終了とすることが考えられる。ステップＳ２で‖ｆ２ｇ１−ｑ‖２＜εが成立するとき、あるいは、ステップＳ３で‖ｆ２ｇ２−ｑ‖２＜εが成立するとき終了とすることも考えられる。そのほか，初期多項式ｆ０を変えて複数回アルゴリズムを走らせた結果のうち、一番よいものを採用してもよい．
【００７７】
≪具体例１≫
ｐ＝ｘ２＋ｙ２−１，ε＝１０-５として、以下のｆ０に対し上記のアルゴリズムを適用すると、以下の出力が得られる。
ｆ０＝０．７０７１０６８ｘ＋０．７０７１０６８のとき出力は、（０．７０７１０６８ｘ＋０．７０７１０６８，−１．４１４２１４ｙ＋１．４１４２１４，１．００００００ｙ２−７．１６６５７６×１０−１７ｙ−１．００００００，１．００００００）となる。
【００７８】
ｆ０＝０．５７７３５０３ｘ＋０．５７７３５０３ｙ＋０．５７７３５０３のとき出力は、（０．４４７２４９３ｘ＋０．４４７２４９３ｙ＋０．７７４５５５４，０．７４５３７０９ｘ＋０．７４５３７０９ｙ−１．２９０９７７，０．３３３３６６６ｘ２−５．７６５３５５×１０−５ｘｙ＋０．３３３３６６６ｙ２−５．７６５３５５×１０−５ｘ−５．７６５３５５×１０−５ｙ−０．９９９９３３４，１．１５４７０１）となる。
【００７９】
ｆ０＝０．８１６４９６６ｘ＋０．４０８２４８３ｙ＋０．４０８２４８３のとき出力は、（０．７０７１３７３ｘ＋７．８６９６４６×１０−４ｙ＋０．７０７０７５８，１．４１４２３２ｘ＋７．８６８７３７×１０−４ｙ−１．４１４１９２，１．００００５７ｘ２＋１．６６９３７９×１０−３ｘｙ＋６．１９２４１７×１０−７ｙ２−５．８３７３５４×１０−５ｘ−５．５６５３９７×１０−４ｙ−０．９９９９４１０，１．０００００１）となる。
【００８０】
≪具体例２≫
ｐ＝ｘ２＋ｙ２−１，ε＝１０−５として、以下のｆ０に対し上記アルゴリズムの終了条件をｆｊとｇｋの積ｆｊｇｋの変化分のノルムが閾値ε未満のとき終了、と変更したアルゴリズムを適用する。
【００８１】
ｆ０＝０．７０７１０６８ｘ＋０．７０７１０６８のとき出力は、（０．７０７１０６８ｘ＋０．７０７１０６８，−１．４１４２１４ｙ＋１．４１４２１４，１．００００００ｙ２−７．１６６５７６×１０−１７ｙ−１．００００００，１．００００００）となる。
【００８２】
ｆ０＝０．５７７３５０３ｘ＋０．５７７３５０３ｙ＋０．５７７３５０３のとき出力は、（０．４４７２４９３ｘ＋０．４４７２４９３ｙ＋０．７７４５５５４，０．７４５５９２４ｘ＋０．７４５５９２４ｙ−１．２９０７１６，０．３３３４６５７ｘ２＋０．６６６９３１４ｘｙ＋０．３３３４６５７ｙ２＋２．３０６８２７×１０−４ｘ＋２．３０６８２７×１０−４ｙ−０．９９９７３１２，１．１５４７０１）となる。
【００８３】
ｆ０＝０．８１６４９６６ｘ＋０．４０８２４８３ｙ＋０．４０８２４８３のとき出力は、（０．７０７１３７３ｘ＋７．８６９６４６×１０−４ｙ＋０．７０７０７５８，１．４１４２３２ｘ＋７．８６８７３７×１０−４ｙ−１．４１４１９２，１．００００５７ｘ２＋１．６６９３７９×１０−３ｘｙ＋６．１９２４１７×１０−７ｙ２−５．８３７３５４×１０−５ｘ−５．５６５３９７×１０−４ｙ−０．９９９９４１０，１．０００００１）となる。
【００８４】
［実施形態］
以下、上記アルゴリズムに対応する、この発明の一実施形態を詳細に説明する。
【００８５】
図１は、この発明による最近多項式算出装置の例の機能ブロック図である。図２及び図３は、この発明による最近多項式算出方法の例の流れ図である。
【００８６】
最近多項式算出装置は、第一演算部１、第二演算部２、第三演算部３、記憶部４、制御部５、終了条件判定部６、ランダム選択部７、最近判定部８を例えば含む。
【００８７】
最近多項式算出装置には、既約多項式ｐ、多項式ｆ０∈Ｋ［ｘ１，…，ｘｓ］及びεが与えられ、記憶部４に記憶される。ただし、１≦ｄｅｇ（ｆ０）＜ｄｅｇ（ｐ）、‖ｆ０‖２＝１、及びε＞０であるとする。例えば多項式ｆ０はランダム選択部７により、上記の条件を満たすようにランダムに選択される。
【００８８】
＜ステップＳ１＞
第一演算部１は、多項式ｆ０ｇ１がｄｅｇ（ｆ０ｇ１）≦ｎを満たし既約多項式ｐに最も近くなるような多項式ｇ１を求める（ステップＳ１１）。ここで、ｎ＝ｄｅｇ（ｐ）である。
【００８９】
第一演算部１は、例えば既約多項式ｐ及び多項式ｆ０についての正規方程式を解くことにより、多項式ｇ１を求めることができる。すなわち、Ｍ（ｆ０）＊Ｍ（ｆ０）ｖ（ｇ１）＝Ｍ（ｆ０）＊ｖ（ｐ）の関係を満たす多項式ｇ１を求める。上記したように、この関係を満たす多項式ｇ１は一意に定まり、多項式ｆ０ｇ１は多項式ｆ０を因子に持つ多項式の中で既約多項式ｐに最も近い多項式、すなわち既約多項式ｐの最近多項式となる。
【００９０】
ｄｅｇ（ｆ０）＋ｄｅｇ（ｇ１）≦ｎの関係を満たすように、ｇ１の全次数ｄｅｇ（ｇ１）を定める。例えば、ｎ−ｄｅｇ（ｆ０）をｄｅｇ（ｇ１）とする。定まった全次数ｄｅｇ（ｇ１）により、係数ａｊ１…ｊｓを用いて、多項式ｇ１を次のように記載することができる。ただし、ｊ１＋…＋ｊｓの最大値はｄｅｇ（ｇ１）である。
【００９１】
【数１４】
2011118806.tif 000016
【００９２】
例えば、各多項式をいわゆる次数付き辞書式順序に基づいて記載し、ベクトルｖ（・）の第ｍ行の成分が多項式・の第ｍ項の係数に対応しており、Ｍ（ｆ０）ｖ（ｇ１）の第ｍ行の成分が多項式ｆ０ｇ１の第ｍ項の係数に対応しているとする。このとき、行列Ｍ（ｆ０）の第ｍ行第ｋ列の成分は、多項式ｆ０に多項式ｇ１の第ｋ項から係数を除いたものをかけることにより求まった多項式の第ｍ項の係数である。
【００９３】
第一演算部１は、与えられた既約多項式ｐ、多項式ｆ０及び上記のように定めた多項式ｇ１により定まる正規方程式Ｍ（ｆ０）＊Ｍ（ｆ０）ｖ（ｇ１）＝Ｍ（ｆ０）＊ｖ（ｐ）を、ａｊ１…ｊｓについて解き、多項式ｇ１を求め、その計算結果を記憶部４に記憶する。
【００９４】
制御部５は、多項式ｇ１が定数かどうかを判定して（ステップＳ１２）、定数であれば「不適」として、処理を終える（ステップＳ１３）。一方、多項式ｇ１が定数でない場合には、制御部５はｆ１＝ｆ０、ｑ＝ｆ０ｇ１としてｆ１及びｑを記憶部４に記憶し（ステップＳ１４）、その後ステップＳ２１に進む。
【００９５】
＜ステップＳ２＞
第二演算部２は、記憶部４から読み込んだ既約多項式ｐ及び多項式ｇ１についての正規方程式を解くことにより、多項式ｆ２’ｇ１がｄｅｇ（ｆ２’ｇ１）≦ｎを満たし既約多項式ｐに最も近くなるような多項式ｆ２’を求める（ステップＳ２１）。
【００９６】
第二演算部２は、例えば既約多項式ｐ及び多項式ｇ１についての正規方程式を解くことにより、多項式ｆ２’を求めることができる。すなわち、Ｍ（ｇ１）＊Ｍ（ｇ１）ｖ（ｆ２’）＝Ｍ（ｇ１）＊ｖ（ｐ）の関係を満たす多項式ｆ２’を求める。この関係を満たす多項式ｆ２’は一意に定まり、多項式ｆ２’ｇ１は多項式ｇ１を因子に持つ多項式の中で既約多項式ｐに最も近い多項式、すなわち既約多項式ｐの最近多項式となる。
【００９７】
ｄｅｇ（ｆ２’）＋ｄｅｇ（ｇ１）≦ｎの関係を満たすように、ｆ２’の全次数ｄｅｇ（ｆ２’）を定める。例えば、ｎ−ｄｅｇ（ｇ１）をｄｅｇ（ｆ２’）とする。定まった全次数ｄｅｇ（ｆ２’）により、係数ａｊ１…ｊｓを用いて、多項式ｆ２’を次のように記載することができる。ただし、ｊ１＋…＋ｊｓの最大値はｄｅｇ（ｆ２’）である。
【００９８】
【数１５】
2011118806.tif 000017
【００９９】
例えば、各多項式をいわゆる次数付き辞書式順序に基づいて記載し、ベクトルｖ（・）の第ｍ行の成分が多項式・の第ｍ項の係数に対応しており、Ｍ（ｇ１）ｖ（ｆ２’）の第ｍ行の成分が多項式ｆ２’ｇ１の第ｍ項の係数に対応しているとする。このとき、行列Ｍ（ｇ１）の第ｍ行第ｋ列の成分は、多項式ｇ１に多項式ｆ２’の第ｋ項から係数を除いたものをかけることにより求まった多項式の第ｍ項の係数である。
【０１００】
第二演算部２は、与えられた既約多項式ｐ、多項式ｇ１及び上記のように定めた多項式ｆ２’により定まる正規方程式Ｍ（ｇ１）＊Ｍ（ｇ１）ｖ（ｆ２’）＝Ｍ（ｇ１）＊ｖ（ｐ）を、ａｊ１…ｊｓについて解き、多項式ｆ２’を求め、その計算結果を記憶部４に記憶する。
【０１０１】
制御部５は、多項式ｆ２’が定数かどうか又は‖ｆ２’ｇ１‖２＜‖ｑ‖２かどうか判定し（ステップＳ２２）、多項式ｆ２’が定数又は‖ｆ２’ｇ１‖２＜‖ｑ‖２であれば、（ｆ１，ｇ１，ｑ，‖ｑ−ｐ‖２）を出力して処理を終える（ステップＳ２３）。一方、多項式ｆ２’が定数又は‖ｆ２’ｇ１‖２＜‖ｑ‖２でなければ、制御部５はｑ＝ｆ２’ｇ１、ｆ２＝ｆ２’／‖ｆ２’‖２としてｑ及びｆ２を記憶部４に記憶し（ステップＳ２４）、その後ステップＳ３１に進む。
【０１０２】
＜ステップＳ３＞
第三演算部３は、記憶部４から読み込んだ既約多項式ｐ及び多項式ｆ２についての正規方程式を解くことにより、多項式ｆ２ｇ２がｄｅｇ（ｆ２ｇ２）≦ｎを満たし既約多項式ｐに最も近くなるような多項式ｇ２を求める（ステップＳ３１）。
【０１０３】
第三演算部３は、例えば既約多項式ｐ及び多項式ｆ２についての正規方程式を解くことにより、多項式ｇ２を求めることができる。すなわち、Ｍ（ｆ２）＊Ｍ（ｆ２）ｖ（ｇ２）＝Ｍ（ｆ２）＊ｖ（ｐ）の関係を満たす多項式ｇ２を求める。上記したように、この関係を満たす多項式ｇ２は一意に定まり、多項式ｆ２ｇ２は多項式ｆ２を因子に持つ多項式の中で既約多項式ｐに最も近い多項式、すなわち既約多項式ｐの最近多項式となる。
【０１０４】
ｄｅｇ（ｆ２）＋ｄｅｇ（ｇ２）≦ｎの関係を満たすように、ｇ２の全次数ｄｅｇ（ｇ２）を定める。例えば、ｎ−ｄｅｇ（ｆ２）をｄｅｇ（ｇ２）とする。定まった全次数ｄｅｇ（ｇ２）により、係数ａｊ１…ｊｓを用いて、多項式ｇ２を次のように記載することができる。ただし、ｊ１＋…＋ｊｓの最大値はｄｅｇ（ｆ２’）である。
【０１０５】
【数１６】
2011118806.tif 000018
【０１０６】
例えば、各多項式をいわゆる次数付き辞書式順序に基づいて記載し、ベクトルｖ（・）の第ｍ行の成分が多項式・の第ｍ項の係数に対応しており、Ｍ（ｆ２）ｖ（ｇ２）の第ｍ行の成分が多項式ｆ２ｇ２の第ｍ項の係数に対応しているとする。このとき、行列Ｍ（ｆ２）の第ｍ行第ｋ列の成分は、多項式ｆ２に多項式ｇ２の第ｋ項から係数を除いたものをかけることにより求まった多項式の第ｍ項の係数である。
【０１０７】
第一演算部１は、与えられた既約多項式ｐ、多項式ｆ２及び上記のように定めた多項式ｇ２により定まる正規方程式Ｍ（ｆ２）＊Ｍ（ｆ２）ｖ（ｇ２）＝Ｍ（ｆ２）＊ｖ（ｐ）を、ａｊ１…ｊｓについて解き、多項式ｇ２を求め、その計算結果を記憶部４に記憶する。
【０１０８】
制御部５は、多項式ｇ２が定数かどうか又は‖ｆ２ｇ２‖２＜‖ｑ‖２かどうか判定し（ステップＳ３２）、多項式ｇ２が定数又は‖ｆ２ｇ２‖２＜‖ｑ‖２であれば、（ｆ２’，ｇ１，ｑ，‖ｑ−ｐ‖２）を出力して処理を終える（ステップＳ３３）。一方、多項式ｇ２が定数又は‖ｆ２ｇ２‖２＜‖ｑ‖２でなければ、制御部５はｑ＝ｆ２ｇ２として、ｑを記憶部４に記憶し（ステップＳ３４）、その後ステップＳ４１に進む。
【０１０９】
＜ステップＳ４＞
終了条件判定部６は、記憶部４から読み込んだ多項式ｆ１，ｆ２，ｇ１，ｇ２が、‖ｆ２−ｆ１‖２＜εかつ‖ｇ２−ｇ１‖２＜εの終了条件を満たしているかを判定し（ステップＳ４１）、終了条件を満たす場合には、（ｆ２，ｇ２，ｑ，‖ｑ−ｐ‖２）を出力して処理を終える（ステップＳ４２）。この場合、多項式ｆ２ｇ２が、求めようとしていた既約多項式ｐに近い可約多項式となる。終了条件を満たさない場合には、ｆ１をｆ２で、ｇ１をｇ２で置き換え、すなわちｆ１＝ｆ２、ｇ１＝ｇ２として、ｆ１、ｇ１を記憶部４に記憶し（ステップＳ４３）、その後ステップＳ２１に進む。
【０１１０】
このように、多項式ｆ２で多項式ｆ１を、多項式ｇ２で上記多項式ｇ１を置き換えて、第二演算部２の処理及び第三演算部３の処理を繰り返すごとに、命題１により、求まる可約多項式は既約多項式ｐに近づくため、既約多項式ｐに必要なだけ近い可約多項式を求めることができる。
【０１１１】
従来の近似因数分解の手法は、与えられた多項式のごく近くに可約な多項式が存在することを利用して、その可約な多項式を求めている。そのために、可約な多項式が離れている場合に計算が不安定になる問題が生じる。一方、上記実施形態のように、与えられた多項式の近くに可約な多項式が存在するか否かに依存しない手法により可約な多項式を求めることにより、可約な多項式が離れている場合にも安定な計算を行うことができるようになる。
【０１１２】
上記の例では、‖ｆ２−ｆ１‖２＜εかつ‖ｇ２−ｇ１‖２＜εを終了条件としたが、他の条件を終了条件としてもよい。
【０１１３】
例えば、終了条件判定部６は、ステップＳ２１の後に、記憶部４から読み込んだｆ１，ｆ２’からｆ２＝ｆ２’／‖ｆ２’‖２を求め、終了条件‖ｆ２−ｆ１‖２＜εを満たすか判定して、この終了条件を満たす場合には、多項式ｆ２’ｇ１を既約多項式ｐに近い可約多項式として出力してもよい。また、終了条件判定部６は、ステップＳ３１の後に、記憶部４から読み込んだｇ１，ｇ２が終了条件‖ｇ２−ｇ１‖２＜εを満たすか判定して、この終了条件を満たす場合には、多項式ｆ２ｇ２を既約多項式ｐに近い可約多項式として出力してもよい。
【０１１４】
また、終了条件判定部６は、ステップＳ２１の後に、記憶部４から読み込んだｆ２’，ｇ１，ｑ（＝ｆ０ｇ１又はｆ２ｇ２）が、終了条件‖ｆ２’ｇ１−ｑ‖２＜εを満たすか判定して、この終了条件を満たす場合には、多項式ｆ２’ｇ１を既約多項式ｐに近い可約多項式として出力してもよい。また、終了条件判定部６は、ステップＳ３１の後に、記憶部４から読み込んだｆ２，ｇ２，ｑ（＝ｆ２’ｇ１）が、終了条件‖ｆ２ｇ２−ｑ‖２＜εを満たすか判定して、この終了条件を満たす場合には、多項式ｆ２ｇ２を既約多項式ｐに近い可約多項式として出力してもよい。
【０１１５】
すなわち、終了条件判定部６は、‖ｆ２−ｆ１‖２＜ε、‖ｇ２−ｇ１‖２＜ε、‖ｆ２’ｇ１−ｆ２ｇ２‖２＜εの少なくとも１つを終了条件として、終了条件を満たすと判定されるまで、多項式ｆ２で多項式ｆ１を、多項式ｇ２で多項式ｇ１を置き換えて第二演算部２の処理及び第三演算部３の処理を繰り返してもよい。‖ｆ２’ｇ１−ｆ２ｇ２‖２＜εの終了条件は、終了条件‖ｆ２’ｇ１−ｑ‖２＜εと、終了条件‖ｆ２ｇ２−ｑ‖２＜εとをまとめて記載したものである。
【０１１６】
また、終了条件を判定せずに、第二演算部２の処理及び第三演算部３の処理を所定の回数だけ繰り返して、その後ｆ２’ｇ１又は多項式ｆ２ｇ２を既約多項式ｐに近い可約多項式として出力してもよい。第二演算部２の処理を終えた後はｆ２’ｇ１を出力し、第三演算部３の処理を終えた後はｆ２ｇ２を出力する。
【０１１７】
また、ランダム選択部７が生成した異なる複数の多項式ｆ０のそれぞれについて、上記の第一演算部１、第二演算部２及び第三演算部３の処理を行うことにより、既約多項式ｐに近い可約多項式を複数求め、最近判定部８がそれらの求まった多項式の中で既約多項式ｐに最も近い多項式を出力してもよい。これにより、既約多項式ｐにより近い可約多項式を求めることができる可能性が高まる。
【０１１８】
最近多項式算出装置は、コンピュータによって実現することができる。この場合、この装置が有すべき各機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これ装置における各処理機能が、コンピュータ上で実現される。
【０１１９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１２０】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【０１２１】
１     第一演算部
２     第二演算部
３     第三演算部
４     記憶部
５     制御部
６     終了条件判定部
７     ランダム選択部
８     最近判定部
【図１】
2011118806.tif 000019
【図２】
2011118806.tif 000020
【図３】
2011118806.tif 000021