科研之友
微信
新浪微博
Facebook
分享链接
摘要
设合数阶有限循环群G=G1×G2,其中2n-1<|G|≤2n,p是|G1|的最大素因子.对于Hamming重量为δn的离散对数问题,其中δ∈(0,1),May和Ozerov给出了时间复杂度为■、空间复杂度为■的一般性算法.为了降低空间复杂度,本文给出了计算合数阶群中低Hamming重量离散对数的低存储算法.基于启发式假设,该算法的时间复杂度为■、空间复杂度为O(1).进一步,我们给出算法的并行版本.当我们将空间复杂度提高至■时,时间复杂度可以降低至■,和May-Ozerov算法一致,但空间复杂度更低.
- 单位
