计算合数阶群中低重量离散对数的低存储算法

摘要

设合数阶有限循环群G=G1×G2,其中2n-1＜|G|≤2n,p是|G1|的最大素因子.对于Hamming重量为 δn的离散对数问题,其中 δ ∈(0,1),May和Ozerov给出了时间复杂度为?(√p+√|G2|H(δ))、空间复杂度为?(√|G2|H(δ))的一般性算法.为了降低空间复杂度,本文给出了计算合数阶群中低Hamming重量离散对数的低存储算法.基于启发式假设,该算法的时间复杂度为?(√p+√G2|2H(δ)-H(Φ(δ)))、空间复杂度为O(1).进一步,我们给出算法的并行版本.当我们将空间复杂度提高至?(|G2|H(δ)-H(Φ(δ))时,时间复杂度可以降低至?(√p+√|G2|H(δ)和May-Ozerov算法一致,但空间复杂度更低.