2011年連合発表会
「数論アルゴリズムとその応用」 (JANT) 講演要旨

数論システム NZMATH の有効活用について (1)
○中村 憲, 宮本 泰徳, 平野 正樹(首都大学東京)

我々が開発している数論システム NZMATH の性能を評価する為に, これ迄に実装した各種数論アルゴリズムの性能を, 他システムによるものと比較する. 入力データのサイズや実行環境による差異等, 色々な側面から検証する. それにより NZMATH の上手な活用法を探る. 今回は主に基本算法と初等数論アルゴリズムを扱う.

Elliptic Divisibility Sequence を用いた素因数分解アルゴリズム
○鑓水淳一、櫻田尚寿、小椋直樹、内山成憲(首都大学東京)

楕円曲線の等分多項式の持つ性質と同様の性質を持つ数列としてElliptic Divisibility Sequence（以下、EDS） と呼ばれるものがある。ここでは、この EDS を用いた素因数分解アルゴリズムを提案し、その実装や高速化などについても述べる。

３変数多項式環の自己同型のtame性判定アルゴリズムの実装について
○原田諭、宮本泰徳、小椋直樹、黒田茂、内山成憲(首都大学東京)

多項式環の自己同型がtameであるとは、 アフィン自己同型と基本自己同型と呼ばれる単純な形の自己同型の合成写像であるときにいう。1972年に永田は３変数多項式環のある自己同型を構成し、それがtameではないと予想した。その予想は30年もの間未解決であったが、2003年にShestakovとUmirbaevにより肯定的に解決された。
その後、黒田は Shestakov 等の理論を再構築し、自己同型が tame であるかどうか判定するための方法を改良した。そして、この判定法をもとに、実装可能な形のアルゴリズムを与えた。本発表では、黒田によるアルゴリズムを実装し、実験した結果について報告する。

楕円曲線 y^2=x^3+n のある族のモーデルヴェイユ群について
奈良忠央(東北大学)

これは y^2=x^3+n のかたちのある楕円曲線の族のモーデルヴェイユ群についての研究です。それらはある明示的な３つの整数点をもち、それらは独立になっています。そしてそのうち、どの２点もモーデルヴェイユ群の自由部分の基底の一部として使えることを、標準高さの計算を用いて示します。日大の藤田育嗣氏との共同研究です。

実二次体上至る所 good reduction を持つ楕円曲線の非存在性について
○横山 俊一, 島崎 有(九州大学)

実二次体上至る所 good reduction を持つ楕円曲線の非存在性については、保型性予想の観点からも有用なため多数の先行研究があるものの、計算機的問題ゆえに未解決のケースが数多く残されている。 今回、その中から新しく非存在性が判明したものが見つかったので、これについて報告する。

正規化された Miller 関数を用いたペアリングの計算についての注意
小椋 直樹 (首都大学東京 D2), 内山 成憲 (首都大学東京), ○金山 直樹 (筑波大学), 岡本 栄司 (筑波大学)

本発表では，Ateペアリング$a(Q,P)$のような拡大体有理点Qから有理関数を構成しそれに点Pそのものを代入するペアリングについて、ペアリング計算のためのMillerのアルゴリズムの標準的な実装に対し，その中のMiller関数の正規化について考察を行う．BN曲線等の現在標準的に用いられている楕円曲線を使用した場合は，Millerのアルゴリズムの標準的な実装の中で，Miller関数の正規化はかならずしも必要ではないことを示す．一方，Miller関数の正規化が必要となるような特殊な楕円曲線が存在することも示す．

F2-線形擬似乱数発生法の最適化のための高速格子簡約アルゴリズム
原瀬 晋(東京大学)

(部分的に松本眞氏、斎藤睦夫氏との共同研究)
擬似乱数を評価する規準の一つとして、高次元均等分布性が用いられる。メルセンヌツイスター法を含む二元体上の線形擬似乱数発生法に対しては、上位ビットの均等分布の次元を具体的に計算することが可能であり、擬似乱数の出力列から構成したある格子の簡約基底を求める問題(二元体係数冪級数体の数の幾何)に帰着される。本講演では、新しいアルゴリズムを導入し、均等分布の次元計算の高速化について述べる。この方法は、Couture-L'Ecuyerによる双対格子を用いた改良よりも計算量が減少することを計算機実験と合わせて紹介する。

問い合わせ先

内山成憲 (首都大学東京)
uchiyama-shigenori(at)tmu.ac.jp