代数学特論 I 要約 NO.12

今日前半のテーマ:

ネータ環の直積分解と加群

補題 12.1. 可換ネータ環 R があたえられているとする。このとき, R の直積分解

R = R_{1} × R_{2} × R_{3} × ⋯ × R_{n}

で、各直和因子 R_{i} の巾等元は 1 と 0 のみであるようなものが存在する。

PID をイデアルで割ったような環についてはすでにもっと詳しい様子を知っている。補題 12.2. 任意の可換環 R に対して,

\sqrt{0}_{R} = \{x ∈ R; x^{n} = 0 (∃n ∈ ℤ_{>0})\}

は R のイデアルである。もし R/\sqrt{0_{R}} が整域ならば、 R の巾等元は 0 と 1 のみである。補題 12.3. ( 既出 ) S が PID で、 e ∈ S \ {0} なら、

S/(e) ≅ R_{1} × R_{2} × ⋯ × R_{n}

なる直積分解で、 R_{i}/\sqrt{0_{R_{i}}} は体であるようなものが存在する。補題 12.4. 可換環 R が R = R_{1} × R_{2} と直積分解されていたとすると, 任意の R-加群 M は, R-加群としての直和分解

M = M_{1} ⊕ M_{2}

で、 R の M への作用がこの直和分解によって対角の形

(r_{1}, r_{2}).(m_{1}, m_{2}) = (r_{1}.m_{1}, r_{2}.m_{2})

に書けるようなものをもつ。

PID S に対して, S-加群がどのような構造をもつかが、単因子論の話題であった。

後半では素因数分解の効率化について考えたい。 n を素因数分解する一番原始的な方法は、 2 から\sqrt{n} までの整数で順次割っていく方法である。ただしこれでは\sqrt{n} に比例する時間がかかる。 (手法 1) 最初の m 個を除いて有限個の数を繰り返す数列

b_{1}, b_{2}, …, b_{m}, a_{1}, a_{2} …, a_{n}, a_{1}, a_{2}, …, a_{n}, a_{1}, a_{2}, …, a_{n}, a_{1}, a_{2}, …

が与えられているとする。このとき,

b_{k} = a_{2k} − a_{k}

とおくと, b_{l} = b_{2l} = 0 となる l が存在する。整数係数の多項式 f を決めて、

x_{i+1} = f(x_{i})(mod p)

なる漸化式で定義される数列にこの手法を適用すると, x = y (p) だが x ≠ y (n) なる x, y がもとまって, n の素因子が求まる場合がある。これを Pollard の ρ 法という。問題 12.1. ρ 法またはその他の方法を用いてn = 7278202201270378983212653 の素因数を求めよ。使用した方法と, プログラム、および実行時間をそえること。

(参考) ρ 法を UBASIC で書くと次のようになる。 (ただし、プログラムを複雑にするのを避けるために若干効率の悪いプログラムにしてある。興味のある人は改良するか、自分で一から書いてみること。 )

10  n=607143768775207   ' 分解する数
30  a=1:b=1        ' a=x_i, b=x_{2i} のつもりである。
50  while 1        ' ここから wend (150 行) まで無限ループ
60    a=fnf(a)@n
70    b=fnf(fnf(b))@n
80    x=gcd(a-b,n)
90    if x<>1 then print x,n  :end
150 wend
160 end
1000 def fnf(k)   ' fnf() 関数の定義; fn... はユーザ定義関数
1010 return(k*k+1)   ' もちろんほかの関数でもよい。

ubasic などのプログラム言語を使ったことがないひとは、講義のホームページから ubasic をダウンロードし, ubasic を解凍したあとそのフォルダにメモ帳などで上記プログラムを書いて、 ”rho.txt” などに保存し, そのあと ubasic を起動して, load ”rho.txt” とすればよいだろう。講義のページには数式処理ソフト mupad もおいてあるので, それを使ってもよろしい。ただし,mupad の ifactor 関数を用いるとさすがに簡単すぎるので、 ifactor だけは今回は禁じ手とする。