大步小步算法

✍ dations ◷ 2025-12-09 07:21:58 #自2020年4月需要从俄语维基百科翻译的条目,算法,群论

在群论中，大步小步算法（英语：baby-step giant-step）是丹尼尔·尚克斯（英语：Daniel Shanks）发明的一种中途相遇算法，用于计算离散对数或者有限阿贝尔群的阶。其中离散对数问题在公钥加密领域有着非常重要的地位。

许多常用的加密系统都基于离散对数极难计算这一假设——计算越困难，这些系统提供的数据传输就越安全。增加离散对数计算难度的一种方法，是把密码系统建立在更大的群上。

这是一种空间换时间（英语：space–time tradeoff）的算法，实质上是求解离散对数的朴素算法（枚举并试乘）的一个相当简单的改进。

给出一个 $n {\displaystyle n}$ $n$ 阶循环群 $G {\displaystyle G}$ $G$ 、该群的一个生成元 $\alpha$ $\alpha$ 和一个元素 $\beta$ $\beta$ 。试找到一个整数 $x {\displaystyle x}$ $x$ 满足

大步小步算法把 $x {\displaystyle x}$ $x$ 代换成：

于是，我们有：

该算法先对 $j {\displaystyle j}$ $j$ 的不同取值计算出 $\alpha ^{j}$ $\alpha ^{j}$ 的值，然后固定一个 $m {\displaystyle m}$ $m$ ，并对 $i {\displaystyle i}$ $i$ 尝试不同的取值,带入上面同余式的右边，看是否与某个（已经预先算出的）同余式左边的值相匹配。

给出C++17版本的代码：

相关

Royal Society伦敦王家自然知识促进学会（英语：Royal Society of London for Improving Natural Knowledge），简称“王家学会”（Royal Society），但多译作“皇家学会”，是英国资助科学发展的组织，成立
行政院农业委员会动植物防疫检疫局行政院农业委员会动植物防疫检疫局（简称动植物防疫检疫局、防检局）是中华民国行政院农业委员会的附属机关，成立于1998年8月1日，负责动植物的防疫检疫工作。
前沿交叉学科研究院前沿交叉学科研究院（英文Academy for Advanced Interdisciplinary Studies，缩写AAIS）成立于2006年4月4日，是北京大学的交叉学科研究机构。首任院长为韩启德院士。现任院长为韩启
海岸巡防队海岸警卫队（英语：Coast Guard），港澳称为海岸巡防队，台湾称为海岸防卫队，是一些国家或地区设置的海洋安全机构。在不同的政府中，被赋予不同的权限，通常有管理海洋资源、护渔巡逻、海
函数函数在数学中为两不为空集的集合间的一种对应关系：输入值集合中的每项元素皆能对应唯一一项输出值集合中的元素。例如实数 x {\display
尼可籁·霍奇艾诺夫尼可籁·霍奇艾诺夫（俄语：Николай Хозяинов，英语：Nikolay Khozyainov, 1992年7月17日－），俄罗斯古典钢琴家，诞生于俄罗斯远东地区海兰泡（俄语名布拉戈维申斯克，Blagoves
佛公天后宫佛公天后宫，是台湾高雄市前镇区的庙宇，主奉福建海神天上圣母。佛公天后宫的妈祖神像相传是明朝天启年间，来自福建福州马尾沟的一对夫妻（黄奎及何氏更娘）有一日出海捕鱼，当捕完鱼准
Heroine (单曲)《Heroine》（韩语：주인공；中文：主人公）为韩国歌手善美的一首单曲，此单曲由MakeUS娱乐在2018年1月18日发行。1月18日，善美在首尔江南区举办新曲记者会，善美在记者会中表示此次作品为
利奥波德一世 (比利时)利奥波德一世（荷兰语、德语：Leopold I，法语：Léopold Ier，1790年12月16日－1865年12月10日），原名利奥波德·乔治·克里斯蒂安·腓特烈（德语：Leopold Georg Christian Friedrich）；出生于德
雅可比三重乘积雅可比三重乘积是由德国数学家卡尔·雅可比在对theta函数和q-模拟的研究中发现的有关一个三重无穷乘积的恒等式，形如其中 q < |