大步小步算法

✍ dations ◷ 2025-11-14 23:15:15 #自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版本的代码：

相关

俄罗斯－南非俄罗斯－南非关系（俄语：Российско-южноафриканские отношения），是指俄罗斯和南非的外交关系。两国在1992年2月28日建交，俄罗斯在比勒陀利亚有大
北极大学合作网络加拿大、丹麦、芬兰、冰岛、挪威、俄罗斯、瑞典、美国、英国北极大学（英语：University of the Arctic，UArctic）是一个包含北极圈内大学、学院及其他组织的协作网络，其目的是提升
瓦尔格拉瓦尔格拉（阿拉伯语：وَرڤلة‎）位于阿尔及利亚中部，是瓦尔格拉省的首府。
格雷格·阿博特格雷格·阿博特（Greg Abbott；1957年11月13日－）是美国的一位政治人物。格雷格·阿博特自2015年开始担任第48任德克萨斯州州长。格雷格·阿博特的党籍是共和党。阿博特在担任州长
M3反坦克炮第二次世界大战时美军的反坦克炮有75毫米口径M1A1和37毫米口径M3两种，由于在欧洲战场上的纳粹德军的坦克大多甲坚炮利，故美军以威力较强的M1A1主打欧洲，而M3则留在东亚和太平洋
M24霞飞M24霞飞（英语：M24 Chaffee）为一款美国在二次世界大战中期服役的轻型坦克，并且使用于韩战。本坦克是以拥有“美国装甲兵之父”头衔的小阿德纳·霞飞将军作为命名。1942年北非一系
四氯化钛四氯化钛，或氯化钛（IV），是化学式为 TiCl4 的无机化合物。四氯化钛是生产金属钛及其化合物的重要中间体。室温下，四氯化钛为无色液体，并在空气中发烟，生成二氧化钛固体和盐酸液滴的
北拉勒米河北拉勒米河（英语：North Laramie River）是拉勒米河的一条支流，长约139.0千米，位于美国怀俄明州的东南部。坐标：42°07′36″N 104°55′28″W / 42.12667°N 104.92444°W / 42.12
安拉阿巴德安拉阿巴德（印地语：प्रयागराज；乌尔都语：پریاگراج‎，转写：Prayāgrāj‎）是印度北方邦的一座城市。安拉阿巴德的意思是“安拉的城市”（City of Allah），这是由莫卧儿帝
皮纽湖皮纽湖（Panixersee），是瑞士的水库，位于该国东南部，由格劳宾登州负责管辖，长1.5公里、宽0.3公里，面积4平方公里，海拔高度1,452米，水体容量7,300万立方米。