factor 20100914: 2 137 73361

今日はじめて知ったんですが、linuxにはfactorという素因数分解をするコマンドが標準であります。
macにはありませんが sudo port install coreutils すれば gfactor という名前で使えます。

$ gfactor 12
12: 2 2 3
$ gfactor 100
100: 2 2 5 5
$ gfactor 2134097
2134097: 7 7 97 449

普通に速いです。infoによれば

Factoring the product of the eighth and ninth Mersenne primes takes
about 30 milliseconds of CPU time on a 2.2 GHz Athlon.

M8=`echo 2^31-1|bc` ; M9=`echo 2^61-1|bc`
/usr/bin/time -f '%U' factor $(echo "$M8 * $M9" | bc)
4951760154835678088235319297: 2147483647 2305843009213693951
0.03

Similarly, factoring the eighth Fermat number 2^256+1 takes about 20
seconds on the same machine.

ということらしいです。

アルゴリズムは

Factoring large prime numbers is, in general, hard. The Pollard Rho
algorithm used by `factor' is particularly effective for numbers with
relatively small factors. If you wish to factor large numbers which do
not have small factors (for example, numbers which are the product of
two large primes), other methods are far better.

とうことでこれのようです。

余談ですけどソース一瞬見たら

static const unsigned char wheel_tab[] =
  {
#include "wheel.h"
  };

としていてcsvなデータを読みこんでいたんですが、この方法って本当に使われてたんですね(驚)。

それにしてもなんでこのコマンドcoreutilsに含まれてるんだ…。