• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>4th International Conference on Cryptology in India; Dec 8-10, 2003; New Delhi, India >Counting Points on an Abelian Variety over a Finite Field
【24h】

Counting Points on an Abelian Variety over a Finite Field

机译：在有限域上对阿贝尔品种的点计数

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Matsuo, Chao and Tsujii have proposed an algorithm for counting the number of points on the Jacobian variety of a hyper-elliptic curve over a finite field. The Matsuo-Chao-Tsujii algorithm is an improvement of the 'baby-step-giant-step' part of the Gaudry-Harley scheme. This scheme consists of two parts: firstly to compute the residue modulo a positive integer m of the order of a given Jacobian variety, and then to search for the actual order by a square-root algorithm. In this paper, following the Matsuo-Chao-Tsujii algorithm, we propose an improvement of the square-root algorithm part in the Gaudry-Harley scheme by optimizing the use of the residue modulo m of the characteristic polynomial of the Frobenius endomorphism of an Abelian variety. It turns out that the computational complexity is O ( q~(4g-2+i~2-i/8)/m~(i+1/2)), where i is an integer in the range 1 ≤ i ≤ g. We will show that for each g and each finite field F_9 of q = p~n elements, there exists an i which gives rise to the optimum complexity among all three corresponding algorithms.
机译：Matsuo，Chao和Tsujii提出了一种算法，用于计算有限域上超椭圆曲线的Jacobian变种上的点数。 Matsuo-Chao-Tsujii算法是对Gaudry-Harley方案的“婴儿步-巨型步”部分的改进。该方案包括两个部分：首先计算给定雅可比变量阶数的正整数m的模余数，然后通过平方根算法搜索实际阶数。本文根据Matsuo-Chao-Tsujii算法，通过优化Abelian Frobenius同态特征多项式的残差模的使用，提出了对Gaudry-Harley方案中平方根算法部分的改进品种。事实证明，计算复杂度为O（q〜（4g-2 + i〜2-i / 8）/ m〜（i + 1/2）），其中i是1≤i≤g范围内的整数。我们将证明，对于q = p〜n个元素的每个g和每个有限域F_9，都存在一个i，这会在所有三个相应算法中引起最佳复杂度。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号