Baby Step Giant Step Algorithms in Point Counting of Hyperelliptic Curves
スポンサーリンク
概要
- 論文の詳細を見る
Counting the number of points of Jacobian varieties of hyperelliptic curves over finite fields is necessary for construction of hyperelliptic curve cryptosystems. Recently Gaudry and Harley proposed a practical scheme for point counting of hyperelliptic curves. Their 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 search for the order by a square-root algorithm. In particular, the parallelized Pollard's lambda-method was used as the square-root algorithm, which took 50CPU days to compute an order of 127 bits. This paper shows a new variation of the baby step giant step algorithm to improve the square-root algorithm part in the Gaudry-Harley scheme. With knowledge of the residue modulo m of the characteristic polynomial of the Frobenius endomorphism of a Jacobian variety, the proposed algorithm provides a speed up by a factor m, instead of √<m> in square-root algorithms. Moreover, imple-mentation results of the proposed algorithm is presented including a 135-bit prime order computed about 15 hours on Alpha 21264/667 MHz and a 160-bit order.
- 社団法人電子情報通信学会の論文
- 2003-05-01
著者
-
Tsujii Shigeo
Graduate School Of Information Security Institute Of Information Security:research And Development I
-
Tsujii Shigeo
Department Of Information & System Engineering Chuo University
-
Matsuo Kazuto
Graduate School Of Information Security Institute Of Information Security:research And Development I
-
Tsujii S
Graduate School Of Information Security Institute Of Information Security:research And Development I
-
CHAO Jinhui
Dept. of Information and System Engineering, Chuo University
-
MATSUO Kazuto
Research and Development Initiative, Chuo University
-
CHAO Jinhui
Department of Electrical, Electronic and Communication Engineering, Chuo University
-
Chao Jinhui
Department Of Electrical And Electronic Engineering Faculty Of Science And Engineering Chuo Universi
関連論文
- Dually-Perturbed Matsumoto-Imai Signature (DPMS) Scheme
- Security Enhancement of Various MPKCs by 2-Layer Nonlinear Piece in Hand Method
- Proposal for Piece in Hand Matrix : General Concept for Enhancing Security of Multivariate Public Key Cryptosystems(Discrete Mathematics and Its Applications)
- A Subspace Blind Identification Algorithm with Reduced Computational Complexity : Colored Noise Case(Digital Signal Processing)
- A Practical Subspace Blind Identification Algorithm with Reduced Computational Complexity : Colored Noise Case
- A Practical Subspace Blind Identification Algorithm with Reduced Computational Complexity(Digital Signal Processing)
- On Ambiguity in Coppersmith' Attacking Method against NIKS-TAS Scheme (Special Section on Cryptgraphy and Information Security)
- Improvements of Addition Algorithm on Genus 3 Hyperellipic Curves and Their Implementation(Public Key Cryptography)(Cryptography and Information Security)
- Baby Step Giant Step Algorithms in Point Counting of Hyperelliptic Curves
- On Waveform Equalization and its Economical Profit in Optical Fiber PCM Transmission System
- Analysis of Baby-Step Giant-Step Algorithms for Non-uniform Distributions (Fundamental) (Cryptography and Information Security)
- Realization of Geometric Illusions Using a Lateral-Inhibitive Shifting Model and Intrinsic Geometry of Subjective Visual Space
- Robust noise suppression algorithm using the only Kalman filter theory for white and colored noises (Speech) -- (国際ワークショップ"Asian workshop on speech science and technology")
- Robust Noise Suppression Algorithm with the Kalman Filter Theory for White and Colored Disturbance
- Robust noise suppression algorithm using the only Kalman filter theory for white and colored noises
- A CGM APPROACH TO SUBSPACE BASED BLIND CHANNEL IDENTIFICATION
- An Extension of GHS Weil Descent Attack(Public Key Cryptography)(Cryptography and Information Security)
- Invariant Extraction and Segmentation of 3D Objects Using Linear Lie Algebra Models(Regular Section)
- A secure ID based authenticated key agreement scheme with pairing(情報通信基礎サブソサイエティ合同研究会)
- A secure ID based authenticated key agreement scheme with pairing(情報通信基礎サブソサイエティ合同研究会)
- A secure ID based authenticated key agreement scheme with pairing(情報通信基礎サブソサイエティ合同研究会)