ネギ式

適当に生きるおっさんのブログ

数学:余り物には福がある

余談:(整係数)多項式因数分解はちゃんと勉強したと思っていたが、復習してみたら、なんか見覚えないことがいろいろ出てきた。途中までやって放り出したのかも知れない。(よくあること)

本題:そんなに本題じゃない気もするが。「ユークリッドの互除法」がなら、「余り付き割り算」天使である。だいたいこの重要な計算に「余り付き割り算」とかいう長い名前が付いているのがおかしい。もっと一言で表す言葉があって当然である。コンピュータのプログラムでも、余りを求める演算と、商を求める演算が別々にあって、両方を求めるには2回演算をしなければならないのがおかしい。1回の演算で商と余りの両方を返す演算があるべきだ。(最近のイケてる言語ならあるかも知れない)

だいたい、余り付き割り算は小学生の割り算という印象があるのがおかしい。重要な計算なのに。

多項式因数分解をコンピュータで行うには、有限体というものを使うとよい。有限体というと難しいようだが、ここで使うのは素数で割った余りだ。2で割った余りとか、3で割った余りの世界。6とか12で割った余りではない。有限体にはもっと別のタイプのものもあるが、それは多項式因数分解では、とりあえず使わなくても済む。

それから多項式多項式で割った余りも使う。こちらは素数に対応する既約多項式でなくてもいい。単純にある多項式で割った余り。

整数係数多項式を有限体係数多項式の世界に持っていく。それには係数を素数で割ればよい。のだが、この計算は整数係数多項式を入力として、有限体係数多項式を出力する関数と考えることが出来る。別の言い方をすると写像である。そしてこの写像は1対1の写像ではなくて、多対1の写像である。最終的にやりたいのは整数係数多項式因数分解なので、最後にはこの写像を逆にして整数係数多項式を得たいわけだ。でも多対1の写像なので、簡単には元に戻らない。

整数係数多項式の世界⇨有限体係数多項式の世界、その世界で因数分解する⇨整数係数多項式の世界に戻す。(少なくとも最後の段階に難しさがある)

それはともかく、素数で割った余りの世界といってもどの素数で割るかを決めなくてはならない。それは簡単で、因数分解したい多項式最高次の係数の約数ではない素数(のなかで一番小さい素数)を選べばいい。最高次の係数が1なら2、2なら3を選べばいい。(余りの世界なので最高次の係数の余りが0になるような素数を選ぶと、次数が下がって都合が悪い)

と思っていたのだが、英語版wikipediaを見たら、奇数の素数が前提になっていた。(2の場合でも大丈夫とは書いてあったが、細かいやり方は奇素数のものだった)

あとのことはあとで考えるとして、整数係数多項式の世界⇨有限体係数多項式の世界という部分で重要なことは、もとの世界で因子(因数分解の要素となるもの。括弧のついた多項式)だったものは、転生後の世界でも因子であるということである。これが重要な性質で、あまりにも重要なので、数学を知っている人はそれだけで何万字も数学の話をしてしまうだろう。

しかし、この性質も逆は成り立たない。転生後の世界で因子だとしても転生前に戻した時には因子ではないことがある。でもこれはそんなに問題ではない。元の世界に戻してから、元の多項式を割ってみて割り切れなければ違うというだけである。

だいたい一回に書ける量が(気力、体力的に。アニメも見なきゃならんし)このくらいなので、今日はおわり。