大步小步算法

✍ dations ◷ 2024-09-20 05:26:31 #自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版本的代码：

相关

假记忆假记忆体综合征（英语：False memory syndrome，FMS）是一个人确信的身份和人际关系与事实不符的一种心理疾病症状。这个词语最先由Peter J. Freyd（英语：Peter J. Freyd）提出，后来由假记
HER21MFG, 1MFL, 1MW4, 1N8Z, 1QR1, 1S78, 2A91, 2JWA, 2KS1, 2L4K, 3BE1, 3H3B, 3MZW, 3N85, 3PP0, 3RCD· protein tyrosine kinase activity · transmembrane receptor pro
素质－压力模式素质—压力模型（英语：diathesis-stress model）是一个心理学理论，尝试去解释心理疾病的成因，主要应用于精神病理学。这个模型也可以用来研究先天与后天在人一生中对于心理疾病的交
中的基督徒相信耶稣是弥赛亚（基督），并相信通过他的死和复活，人类可以与上帝和好，从而得到救恩和永生的承诺。这些教义强调，作为上帝悦纳的羔羊，耶稣选择在髑髅地的十字架上受难，以此作为
黔南民族师范学院黔南民族师范学院黔南民族师范学院，位于贵州省都匀市北开发区，前身为黔南民族师范专科学校，2000年3月28日，经国家教育部教发57号文件批准黔南民族师范专科学校、黔南教育学院、
中国科学技术史 (李约瑟)《中国科学技术史》（英语：Science and Civilization in China）乃李约瑟研究所李约瑟博士和国际学者们所编著的一套关于中国的科学技术历史的著作。李约瑟在书中列出中国人的发
会长会长，即“一会之长”，是流行于汉字文化圈的职称；但随文化语境不同，可能指涉不同类型的职位。称为“会长”的职位包括：
杜鸿君杜鸿君（越南语：Đỗ Hồng Quân，1956年8月1日－），越南音乐家。1956年出生在海阳省锦平县。8岁时入学音乐学院，在艺术家蔡氏莲的指导下初级班。毕业于钢琴与创作中级。从1976年至198
阿斯图里亚斯联合左翼阿斯图里亚斯联合左翼（西班牙语：Izquierda Unida de Asturias）是西班牙左翼政党联盟联合左翼在阿斯图里亚斯的分支。它成立于1993年，主要成员是阿斯图里亚斯共产党。它的政治立
转动惯量列表对于一个有多个质点的系统， I = ∑ i = 1 N