Analysis of Baby-Step Giant-Step Algorithms for Non-uniform Distributions

Koh-ichi NAGAO; Shigenori UCHIYAMA; Naoki KANAYAMA; Kazuto MATSUO

Analysis of Baby-Step Giant-Step Algorithms for Non-uniform Distributions

Koh-ichi NAGAO, Shigenori UCHIYAMA, Naoki KANAYAMA, Kazuto MATSUO

Full Text Views

0

Share
Cite this

Summary :

The baby-step giant-step algorithm, BSGS for short, was proposed by Shanks in order to compute the class number of an imaginary quadratic field. This algorithm is at present known as a very useful tool for computing with respect to finite groups such as the discrete logarithms and counting the number of the elements. Especially, the BSGS is normally made use of counting the rational points on the Jacobian of a hyperelliptic curve over a finite field. Indeed, research on the practical improvement of the BSGS has recently received a lot of attention from a cryptographic viewpoint. In this paper, we explicitly analyze the modified BSGS, which is for non-uniform distributions of the group order, proposed by Blackburn and Teske. More precisely, we refine the Blackburn-Teske algorithm, and also propose a criterion for the decision of the effectiveness of their algorithm; namely, our proposed criterion explicitly shows that what distribution is needed in order that their proposed algorithm is faster than the original BSGS. That is, we for the first time present a necessary and sufficient condition under which the modified BSGS is effective.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.1 pp.10-17

Publication Date: 2004/01/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Fundamental

Cite this

Copy

Koh-ichi NAGAO, Shigenori UCHIYAMA, Naoki KANAYAMA, Kazuto MATSUO, "Analysis of Baby-Step Giant-Step Algorithms for Non-uniform Distributions" in IEICE TRANSACTIONS on Fundamentals, vol. E87-A, no. 1, pp. 10-17, January 2004, doi: .
Abstract: The baby-step giant-step algorithm, BSGS for short, was proposed by Shanks in order to compute the class number of an imaginary quadratic field. This algorithm is at present known as a very useful tool for computing with respect to finite groups such as the discrete logarithms and counting the number of the elements. Especially, the BSGS is normally made use of counting the rational points on the Jacobian of a hyperelliptic curve over a finite field. Indeed, research on the practical improvement of the BSGS has recently received a lot of attention from a cryptographic viewpoint. In this paper, we explicitly analyze the modified BSGS, which is for non-uniform distributions of the group order, proposed by Blackburn and Teske. More precisely, we refine the Blackburn-Teske algorithm, and also propose a criterion for the decision of the effectiveness of their algorithm; namely, our proposed criterion explicitly shows that what distribution is needed in order that their proposed algorithm is faster than the original BSGS. That is, we for the first time present a necessary and sufficient condition under which the modified BSGS is effective.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e87-a_1_10/_p

Copy

@ARTICLE{e87-a_1_10,
author={Koh-ichi NAGAO, Shigenori UCHIYAMA, Naoki KANAYAMA, Kazuto MATSUO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Analysis of Baby-Step Giant-Step Algorithms for Non-uniform Distributions},
year={2004},
volume={E87-A},
number={1},
pages={10-17},
abstract={The baby-step giant-step algorithm, BSGS for short, was proposed by Shanks in order to compute the class number of an imaginary quadratic field. This algorithm is at present known as a very useful tool for computing with respect to finite groups such as the discrete logarithms and counting the number of the elements. Especially, the BSGS is normally made use of counting the rational points on the Jacobian of a hyperelliptic curve over a finite field. Indeed, research on the practical improvement of the BSGS has recently received a lot of attention from a cryptographic viewpoint. In this paper, we explicitly analyze the modified BSGS, which is for non-uniform distributions of the group order, proposed by Blackburn and Teske. More precisely, we refine the Blackburn-Teske algorithm, and also propose a criterion for the decision of the effectiveness of their algorithm; namely, our proposed criterion explicitly shows that what distribution is needed in order that their proposed algorithm is faster than the original BSGS. That is, we for the first time present a necessary and sufficient condition under which the modified BSGS is effective.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Analysis of Baby-Step Giant-Step Algorithms for Non-uniform Distributions
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 10
EP - 17
AU - Koh-ichi NAGAO
AU - Shigenori UCHIYAMA
AU - Naoki KANAYAMA
AU - Kazuto MATSUO
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2004
AB - The baby-step giant-step algorithm, BSGS for short, was proposed by Shanks in order to compute the class number of an imaginary quadratic field. This algorithm is at present known as a very useful tool for computing with respect to finite groups such as the discrete logarithms and counting the number of the elements. Especially, the BSGS is normally made use of counting the rational points on the Jacobian of a hyperelliptic curve over a finite field. Indeed, research on the practical improvement of the BSGS has recently received a lot of attention from a cryptographic viewpoint. In this paper, we explicitly analyze the modified BSGS, which is for non-uniform distributions of the group order, proposed by Blackburn and Teske. More precisely, we refine the Blackburn-Teske algorithm, and also propose a criterion for the decision of the effectiveness of their algorithm; namely, our proposed criterion explicitly shows that what distribution is needed in order that their proposed algorithm is faster than the original BSGS. That is, we for the first time present a necessary and sufficient condition under which the modified BSGS is effective.
ER -