大步小步算法

✍ dations ◷ 2025-11-18 01:08:47 #自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版本的代码：

相关

扩散方程扩散方程是一类偏微分方程，用来描述扩散现象中的物质密度的变化。通常也用来和扩散类似的现象，例如在群体遗传学中等位基因在群体中的扩散。扩散方程通常写作：其中
汪　耕汪耕（1927年10月－），安徽休宁人。1949年毕业于上海交通大学电机系，于1991年当选为中国科学院院士（学部委员），主管学部为技术部。他现亦为上海电机厂的高级工程师。汪耕为电机及发电机
专政专政是一种政体形式，可能指：
韦诺萨韦诺萨（意大利语：Venosa）是意大利南部巴西利卡塔大区波坦察省的一个镇，人口12,147（2004年）。罗马帝国时代著名的诗人贺拉斯出生于韦诺萨。
奥莉加·库津科娃奥莉加·谢尔盖耶夫娜·库津科娃（俄语：Ольга Сергеевна Кузенкова，1970年10月4日－），出生于俄罗斯斯摩棱斯克，是俄罗斯女子田径运动员。她曾获得2000年悉尼
穆胡鲁穆胡鲁（Muhuru）是一种传闻出没于非洲肯尼亚的神秘生物，它通常被描述为一只四足巨型野兽，背上长着剑龙般的骨板，尾部则长着一个尾锤。目前已知第一例有记载的目击是传教士Cal Bomb
2+22+2或二加二可指：
乙武洋匡乙武洋匡（1976年4月6日－）出生于日本东京都新宿区，自幼有先天性四肢切断症，由于自传《五体不满足》而广为知名。在家人与老师的帮助下，克服了许多身体上的不便，一路完成学校教育，并读
2020年欧洲花样滑冰锦标赛2020年欧洲花样滑冰锦标赛于2020年1月20日至26日在奥地利格拉茨举行。比赛分男子单人滑、女子单人滑、双人滑和冰舞四个小项。本次比赛也是2021年欧洲花样滑冰锦标赛的资格
城守尉城守尉，清代八旗驻防将领官名，正三品，负责重要府州防卫，其与副都统等。城守尉所领兵一般为数百人，少者百余人，个别地方也有超过千人的。