大步小步算法

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

相关

本多健一本多健一（日语：ほんだけんいち；1925年8月23日－2011年2月26日）是一名日本的电化学学者。其最重要的贡献在于发现并定性研究二氧化钛光触媒，并于1960年代发现著名的本多－藤嶋效应，因
鹿豚鹿豚（学名：Babyrousa）又名鹿猪，为偶蹄目猪科鹿豚亚科下的唯一一个属，分布于印尼苏拉威西岛、托吉安群岛、苏拉群岛及布鲁岛。此属原被认为是单型，但现已分成几个物种。最初鹿豚被
大稻埕圆环防空蓄水池坐标：25°03′14.11″N 121°30′52.39″E / 25.0539194°N 121.5145528°E / 25.0539194; 121.5145528大稻埕圆环防空蓄水池是第二次世界大战中太平洋战争（日本称之为大东亚
何家英何家英（1957年－），生于天津，籍贯河北任丘，中国当代工笔画家，中国美术家协会副主席、天津美术学院教授、博士生导师、中国天津文史馆馆员。第九、十、十一届全国政协委员。1980年毕业
八一起义纪念馆坐标：28°40′41″N 115°53′04″E / 28.67806°N 115.88444°E / 28.67806; 115.88444南昌八一起义纪念馆位于中国江西省南昌市中山路380号，是以八一起义指挥部旧址（总指挥部
德山德山（1795年 - ），字琴南，舒舒觉罗氏，满洲镶黄旗人。道光二年壬午科三甲同进士出身，后任刑部主事员外郎，湖北黄州府知府，直隶候补知州等职。兄长德玉是嘉庆二十二年丁丑科进士。
撞角撞角，又名冲角，是一种海战武器，安装在军舰上，对敌舰实施撞击战术。撞角曾经在古代海军舰艇上得到普遍应用。随着舰载火炮的发展，撞角开始没落。十九世纪的铁甲舰时代初期，因当时的
犍为站.mw-parser-output ruby.zy{text-align:justify;text-justify:none}.mw-parser-output ruby.zy>rp{user-select:none}.mw-parser-output ruby.zy>rt{font-feature-settings:
周凤鸣 (正德进士)顾沅辑《吴郡名贤图传赞》之周大理像周凤鸣（1489年－1550年），字于岐，号山斋，南直隶苏州府昆山县（今江苏昆山市）人。明朝政治人物。正德九年（1514年）进士。授刑部主事。嘉靖初历官刑部
瑞岩温泉坐标：24°08′09″N 121°10′29″E / 24.135948°N 121.1748339°E / 24.135948; 121.1748339瑞岩温泉位于台湾南投县仁爱乡发祥村，分布于当地瑞岩部落东北方的北港溪溪谷。