代数曲線のセコビ多様体に関するアルゴリズムとその公開鍵暗号への応用についての研究

代数曲线Secobi流形算法研究及其在公钥密码中的应用

• 批准号: 03J05882
• 负责人: 金山 直樹
• 金额: $ 2.11万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-03J05882/
• 关键词: 代数曲線暗号; 超楕円曲線; ヤコビ多様体; 位数計算; Ray Class Field; 単数; テータ関数; 素因子; 素因数分解; アルゴリズム; 格子; 楕円曲線; 群位数

今年度は、有限体上定義された種数2の超楕円曲線のヤコビ多様体の群位数計算アルゴリズムの具体的構成に取り掛かった。有限体上の楕円曲線上の離散対数問題の計算量的困難性に安全性の根拠を置く「楕円曲線暗号」は安全性・効率ともに優れた公開鍵暗号であるが、暗号に適した曲線を探索するには、楕円曲線の位数計算(元の個数を数える)アルゴリズムを用いる。楕円曲線の代わりに種数2以上の曲線を利用した「代数曲線暗号」を設計しようとするならば、曲線のヤコビ多様体の群位数計算を実行するアルゴリズムが必要である。このアルゴリズムを構成するには、ヤコビ多様体の定義方程式、加法公式そして倍算公式が必要である。定義方程式と加法公式は1990年にGrantによって与えられ、倍算公式は2003年に研究代表者によって与えられた。今年度は、それらを道具として群位数計算アルゴリズムの構成に着手した。理論的には、楕円曲線のときのアルゴリズムの手順と同様であるが、種数2以上の場合は加法X+Yを計算するためにはXとYの性質の違いによる場合わけをせねばならず、そのため楕円曲線の場合と比べ極めて煩雑なアルゴリズムとなり計算機に実装するには大変不便なものとなる。しかし、数値実験により、上のような場合分けは実際は殆ど必要ないことがわかり、(確率的アルゴリズムとなるが)かなり簡単になることが分かった。現在は、簡略化されたアルゴリズムを書き下し実装作業を行いつつ発表準備をしている段階である。

This year, the number of units defined on the finite body is 2. The number of positions in the multi-body group is calculated, and the specific data are selected. The difficulty of calculating the number of scattered data on the surface of a finite body. The root of the problem is to set the "security" code "security", "security", "security Use the algebraic curve code to design the number of data sets and calculate the number of multi-body group digits to calculate the number of necessary data. The definition equation, the addition formula, the multiplication formula. Define equation "addition formula" 1990 "Grant formula" and double formula "2003" research representative "formula" and "formula". This year, the number of props is calculated and the number of bits is calculated. The theoretical and experimental results show that the computer is the same as the computer, and the number of data is more than 2. The calculation is based on the addition of the number of two or more. The calculation results show that there are significant differences in the performance of the computer, such as the computer, the computer and the computer. Please do not know if it is necessary to make sure that it is necessary to make sure that you do not know what to do. Now, we are going to install the operation management table in order to improve the performance of the operation.

项目成果

Prime divisors of special values of theta functions in the ray class field of a certain quartic field modulo$2'n$

某个四次域模 $2n$ 的射线类域中 theta 函数特殊值的素因数

• 发表时间: 2005
• 作者: Takashi Fukuda;Naoki Kanayama;Keiichi Komatsu
• 通讯作者: Keiichi Komatsu

長尾孝一(Koh-ichi NAGAO): "Analysis of Baby-Step Giant-Step Algorithms for Non-uniform Distributions"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. Vol.E87-A No.1. 10-17 (2004)

Koh-ichi NAGAO：“非均匀分布的 Baby-Step Giant-Step 算法的分析”IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences Vol.E87-A No.1 (2004)。