2017-09-06

ポラードのp-1因数分解法

整数論

大きな合成数を素因数分解(factorization in prime numbers)するアルゴリズムの一つにポラードのp-1法があります。
ポラードの $\rho$ (ロー)法とは別モノなので混同しないようにしましょう。

因数分解したい合成数をnとします。
$n=p \times q$ の時、素数pを求めたいです。qはとりあえず合成数としておきます。
ある整数mがp-1の倍数であると仮定します(mの選び方はあとで考えます) 。
kを1以上の整数とすると、
$m = (p-1) k$
aとpが違いに素であれば(aの選び方はあとで考えます)、フェルマーの小定理を使うと、
$a^{m} = a^{ (p-1) k} = {(a^{p-1})}^k = 1^{k} = 1\mod p$ となり、

$(a^{m}\mod p) - 1 = h$ はpで割り切れます。
一方、nもpで割り切れますので、hとnの最大公約数(greatest common divider)
$gcd(h, n) = g$ はpで割り切れます。
gが1より大きくnより小さい場合は、gはnの因数であることが分かります。
gが1やnになった場合はmの選び方が悪いので別の値を使って再チャレンジします。
これを繰り返せば、素因数分解を完了させることができます。

mはどうやって選べばよいでしょうか。
p-1の倍数になればよいので、ある整数cとして、以下の最小公倍数(least common multiple)を考えます。
m = lcm(2, 3, 4, 5, ..., c)
このように素因数をできるだけ多く含むようにしておけば、p-1の倍数になりやすいと言えるでしょう。
mがp-1の倍数になりにくくするには、
p-1がB-power-smooth(B-smooth と B-power-smooth - Pebble Coding)である時のBの値が大きければよいです。
つまり、p-1が大きな素数因数を含めばよいということです。

a,mの値を変えながらgcdの値を計算していきますが、
計算量が少なくて済むようにa,mともに小さい値から試していきます。
aはpと違いに素であれば良いので、通常2を使い、Bを少しづつ大きくしていくようです。
Bを大きくするとmの値が大きくなっていきます。

参考:

http://www.maroon.dti.ne.jp/fermat/factor3.html

http://www.math.mcgill.ca/darmon/courses/05-06/usra/charest.pdf

2017-09-03

体の標数(characteristic)

群環体

体Kにおいて、n個の1の和
1+1+...+1
が0となるような整数が存在するとき、その最小値を体Kの標数といい、ch(K)と表します。
いくつ加えても0にならない時は標数が0と定めます。
標数は0か素数です。
有理数体Qの標数は0です。
有限体 $F_{p}$ の標数はpです。

2017-09-03

体の拡大

群環体

拡大体

体とは大雑把に言って、加法と乗法に対して演算が閉じている数の集合のことを指します。

有理数Q, 実数体R, 複素数体Cは全て加法と乗法において演算が閉じているので体と呼べます。

これらは数の集合としては数の存在の密度が高すぎますね。
整数Zと複素数体Cの中間くらいの数の密度の体って作れないものでしょうか。

例えば、a,bを整数として、 $a + b \sqrt {2}$ の集合を考えてみると、
整数よりちょっとしか密度が高くなっていないですし、なにか面白い性質があるかもしれません。
他にも、c,dを有理数として、 $c + d \sqrt {2}$ の集合なんかも良さそうです。
ちょっとひねって、e, fを整数として、 $e + f \sqrt {-1}$ の集合を考えることができます。

さらにひねって、 g,hを整数とし、 $\alpha = \frac {-1 \pm \sqrt {3} i} {2} とすると、 g + \alpha h$ の集合を考えることもできます。

これらは全て体となります。

b, d, f, hを0とすれば、元になる体に戻ります。

このように既存の体に要素を追加しても体になっており、かつ元の体の元を全て含んでいる体を拡大体と呼びます。

これらは全て、元の数が無限個で複雑です。

有限体の拡大

元の数が有限個の体も考えたいですね。
整数に対して素数pで割った余りの集合{0, 1, 2, ..., p-1}は加法、乗法に対して演算が閉じており、体となることが知られています。
素数でない場合は乗算が閉じないので体とはなりません。

これを素体と呼び $F_p$ (pは素数) と表します。
素体も拡大してみましょう。

a, b を素体 $F_p$ の元、 $\alpha = \frac {-1 + \sqrt {3} i} {2}$ として $a + \alpha b$ の集合を考えます。
このとき $\alpha$ に対しては素数で割った余りという概念が使えませんので、剰余演算の対象外とします。
ただし、この $\alpha$ は
${\alpha}^{2} = { ( \frac {-1 + \sqrt {3} i} {2} ) }^{2} = \frac {-1 - \sqrt {3} i} {2} = - {\alpha} - 1$
の関係を満たしますので、
${\alpha}$ の２乗が現れたらこの値に置き換えるという規則を設けることにします。

p=2の場合は、a,bは2で割った余りなので、0または1しかありません。
なので、拡大体の元は
$0 + \alpha 0 = 0$
$1 + \alpha 0 = 1$
$0 + \alpha 1 = \alpha$
$1 + \alpha 1 = 1 + \alpha$
の４つとなります。

一般にa,bは0からp-1までp通りあるので、元の数は $p^{2}$ となります。

このように拡大した体を $F_{ p^{2}}$ と表します。
ここでは ${\alpha} ^2 + {\alpha} + 1 = 0$ を満たす値 $\alpha$ を使って拡大しました。

さらに、 ${\beta} ^ 3 + {\beta} ^2 + {\beta} + 1 = 0$ を満たす値 $\beta$ を使って
$a + b {\beta} + c {\beta}^2$ の集合に対して、
$\beta$ が３乗以上になった時、 ${\beta} ^3 = - {\beta} ^2 - {\beta} - 1$ を使って置き換えることにします。
この拡大の元の数は $p^{3}$ となります。この拡大体を $F_{ p^{3}}$ と表します。

同じようにして拡大体 $F_{ p^{n}}$ を作れます。
このnのことを素体の拡大次数と呼びます。

素体を拡大した体は代数的にはこれしかないことが知られています。

例えば、
${\alpha} ^2 + {\alpha} + 1 = 0$ を満たす $\alpha$ と
${\beta} ^ 3 + {\beta} ^2 + {\beta} + 1 = 0$ を満たす $\beta$
を使って、
$a + b {\alpha} + c {\beta}^{2} + d {\beta} + e {\alpha} {\beta}^{2} + f {\alpha} {\beta}$ 式(A)
を2で割った余りを考えた時のこの体の元の数はどうなるでしょうか？
元は
0
1
${\alpha}$
${\beta}^2$
${\beta}$
${\alpha} {\beta}^2$
${\alpha} {\beta}$
$1 + {\alpha}$
$1 + {\beta}^2$
$1 + {\beta}$
$1 + {\alpha} {\beta}^2$
$1 + {\alpha} {\beta}$
...
$1 + {\alpha} + {\beta}^{2} + {\beta} + {\alpha} {\beta}^2 + {\alpha} {\beta}$
のようになります。
量が多いので途中を省略しましたが、この元の数を数えることは、式(A)の6つの項の2種類の組み合わせ
を列挙することです。つまり元の数は $2^{6} = 64$ となります。
これは、
$1 + {\alpha} + {\alpha}^{2}+ {\alpha}^{3}+ {\alpha}^{4}+ {\alpha}^{5}+ {\alpha}^{6} = 0$
を満たす ${\alpha}$ を使った場合と同じと考えられます。
(厳密にはこの式ではダメかもしれません。重解を持たない多項式を使う必要があります。)
なのでどうやら素体を拡大したものは $F_{ p^{n}}$ の形のものしかないと考えて良さそうです。

2017-09-02

C/C++/ObjC メモリ破壊系バグのつぶし方その2

C++11

前回
C/C++/ObjC メモリ破壊系バグのつぶし方その1 - Pebble Coding
の続きです。

落ちる原因はいくつかパターンが決まっていますが、例を上げてみます。

ヒープアロケートしていない領域に書き込む

初期化していないポインタに対して、ヒープアロケートせずデータを書き込もうとしています。

#include <stdio.h>
#include <string.h>

typedef struct {
    int   x1; 
    char* x2; 
} Data;

static int f(){
    Data d;
    d.x1 = 1;
    memset(d.x2, 0, 32);
    return 1;
}

int main(int argc, char** argv){
    f();
    return 0;
}

~$ ./a.out
Segmentation fault: 11

ここではSegmentation faultで落ちてくれましたが、もっと複雑なソースの場合でリリースビルドで最適化が入ると、
関数の戻る位置がおかしくなり、単純に処理がスキップされたりします。

これを防ぐには、構造体のメンバがアドレス変数いわゆるポインタの場合は全て0で初期化することです。

以下は、メモリ破壊系バグではなく動作未定義バグと言えますが、記載しておきます。

printfの引数不一致

#include <stdio.h>
int main(int argc, char** argv){
    printf("hoge", 1); 
}

このコードは大抵の場合、おかしな動作をすることもなく動きますが、
リリースビルドで最適化オプションがついたとき、おかしな動作をする時があります。
リリースビルドでしか再現しないバグなんて最悪です。
-Wallオプションを指定し、全てのコンパイラワーニングを有効にしてコンパイルし、
出てきたワーニングでやばいものを全て潰しましょう。
macOSの環境ではデフォルトでこのオプションが付いているようです。

~$ gcc a.c
a.c:3:20: warning: data argument not used by format string [-Wformat-extra-args]
    printf("hoge", 1); 
           ~~~~~~  ^
1 warning generated.
~$ ./a.out
hoge~$

-wオプションをつけてワーニングを無効にしてみるとメッセージが何も出ません。恐ろしいです。

~$ gcc a.c -w
~$

余談ですが、これから新規でプログラムを書く方は、
動作未定義などという狂った仕様を持つC/C++は使わずに、Rustやモダンな言語を使いましょう。
クリティカルな速度が要求されないならGCを持つ言語を使いましょう。

詳解 Objective-C 2.0 第3版

作者: 荻原剛志
出版社/メーカー: SBクリエイティブ
発売日: 2011/12/23
メディア: 単行本
購入: 14人クリック: 98回
この商品を含むブログ (25件) を見る

プログラミングRust

作者: Jim Blandy,Jason Orendorff,中田秀基
出版社/メーカー: オライリージャパン
発売日: 2018/08/10
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

2017-09-01

約数記号

整数論

整数 a が整数 b を割り切るとき $a \mid b$ と書きます。

例:
$2 \mid 4$
$3 \mid 12$
$2 \mid 26$
整数 a が整数 b を割り切らないとき $a \nmid b$ と書きます。

例:
$2 \nmid 13$
$5 \nmid 12$
$2 \nmid 9$
$a \mid b$ であるとき、b は a の倍数であり、a は b の約数であるといいます。