2次持ち上げ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/10 16:16 UTC 版)
1次持ち上げは法 I n {\displaystyle I^{n}} での因数分解を法 I n + 1 {\displaystyle I^{n+1}} での因数分解に持ち上げるものであった。2次持ち上げでは法 I 2 n {\displaystyle I^{2n}} での因数分解に一気に持ち上げる。しかし、ベズーの等式の持ち上げも必要になり、（上述の1次持ち上げでは）法I での計算だけで済んだが法 I n {\displaystyle I^{n}} での計算が必要になるため、追加の計算コストがかかる。 どちらの方法でも大きなN に対して法 I N {\displaystyle I^{N}} まで持ち上げることができる。例えば N = 2 k {\displaystyle N=2^{k}} の場合に法 I N {\displaystyle I^{N}} まで因数分解を持ち上げるためには、1次持ち上げを使うとN − 1 回の反復計算が必要になるが、2次持ち上げを使えばk − 1 回の反復計算で済む。しかし、2次持ち上げを使う方法では扱わなければならない係数のサイズが計算中に増大していく。これは、一番いい持ち上げの方法は、N の値やR の性質、使用する乗算アルゴリズム、ハードウェアの特性などの状況に依存することを意味する[要出典]。 2次持ち上げは次の性質を利用する。 ある正の整数 k に対して因数分解 h ≡ α f g ( mod I k ) {\displaystyle h\equiv \alpha fg{\pmod {I^{k}}}} があったとし、f と g はモニック多項式で、ある a , b ∈ R [ X ] {\displaystyle a,b\in R[X]} が存在し a f + b g ≡ 1 ( mod I k ) {\textstyle af+bg\equiv 1{\pmod {I^{k}}}} が成り立つという意味で法Ikで互いに素だったとする。このとき、ある多項式 δ f , δ g ∈ I k R [ X ] {\displaystyle \delta _{f},\delta _{g}\in I^{k}R[X]} が存在し、 deg δ f < deg f {\displaystyle \deg \delta _{f}<\deg f} かつ deg δ g < deg g {\displaystyle \deg \delta _{g}<\deg g} かつ h ≡ α ( f + δ f ) ( g + δ g ) ( mod I 2 k ) {\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g}){\pmod {I^{2k}}}} が成り立つ。さらに f + δ f {\displaystyle f+\delta _{f}} と g + δ g {\displaystyle g+\delta _{g}} は次の形のベズーの等式 ( a + δ a ) ( f + δ f ) + ( b + δ b ) ( g + δ g ) ≡ 1 ( mod I 2 k ) {\displaystyle (a+\delta _{a})(f+\delta _{f})+(b+\delta _{b})(g+\delta _{g})\equiv 1{\pmod {I^{2k}}}} を満たす（つまり2次持ち上げの反復計算を行うための前提が満たされる）。 証明: 最初の主張は1次持ち上げをk = 1 でI の代わりにイデアル I k {\displaystyle I^{k}} に対して適用することでわかる。 α = a f + b g − 1 ∈ I k R [ X ] {\displaystyle \alpha =af+bg-1\in I^{k}R[X]} と置く。次の式 a ( f + δ f ) + b ( g + δ g ) = 1 + Δ {\displaystyle a(f+\delta _{f})+b(g+\delta _{g})=1+\Delta } が、 Δ = α + a δ f + b δ g ∈ I k R [ X ] {\displaystyle \Delta =\alpha +a\delta _{f}+b\delta _{g}\in I^{k}R[X]} と置くことで成り立つ。2つの多項式を δ a = − a Δ {\displaystyle \delta _{a}=-a\Delta } と δ b = − b Δ {\displaystyle \delta _{b}=-b\Delta } で定めると ( a + δ a ) ( f + δ f ) + ( b + δ b ) ( g + δ g ) = 1 − Δ 2 ∈ I 2 k R [ X ] {\displaystyle (a+\delta _{a})(f+\delta _{f})+(b+\delta _{b})(g+\delta _{g})=1-\Delta ^{2}\in I^{2k}R[X]} が成り立つ。これで2番目の主張も証明できた。
※この「2次持ち上げ」の解説は、「ヘンゼルの補題」の解説の一部です。
「2次持ち上げ」を含む「ヘンゼルの補題」の記事については、「ヘンゼルの補題」の概要を参照ください。
- 2次持ち上げのページへのリンク
