代数学特論 I 要約 No.12

今日前半のテーマ:

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

$$R=R_1\times R_2 \times R_3 \times \dots \times R_n$$

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

PID をイデアルで割ったような環についてはすでにもっと詳しい様子を知っている。

補題 12.2   任意の可換環 $R$ に対して,

$$\sqrt 0_R=\{x\in R ; x^n=0 \quad (\exists n \in {\mbox{${\Bbb Z}$}}_{>0})\}$$

は $R$ のイデアルである。 もし $R/\sqrt{0_R}$ が整域ならば、$R$ の巾等元は $0$ と $1$ のみである。

補題 12.3   $($既出$)$$S$ が PID で、 $e\in S\setminus \{0\}$ なら、

$$S/(e)\cong R_1\times R_2 \times \dots \times R_n$$

なる直積分解で、 $R_i/\sqrt{0_{R_i}}$ は体であるようなものが存在する。

補題 12.4   可換環 $R$ が $R=R_1\times R_2$ と直積分解されていたとすると, 任意の $R$-加群 $M$ は, $R$-加群としての直和分解

$$M=M_1\oplus 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,\dots,b_m,a_1,a_2\dots,a_n ,a_1,a_2,\dots,a_n,a_1,a_2,\dots,a_n,a_1,a_2,\dots$$

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

$$b_k=a_{2k}-a_k$$

とおくと, $b_l=b_{2l}=0$ となる $l$ が存在する。

整数係数の多項式 $f$ を決めて、

$$x_{i+1}=f(x_i) \text{(mod $p$)}$$

なる漸化式で定義される数列にこの手法を適用すると, $x=y \ (p)$ だが $x\neq y \ (n)$ なる $x,y$ がもとまって, $n$ の素因子が求まる場合がある。これを Pollard の $\rho$ 法という。

問題 12.1   $\rho$ 法またはその他の方法を用いて $n=7278202201270378983212653$ の素因数を求めよ。 使用した方法と, プログラム、および実行時間をそえること。

(参考) $\rho$ 法を 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 だけは今回は禁じ手とする。