Difficulty of calculation of discrete logarithm for any arbitrary Field is the basis for security of several popular cryptographic solutions. Pohlig-Hellman method is a popular choice to calculate discrete logarithm in finite field $F_p^*$. Pohlig-Hellman method does yield good results if p is smooth ( i.e. p-1 has small prime factors). We propose a practical alternative to Pohlig-Hellman algorithm for finding discrete logarithm modulo prime. Although, proposed method, similar to Pohlig-Hellman reduces the problem to group of orders $p_i$ for each prime factor and hence in worst case scenario (including when p=2q+1 , q being another prime) order of run time remains the same. However in proposed method, as there is no requirement of combining the result using Chinese Remainder Theorem and do the other associated work ,run times are much faster.


翻译:难以计算任意字段的离散对数是若干流行加密解决方案安全的基础。 Pohlig- Hellman 方法是计算有限字段的离散对数的流行选择 $F_ p ⁇ $。 Pohlig- Hellman 方法如果p 平滑( 即 p-1 有小主要因素 ), 确实会产生良好的效果 。 我们建议了比 Pohlig- Hellman 算法更实用的替代算法, 以寻找离散对数元元。 虽然, 与 Pohlig- Hellman 类似的方法, 将问题降低到每个质因子的单价 $p i, 从而在最坏的情况下( 包括当 p=2q+1, q 是另一个主数) 运行时间顺序仍然相同 。 但是, 在拟议方法中, 没有要求使用中文保留论和做其它相关工作的结果组合, 运行时间要快得多 。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
80+阅读 · 2020年9月28日
专知会员服务
52+阅读 · 2020年9月7日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
还在修改博士论文?这份《博士论文写作技巧》为你指南
MIT新书《强化学习与最优控制》
专知会员服务
273+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
8+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【论文】深度学习的数学解释
机器学习研究会
10+阅读 · 2017年12月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年6月15日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
80+阅读 · 2020年9月28日
专知会员服务
52+阅读 · 2020年9月7日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
还在修改博士论文?这份《博士论文写作技巧》为你指南
MIT新书《强化学习与最优控制》
专知会员服务
273+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
8+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【论文】深度学习的数学解释
机器学习研究会
10+阅读 · 2017年12月15日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员