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

摘要：

设合数阶有限循环群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算法一致,但空间复杂度更低.

关键词：离散对数问题;低Hamming重量;一般性算法

所属期刊栏目：8

分类号：TP309.7(计算技术、计算机技术)

资助基金：国家自然科学基金;国家重点研发计划;山东省重大科技创新工程

在线出版日期：2021-09-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：444-451