首页    期刊浏览 2024年11月07日 星期四
登录注册

文章基本信息

  • 标题:Complexity Reduction of the Baby-Step Giant-Step Algorithm
  • 本地全文:下载
  • 作者:Fahad Alhasoun ; M. A. Matin
  • 期刊名称:International Journal of Computer Science and Network Security
  • 印刷版ISSN:1738-7906
  • 出版年度:2011
  • 卷号:11
  • 期号:5
  • 页码:210-216
  • 出版社:International Journal of Computer Science and Network Security
  • 摘要:The security of cryptosystems depends on the hardness and difficulty of solving the discrete log problem. One of the well known algorithms to solve the discrete log problem is the Baby-Step Giant-Step Algorithm. This algorithm has ��n space and time complexities in the cyclic multiplicative group Zn. In this paper, a modified algorithm is proposed to reduce the space complexity by 50% the algorithm uses properties of 0 function in order to decide what elements are useless for the algorithm. The proposed algorithm of the Baby-Step Giant-Step Algorithm has n time complexity and n/2 space complexity to find a solution for the discrete log problem in the cyclic multiplicative group Zn. The proposed algorithm can find a solution with time complexity of n/2 if it runs with a space complexity of n meaning it will run twice as fast as the conventional algorithm with the same space complexity.
  • 关键词:Cryptosystems; cryptography; discrete log problem; Baby-Step Giant-Step Algorithm; Cyclic Multiplicative Groups
国家哲学社会科学文献中心版权所有