NZMATH 1.2.0

The NZMATH development group is pleased to announce the availability of NZMATH 1.2.0. Some of the highlights of new feature of NZMATH version 1.2 are here:

• implementation of AKS (Cyclotomic congruence test) algorithm.
• new curves added for ECM algorithms.
• improvement multiple polynomial quadratic sieve.

For more details, Please read CHANGES.txt .

nzmath.arith1.log is faster than math.log

nzmath.arith1.log(n) is faster than int(math.log(n)) if base is 2:

$ python -m timeit -s 'import math' '[int(math.log(i, 2)) for i in range(1, 10000000, 1000)]'
10 loops, best of 3: 91.6 msec per loop
$ python -m timeit -s 'import nzmath.arith1' '[nzmath.arith1.log(i, 2) for i in range(1, 10000000, 1000)]'
10 loops, best of 3: 32.5 msec per loop

It's true also for base 10:

$ python -m timeit -s 'import math' '[int(math.log(i, 10)) for i in range(1, 1000000000, 100000)]'
10 loops, best of 3: 93.1 msec per loop
$ python -m timeit -s 'import nzmath.arith1' '[nzmath.arith1.log(i, 10) for i in range(1, 1000000000, 100000)]'
100 loops, best of 3: 16.5 msec per loop

It isn't fair if I stop here.

$ python -m timeit -s 'import math' '[int(math.log(i, 3)) for i in range(1, 1000000000, 100000)]'
10 loops, best of 3: 93.2 msec per loop
$ python -m timeit -s 'import nzmath.arith1' '[nzmath.arith1.log(i, 3) for i in range(1, 1000000000, 100000)]'
10 loops, best of 3: 121 msec per loop

Cornacchia

Iwao Kimura at Blogger の Cornacchia-Smithのアルゴリズム：mod 4で1の素数は2平方数の和という記事を読みました。 Cornacchia という名前に聞き覚えが(読み方は多分イタリア人なのでコルナッキア)あります。 そう確かあれは cubic_root モジュール。

あまりこのモジュールを使ったことがある、という人も多くないと思いますので、その紹介を簡単に。 平方剰余というのは有名ですが、3乗剰余というものもあるのです。 cubic_root モジュールはこの計算をします。 それ以外に Eisenstein 整域 \(\mathbb{Z}[\omega]\) での有理素数の因数分解や素数を法とする3乗根の計算なども提供しています。 この中に何故か、というかまあ実装の都合上ここに、cornacchia という関数があります。

cornacchia(d, p) で \(x^2 + d y^2 = p\) の解(の一つ)をタプルとして返します。 ということで早速使ってみましょう。

>>> import nzmath.cubic_root
>>> nzmath.cubic_root.cornacchia(1, 37)
(6, 1)

つまり \(6^2+1\times 1^2 = 37\) ということですね。

実装は H.Cohen の A Course in Computational Algebraic Number Theory を参考にしています。