第5回「代数学と計算」研究集会(AC2003)アブストラクト

On Systems of Polynomial Equations with Indeterminate Exponents

生成元の項に現れる指数が一般の形(変数)の場合、イデアルの構造が安定化 するかどうか、つまり、変数がある値より大きい場合に、グレブナー基底が一定 の形になるかどうか、は非常に面白い問題である。この問題への最初の試みとし て、より特殊な場合を設定し、安定性を考察する。

スクリプト言語による計算数論システムの開発

今までの計算数論システムは C などのコンパイラ言語で書かれることが多かっ たが、新しい計算機環境への対応など数学以外の部分での努力が要求された。 開発にスクリプト言語を使うことにより、このような部分は言語の開発者に任 せて我々は数学に専念できる。具体的には現在 Python を使ったシステムの開 発を進めており、その現状の紹介を行なう。

統計学にあらわれる代数計算

A new algorithm for computing ideal class groups of abelian number fields

We propose a new method of computing ideal class groups of abelian number fields using Gauss sums and cyclotomic units. A feature of our method resides in the explicit description of the generator of an ideal in plus part using Euler system.

非斉次有理近似アルゴリズムについて

(1)擬素数. Euler 擬素数, 強擬素数に関する幾つかの注意
(2) 拡張フェルマテストあるいは円分環テストの展開

Miller-Rabinの素数判定テストについて

Miller-Rabinの素数判定テストについては、Millerの定理といわれている注目 すべき結果がある (N.Koblitz (桜井幸一訳)p.190 あるいは R.Crandall and C.Pomerance:Prime Numbers p.129 Th.3.4.12参照)。この定理について、この 定理はMiller-Rabinテストに対する定理ではなく、より弱いテストであるEuler テストについての定理であることを注意し、それではMiller-Rabinテストに対 してはどうなるのかについて実験的考察を話したい。

Computation of integral and S-integral points on curves of genus one, especially of elliptic curves I *

Non-Supersingular Elliptic Curves for Pairing-based Cryptosystems

This talk concerns the use of non-supersingular elliptic curves in pairing-based cryptosystems. More precisely, it suggests: a selection of cyclic point groups on non-supersingular elliptic curves for pairing-based cryptosystems and a construction of non-degenerate bilinear maps from the cyclic groups to finite fields, and proposes: candidate collections of one way functions and several evidences of the onewayness.

ヴェイユペアリングを用いたグループ署名

グループ署名は，グループに属するメンバの誰もが グループの代表として署名することを可能とするディジタル署名方式である． グループ署名においては，署名文の正当性を検証することは， 誰にでも可能であるが，署名者の匿名性は保持される． ただし，署名に問題が生じた場合に備えて，グループの管理者は， 署名者の特定を行うことが可能である．グループ署名においては、 管理者以外の者にとって複数の署名が同一の署名者によって生成 されたか否かの判定を行うことが困難であることが求められている。 本発表ではグループ署名の概要と, 筆者等が提案した ヴェイユペアリングを用いたグループ署名方式を紹介する．

On Optimal Superimposed Codes

Computation of integral and S-integral points on curves of genus one, especially of elliptic curves II *

Elliptic curves --- the cross-roads of theory and computation

Computing in the Jacobian of a $C_{34}$ curve

巡回的なFp-有理点群をもつ楕円曲線のパラメトリックな構成について

効率的なモンゴメリ型楕円曲線のスカラ倍演算

モンゴメリ型楕円曲線には、ワイヤーシュトラス型楕円曲線より、 演算が高速という利点がある。楕円曲線暗号の主要演算は、スカラ倍演算である。 それには、楕円曲線暗号の固定のベース点のスカラ倍演算も含まれる。 ワイヤーシュトラス型楕円曲線には、固定点の予備計算テーブルを用いて、 高速化する方法が知られている。しかし、その方法をモンゴメリ型楕円曲線には、 拡張できない。本稿では、モンゴメリ型楕円曲線で、 初めて、予備計算テーブルを用いた高速なスカラ倍演算方法を提案する。 提案法は、(テーブル量を除いて、)従来法より、1.6倍高速である。

ユークリッド空間の tight 4-デザインについて

ユークリッド空間 ${\mathbf R}^n$ の単位球 面 $S^{n-1}$ 上の有限個の点からなる集合 $X$ について，\\ \noindent ``高々 $t$ 次の任意の多項式に対してその球面 $S^{n-1}$ 上での積分はその $X$ 上で の値の平均値に置き換えることができる" 時に集合 $X$ は球面上の $t$-デザインと呼ばれる (Delsarte-Goethals-Sedel(1977))． Neumaier と Seidel はこの概念を拡張してユークリッド空間上の $t$-デザイン の定義を与えた (1988)． すなわち $X\subset {\mathbf R}^n$ に対して，高々 $t$-次の任意の多項式 $f(x)$ が $$\sum_{i=1}^p\frac{\omega(X_i)}{|S_i|}\int_{S_i}f(x)d\sigma_i(x) =\sum_{x\in X}\omega(x)f(x)$$ を満たす時に $X$ をユークリッド空間上の $t$-デザインであると定義する． ここで $\{S_i,\ 1\leq i \leq p\}$ は集合 $X$ と共有点を持つ原点を中心 とする同心球面 の集合， $|S_i|$ は 球面 $S_i$ の面積，$X_i=X\cap S_i$, そして $w:X\rightarrow {\bf R}_{>0}$ は $X$ 上 のウェイト関数とする． この講演ではウェイト関数が定数である場合にユークリッド 空間の4-デザインで tight であるものの分類を与える．またウェイト関数が定数でない場合について も考察する．

貫通直線探索法による実射影平面上８直線アレンジメントの生成実験

本研究の目的は、実射影平面上８直線アレンジメントの分類に ある。発表者の一人である、関口はシンプルな直線配置行列に 対する$E_n$型Weyl群との関係を示し、分類の可能性を示唆した。 本研究では、計算幾何学で知られている、与えられた線分を 全て貫通する直線の探索アルゴリズムを利用し、異なる１４ 種類の７直線配置行列サンプルから、可能な全ての辺を貫通 する８直線アレンジメントを生成し、幾何学的特徴を整理した。 その結果、多角形隣接関係が異なる１３５通りの配置を観測 した。また、１つの直線を除いた部分７直線配置とWeyl群に よる分類の考察から８直線配置とWeyl群との関係に重要な 配置例の発見や幾何学的特徴を観測した。

Complete coset weight distributions of non-self dual binary code

形式的検証技術: Logical Framework と Modal Logic *

Modal Logics for Coalgebras -- A Survey

The notion of coalgebra is an abstraction of state-based systems such as automata and Kripke models. Modal logic has proved to be useful as a specification language for behaviors of coalgebras. There are some different approaches taken by different authors; the aim of this presentation is to give a brief overview of them.

A preliminary study on domains excluding weak-extensionality

A bijective CPS-translation between classical and intuitionistic proofs

The term CPS-translation, in general, denotes a program translation method into continuation-passing style that is the meaning of the program as a function taking the rest of the program. The method has been studied for program transformation, definitional interpreter, or denotational semantics. According to Griffin, a CPS-translation corresponds to a logical embedding from classical logic into intuitionistic logic under the Formulae-as-Types correspondence. Parigot introduced the $\lambda\mu$-calculus from the viewpoint of classical logic, and established an extension of the Curry-Howard isomorphism. We show that the novel CPS-translation due to Hofmann-Streicher is complete for second order $\lambda\mu$-calculus with $(\eta)$-rule, which gives proof terms of second order classical logic. For this, we introduce a universe of the translation, which is closed under reduction rules, and also a context-free grammar that describes the universe. Then it is syntactically proved that the CPS-translation is sound and complete by defining an inverse translation from the universe. The inverse translation, in fact, forms a bijection between the universe and $\lambda\mu$-calculus, under the equivalence relations induced by the reduction rules. This result is a carried over version of the paper presented at the 6th TLCA (Typed Lambda Calculi and Applications) 2003, which proved that the CPS-translation is sound and complete for type free $\lambda\mu$-calculus.

数列の添加によるブロックサイファーの強化

ブロックサイファーを用いて平文を暗号化する時に, 各ブロックに送信者・受信者の共有する数列を 添加してから変換する. 復号後には数列部分が正しく 復元されていることを確認してからそれを切り捨てて もとの平文を得る. これにより, 次のような効果があげられる: (1) 差分解読法, 線形解読法などの既知の平文を用いた攻撃に強い. (2) ブロックの順序が変わっても数列部分の順序を用いて復元できる. (3) ブロックの抜けが検知できる. (1)は送信者側のみが知る数列 (乱数列でも良い)を添加しても 得られる効果であるが、(2)(3)は共有した数列を添加して初めて 得られる効果である。

Explicit upper bounds for |L(1,χ)| for primitive characters χ *

The aim of this lecture is to prove the following fully explicit result: \begin{theorem} Let $S$ be a given finite set of pairwise distinct rational primes. Then, for any primitive Dirichlet character $\chi$ of conductor $q_\chi >1$ we have $$\Bigl\vert\Bigl\{ \prod_{p\in S} (1-{\chi (p)\over p}) \Bigr\}L(1,\chi )\Bigr\vert \le {1\over 2} \Bigl\{ \prod_{p\in S} (1-{1\over p}) \Bigr\} \Bigl (\log q_\chi\ +\kappa_\chi +\omega \log 4 +2\sum_{p\in S} {\log p\over p-1}\Bigr ) +o(1),$$ where $$\kappa_\chi =\cases{ \kappa_{even} =2+\gamma -\log (4\pi) =0.046191\cdots&if $\chi (-1)=+1$\cr \kappa_{odd} =2+\gamma -\log\pi =1.432485\cdots&if $\chi (-1)=-1$,\cr}$$ where $\omega\ge 0$ is the number of primes $p\in S$ which do not divide $q_\chi$, and where $o(1)$ is an explicit error term which tends rapidly to zero when $q_\chi$ goes to infinity. Moreover, if $S =\emptyset$ or if $S =\{2\}$, then this error term $o(1)$ is always less than or equal to zero, and if none of the prime in $S$ divides $q_\chi$ then this error term $o(1)$ is less than or equal to zero for $q_\chi$ large enough. \end{theorem}

連分数展開の無限和表現アルゴリズム II

Fundamental systems of units for some families of number fields We exhibit the unit group of certain composita of two parametric cubic fields.

We will first introduce results of different authors concerning explicit fundamental systems of units for some parametric families of number fields of degree 2, 3, 4, 5, 6, 8, 10, 12. Then we will exhibit the unit group of certain composita of two parametric cubic fields.

リンク:

第5回「代数学と計算」研究集会

「代数学と計算」ホームページ