大步小步算法

✍ dations ◷ 2025-12-03 09:52:00 #自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版本的代码：

相关

锥虫锥虫（Trypanosoma，希腊语：trypaô钻，soma体）是一种带鞭毛的原生动物（鞭毛虫），它可寄生在多种温血动物和冷血动物中。布氏罗得西亚锥虫（Trypanosoma brucei rhodesiense）和布氏冈比亚锥
屏风屏风是家具的一种，作用于间隔出一处特定的空间，有防止光及风直入室内。屏风适合用于更衣、沐浴、睡觉等私人活动。现时在酒楼、办公室等公众场所也常见，它有作为间板房用途，可暂
别尔哥罗德州别尔哥罗德州（俄语：Белгородская область，罗马化：Belgorodskaya oblast）位于俄罗斯西南部顿河—第聂伯河中间的丘陵，南部、西部与乌克兰接壤。是俄罗斯联邦主
卡其布卡其布（印地语：ख़ाकी，乌尔都语：خاکی）是一种主要由棉、毛、化学纤维混纺而成的织品。原文khaki来自波斯语خاک khâk，有大地的颜色、土色之意。在英国或欧洲地区的说法，
大陆军队大陆军（英语：Continental Army）是美国独立战争中的英属北美殖民地军事力量，于1775年6月14日根据第二次大陆议会的决议建立，使美国独立运动有了革命武力对抗英国军队。在整个战争
新加坡国家发展部新加坡国家发展部（英语：Ministry of National Development (MND)；马来语：Kementerian Pembangunan Nasional）是新加坡政府的一个下辖部门。它主要负责规划和指导土地利用、基础设
弗朗西斯科·卡利尼弗朗西斯科·卡利尼（Francesco Carlini，1783年1月7日－1862年8月29日），是一位出生于意大利米兰的天文学家，1832年担任布雷拉天文台台长，并在当年发表了《太阳运动新表》，1810年他曾与
黎伯懽黎伯懽（越南语：Lê Bá Hoan／.mw-parser-output .han-nom{font-family:"Nom Na Tong","Han-Nom Gothic","Han-Nom Ming","HAN NOM A","HAN NOM B","Ming-Lt-HKSCS-UNI-H","Ming
01式轻型反坦克导弹01式轻型反坦克导弹（01式軽対戦車誘導弾，Type 01 LMAT，01-shiki kei-tai-sensha yūdō-dan）是一款由日本重工业企业川崎重工自1993年起研制，到2001年正式生产以后投入陆上自卫队
列塔瓦城堡列塔瓦城堡（斯洛伐克语：Lietavský hrad）是斯洛伐克的一座城堡遗迹，位于斯洛伐克北部日利纳州的苏罗夫山区内。这座城堡修建于1241年之后。1760年代之后，该城堡已经被废弃，不再被