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 を参考にしています。