整数論的アルゴリズムとその公開鍵暗号への応用に関する研究

数论算法研究及其在公钥密码中的应用

基本信息

批准号：
14780243
负责人：
金山直樹
金额：
$ 1.6万
依托单位：
Waseda University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2004
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14780243/
关键词：
公開鍵暗号超楕円曲線位数計算

项目摘要

Schoofは1985年に,有限体K上の楕円曲線Eに対してEのK有理点の全体E(K)の位数を計算する決定的多項式時間アルゴリズムを発表した。同じ年に,MillerとKoblitzにより独立に,有限体上の楕円曲線を利用した公開鍵暗号暗号が提案され,このパラメータ生成にSchoofのアルゴリズムが利用できる事知られ大きな注目を浴びた.有限体上の一般のアーベル多様体に対して同様のことが出来ないか,という自然な問題が生じてくるが,これについても既にいくつかの結果がある。まず,AdlemanとHuangは,種数2の有限体上の超楕円曲線を利用した素数判定法の提案のため,種数2の場合に,そのヤコビ群の位数計算のための確率的多項式時間アルゴリズムの存在を示した.次に,Pilaにより,一般の高次元のアーベル多様体においても(種数を固定して)有限体のサイズについての決定的多項式時間で動くアルゴリズムの存在が証明された.Pilaの群位数計算アルゴリズムの記述のためには,そのアーベル多様体の定義方程式と加法公式が明確な形で与えられていることを仮定している。種数2の代数曲線(これらは全て超楕円曲線である)のヤコビ多様体の定義方程式や加法公式については,GrantやFlynnが具体的に書き下している.研究代表者はGrantの定義方程式によって表現されてヤコビ多様体において等分多項式を用いた乗法倍公式をすでに導き出しているので、それを用いてSchoofの場合と全く同様に,定義方程式と加法公式,そして等分多項式を組み合わせて群位数を計算するアルゴリズムを書き下すことが可能となる.本研究では,Grantのモデルの下で,種数2の超楕円曲線のヤコビ群の位数を計算するアルゴリズムを提案し,その計算量についても考察した.

1985 年，Schoof 发表了一种确定性多项式时间算法，用于计算有限域 K 上的椭圆曲线 E 中 K 个有理点的总 E(K) 的阶数。同年，Miller 和 Koblitz 独立提出了在有限域上使用椭圆曲线的公钥密码学，当人们知道 Schoof 的算法可以用来生成参数时，它引起了很多关注。自然而然出现的问题是：是否有某种东西。对于的一般阿贝尔变体也可以做类似的事情，并且已经有一些关于这方面的结果。首先，Adleman和Huang提出了一种利用2格有限域上的超椭圆曲线来确定素性的方法。我们证明了该算法的存在性。接下来，我们使用Pila来解决一般高维阿贝尔簇的问题。证明了存在一种在有限域大小（属数固定）的确定性多项式时间内工作的算法，并假设定义方程和加法公式以显式形式给出。属 2 代数曲线（均为超椭圆曲线）的雅可比变体的定义方程和加法公式已由格兰特和弗林专门写下。由于我们已经导出了，所以主要研究者使用格兰特的定义方程来表达它们。使用雅可比行列式上的赤道多项式的乘法乘法公式，我们可以将其用作在本研究中，在格兰特模型下，可以通过结合定义方程、加法公式和赤道多项式来写出计算群阶的算法，就像我们在Schoof的情况下提出了计算雅可比行列式阶的算法一样。 2 型超椭圆曲线群，并讨论了其计算复杂性。