多項式の次数を半分にする方法

質問

与えられた多項式 f(x) が 8, 10, 12 次のとき
　f(x) = c * (g_2(x))^d * h(g_1(x) / g_2(x))
　　　　(ただし, d は g(x) の次数で, 4～6, c は定数)
を満たすような g_1(x), g_2(x), h(x) を見つけられるか否かを
判定するアルゴリズムはありますでしょうか？
また、見つけられると判定された場合、
その求め方のアルゴリズムがございましたら教示願います。
　（f(x)は一目では相反多項式とは判別できないケースでお願いします。
　　相反多項式に帰着できないものは、上記の問題は不可能となるのでしょうかね・・・？）
　Generalized Lucas数, Lhemer数を snfs 法で分解可能か否か判定するために必要となります。

回答No.5

178-tall

始末記を若干。

　　P(x) = x^8 + p7*x^7 + p6*x^6 + p5*x^5 + p4*x^4 + p3*x^3 + p2*x^2 + p1*x + p0
　　h(t) = t^4 + h3*t^3 + h2*t^2 + h1*t + h0
　　 t = (x^2 + a)/(bx)
　として、
　　P(x) = h(t)*(bx)^4
　を満たす条件？

[偶部]
　　p0 = a^4
　　(p2 -4a^3)/a^2 = p6-4a = A2b^2
　　p4-6a^2 - 2aA2b^2 = A0b^4
二番目の (p2 -4a^3)/a^2 = p6-4a が成り立つなら、A2b^2, A0b^4 を得る。

[奇部]
　　p7 = p1/a^3 = A3b
　　p5 - 3ap7 = (p3 - 3p1/a)/a = A1b^3
　左側の等式ペアが成り立つなら、A3b, A1b^3 を得る。

…当然ながら、キツイ制約です。

お礼

助言有難う御座います。

アプローチの仕方を少し変えて、h(t)に代入する側の式を
予め式変形することから考察してみました。

当初の
t = (x の二次式) / (x の二次式)　・・・ (1)
に対し
u = (x^2 + a) / x　・・・ (2)
から
t = (c1 * u + c0) / (d1 * u + d0)　・・・ (3)
なる代入操作にて(1)へ変形できるかどうかを探っていましたら

u = (x^2 + a) / (x + b)　・・・ (4)
または
u = (x + a)^2　・・・ (5)
という形からなら(1)の形へ変形できる事が見えてきましたので
それを利用しようと思います。
((2)の形からは、(1)へは変形できない様でした。
その分複雑度が跳ね上がるみたいですが)

・・・しかし、試しにそのまま数式処理ソフトへ突っ込んでみましたら
エライことになってました。（そもそも、その行為自体が問題かもしれませんね）

回答No.4

178-tall

[訂正]　x^4 係数の符号 (+ が正しい)
　　P(x) = x^8 - 2*x^7 + 40*x^6 - 74*x^5 + 366*x^4 - 222*x^3 + 360*x^2 - 54*x + 81
から

[逆算例]　t や h(t) の「係数群」を求めてみました。(整係数)
(1)　h(t) = t^4 - t^3 + 7*t^2 - 7*t + 9
　　　t = (x^2 + 3)/(2x)
(2)　h(t) = t^4 - 2t^3 + 28*t^2 - 56*t + 144
　　　t = (x^2 + 3)/x

t = (x^2 + a)/(bx) の形は冗長らしい。
t = (x^2 + a)/x で良さそう。

回答No.3

178-tall

g_1/g_2 の分母子ともに二次多項式だと、h(t) や t = g_1/g_2 の復元は目途立たず。
…ならば、たとえば回路屋さんが頻用する「リアクタンス関数」では？

[例]　h(t) = t^4 - t^3 + 7*t^2 - 7*t + 9
　　　t = (x^2 + 3)/(2x)
として
　　P(x) = h(t) * (2x)^4
とすれば、
　　P(x) = x^8 - 2*x^7 + 40*x^6 - 74*x^5 - 366*x^4 - 222*x^3 + 360*x^2 - 54*x + 81

「リアクタンス関数」だと P(x) と h(t) の偶・奇対応が一目瞭然。
未定係数の勘定から t や h(t) の「係数群」を求められそう。
適用範囲が狭まるけど定数分離は容易、ということ。

回答No.2

178-tall

次数関係、了解しました。
> d は g(x) の次数
を誤読していたようで…。

アナログ系なので、
>多項式の次数を半分にする
…から、Newton → Bairstow の力技的拡張 (実係数多項式を半分次数の二式積に分解) を考えてましたが、整係数向きじゃなさそうですね。
離散系は "all Greek to me" ながら、興味あるので "ROM" に転向します。

言い訳のみにて、蒙御免。

補足

すみません.
> d は g(x) の次数
確かにこれですと, d は g_1(x) 若しくは g_2(x) の次数と
捉えてしまいますね・・・.

正しくは
　d は h(t) の次数
でした.

ちなみに, 定数 c は今まで何も言及していませんが,
有理数であることを言っておくべきでしたね.

題意の指摘につきまして有難う御座います.

回答No.1

178-tall

「見つけられるか」以前の問題で申訳ありません…けど、次数関係は？

たとえば f(x) が 8 次、d=4 なら、
　f = x^8 + A7*x^7 + … + A1*x + A0
　　= (g2)^4 * {(g1/g2)^4 + B3*(g1/g2)^3 + … + B1*(g1/g2) + B0}
だということでしょうか？
これだと、g2 は 2 次になりそうだけど (if any .... ) 。

補足

題意は, ご指摘の通りでございます.

今, 気づきましたが, h(x) は h(t) と書くべきだったかもしれません.

逆から追いかけますと, たとえば
　h(t) = t^4 - t^3 + 7*t^2 - 7*t + 9
　g_1(x) = x^2 - 2*x + 5
　g_2(x) = x^2 + 3*x - 7
として
f(x) = g_2(x)^4 * h(g_1(x)/g_2(x))
とすれば
　f(x) = 9*x^8 + 68*x^7 + 220*x^6 - 747*x^5 - 3703*x^4 + 3633*x^3 + 33688*x^2 - 73916*x + 43689
となりますが, 上記の逆で
任意の f(x) に対し, h(t) の次数が f(x) の次数の半分になるような
h(t), g_1(x), g_2(x) の組み合わせが存在するか否か
また, 存在する場合は効率的な h(t), g_1(x), g_2(x) の
求め方を探しています.

あと, いい忘れておりましたが, f(x), g_1(x), g_2(x), h(t) は
すべて有理整係数多項式を前提としております.

snfs法を適用可否を判定するため, さらに h(t) の各係数は
3 桁程度を上限に調整できれば尚良いです.

gnfs法を適用する場合であれば, 多項式選択ツールを適用すれば
いいだけなのですが，分解できる桁数を考えるとsnfs法が適用できる
範囲を多くしたいわけです.