搜索

[12407] 2018-02-27_高效幂模算法探究：Montgomery算法解析

文档创建者：s7ckTeam
浏览次数：8
最后更新：2025-01-18
2018-02-27_高效幂模算法探究：Montgomery算法解析 高 效 幂 模 算 法 探 究 ： M o n t g o m e r y 算 法 解 析 原 创   G e e k O n l i n e   F r e e B u f   2 0 1 8 - 0 2 - 2 7 * 本 文 作 者 ： G e e k O n l i n e ， 本 文 属   F r e e B u f   原 创 奖 励 计 划 ， 未 经 许 可 禁 止 转 载 。 模 运 算 ， 又 称 模 算 数 ( m o d u l a r   a r i t h m e t i c ) ， 是 一 个 整 数 的 算 术 系 统 ， 其 中 数 字 超 过 一 定 值 后 ( 称 为 模 ) 会 “ 卷 回 ” 到 较 小 的 数 值 ， 模 运 算 最 早 是 卡 尔 · 弗 里 德 里 系 · 高 斯 在 1 8 0 1 年 出 版 的 《 算 术 研 究 》 中 书 面 公 开 ， 但 在 这 之 前 模 运 算 的 方 法 已 经 深 入 到 人 类 社 会 的 方 方 面 面 ， 例 如 在 时 间 上 的 运 用 ， 我 国 古 时 的 《 中 国 十 二 时 辰 图 》 就 把 一 天 划 分 为 子 、 丑 、 寅 、 卯 等 十 二 个 时 辰 ， 每 个 时 辰 相 当 于 现 在 的 两 个 小 时 ， 每 过 完 十 二 个 时 辰 又 重 新 开 始 计 算 ， 这 种 计 数 方 式 的 模 就 为 1 2 。 模 运 算 在 数 论 、 群 论 、 环 论 、 电 脑 代 数 、 密 码 学 、 计 算 机 科 学 等 学 科 中 都 有 着 广 泛 地 应 用 ， 从 奇 偶 数 的 判 别 到 模 运 算 在 数 论 、 群 论 、 环 论 、 电 脑 代 数 、 密 码 学 、 计 算 机 科 学 等 学 科 中 都 有 着 广 泛 地 应 用 ， 从 奇 偶 数 的 判 别 到 素 数 的 判 别 ， 从 模 幂 运 算 到 最 大 公 约 数 的 求 法 ， 从 孙 子 算 经 中 的 问 题 到 凯 撒 密 码 问 题 ， 都 充 斥 这 模 运 算 的 身 素 数 的 判 别 ， 从 模 幂 运 算 到 最 大 公 约 数 的 求 法 ， 从 孙 子 算 经 中 的 问 题 到 凯 撒 密 码 问 题 ， 都 充 斥 这 模 运 算 的 身 影 。 影 。 在 密 码 学 中 ， 模 运 算 是 R S A 及 迪 菲 - 赫 尔 曼 ( D - H ) 等 公 开 密 钥 机 密 系 统 的 基 础 。 在 电 脑 代 数 多 项 式 分 解 以 及 多 项 式 最 大 公 因 式 、 线 性 代 数 等 问 题 ， 所 有 已 知 有 效 率 的 解 法 用 到 了 模 运 算 。 模 运 算 渗 透 了 人 类 生 活 的 方 方 面 面 ， 因 此 如 何 在 当 下 计 算 系 统 中 更 加 高 效 的 运 用 模 运 算 也 是 一 个 十 分 关 键 的 问 题 ， 尤 其 在 面 对 比 较 消 耗 资 源 的 大 数 幂 模 运 算 时 更 应 该 注 重 此 类 算 法 的 高 效 性 。 普 通 幂 模 算 法 普 通 幂 模 算 法 由 于 模 运 算 可 以 将 所 有 中 间 结 果 和 最 后 结 果 限 制 在 一 个 范 围 内 ， 对 一 个 k 位 的 模 数 n ， 任 何 加 、 减 、 乘 、 除 的 中 间 结 果 将 不 会 超 过 2 k 位 长 ， 因 此 在 计 算 大 数 幂 模 时 通 常 会 考 虑 结 合 模 运 算 分 解 幂 过 程 ， 防 止 计 算 过 程 产 生 大 数 中 间 值 进 而 发 生 溢 出 等 错 误 的 情 况 ， 例 如 ： 图 1   普 通 幂 模 算 法 变 换 以 上 优 化 算 法 使 用 了 模 运 算 的 运 算 法 则 ： 图 2   乘 模 运 算 变 换 这 种 算 法 称 为 加 法 链 ( a d d i t i o n   c h a i n i n g ) ， 或 二 进 制 平 方 和 乘 法 方 法 ， 算 法 的 C 语 言 描 述 ： 利 用 该 算 法 可 以 有 效 避 免 因 为 幂 运 算 产 生 大 数 而 使 得 后 续 模 运 算 无 法 进 行 的 问 题 。
图 3   程 序 示 例 计 算 简 单 幂 模 图 4   计 算 器 验 证 程 序 正 确 性 当 计 算 一 些 高 次 幂 模 时 ， 普 通 计 算 器 由 于 按 顺 序 计 算 ， 在 幂 运 算 时 产 生 大 数 导 致 后 续 无 法 进 行 ， 而 加 法 链 操 作 则 由 于 分 解 了 幂 运 算 ， 使 得 每 次 的 中 间 过 程 变 量 都 限 制 在 了 模 范 围 内 ， 因 此 可 以 计 算 更 加 复 杂 的 幂 模 运 算 。
图 5   计 算 器 程 序 在 计 算 4 8 6 ^ 2 8 6 7 5 4 1 时 产 生 大 数 导 致 错 误 反 汇 编 上 述 算 法 后 ， 发 现 虽 然 该 算 法 有 效 的 解 决 了 幂 模 过 程 中 幂 运 算 产 生 大 数 的 问 题 ， 但 在 实 际 计 算 模 运 算 时 仍 旧 采 用 了 除 法 指 令 ， 且 采 用 除 法 指 令 的 次 数 和 幂 运 算 的 指 数 正 相 关 ， 而 我 们 知 道 在 计 算 机 系 统 除 法 指 令 是 一 个 相 当 耗 时 的 指 令 ， 因 此 该 算 法 不 能 算 作 一 个 高 效 的 幂 模 算 法 。 图 6   加 法 链 算 法 反 汇 编 M o n t g o m e r y 算 法 算 法 M o n t g o m e r y 算 法 由 1 9 8 5 年 美 国 数 学 家 P e t e r   L . M o n t g o m e r y 在 其 论 文 ” M o d u l a r   M u l t i p l i c a t i o n   W i t h o u t   T r i a l   D i v i s i o n ” 中 向 大 家 展 示 如 何 在 不 使 用 除 法 的 情 况 下 实 现 快 速 乘 模 计 算 ， 下 面 便 以 此 种 算 法 介 绍 高 效 幂 模 算 法 的 实 现 。 首 先 考 虑 最 初 的 我 们 进 行 模 运 算 的 基 本 方 法 ， 通 常 最 容 易 回 想 起 的 就 是 使 用 除 法 然 后 得 到 余 数 就 是 我 们 要 取 的 模 ( 此 处 只 考 虑 正 整 数 运 算 ) ， 即 ：
图 7   常 规 模 运 算 公 式 现 在 我 们 知 道 如 果 利 用 此 公 式 在 计 算 机 中 不 可 避 免 的 将 使 用 除 法 进 行 运 算 ， 于 是 在 大 型 幂 模 计 算 时 是 不 可 取 的 ， 那 么 我 们 考 虑 一 种 更 原 始 的 计 算 模 的 运 算 — — 减 法 ： 图 8   使 用 减 法 的 思 想 计 算 模 使 用 该 思 想 有 效 的 避 免 了 在 模 运 算 中 使 用 除 法 指 令 ， 但 是 当 计 算 的 数 非 常 大 时 ， 这 种 运 算 将 进 行 太 多 次 循 环 减 法 ， 可 以 想 象 在 该 数 达 到 某 一 个 界 限 时 使 用 减 法 进 行 模 运 算 的 资 源 消 耗 将 和 除 法 相 差 不 大 ， 当 超 越 这 个 界 限 那 么 减 法 思 想 的 求 模 运 算 几 乎 是 毫 无 意 义 。 在 排 除 了 减 法 和 除 法 后 ， 我 们 转 而 考 察 使 用 加 法 进 行 模 运 算 的 可 能 性 ， 这 也 是 M o n t g o m e r y 算 法 所 探 寻 的 方 向 ， 我 们 用 例 子 来 体 会 这 种 思 维 转 变 的 路 线 。 考 虑 计 算   4 3 5 6   ( m o d   9 7 ) ， 因 为 给 出 的 两 个 数 值 并 不 是 很 大 ， 可 以 很 快 计 算 出 乘 积 4 3 5 6 = 2 4 0 8 ， 此 时 可 以 使 用 除 法 较 快 的 计 算 出 模 的 结 果 ， 也 可 以 使 用 减 法 得 出 结 果 ， 但 我 们 此 时 不 考 虑 计 算 模 ， 而 是 使 用 乘 积 加 上 n 倍 模 数 9 7 使 得 该 乘 积 ( 2 4 0 8 ) 转 变 成 我 们 人 思 维 中 好 计 算 的 数 字 ， 比 如 数 字 低 位 全 为 0 的 状 态 ： 图 9   经 过 两 次 变 换 后 的 乘 积 表 示 那 么 此 时 如 果 再 让 我 们 计 算 5 9 0 0   /   1 0 0 ， 那 么 对 于 我 们 人 脑 来 说 这 再 简 单 不 过 了 ， 可 以 瞬 间 口 算 出 结 果 为 5 9 。 可 惜 的 是 ， 5 9 并 不 是 我 们 要 求 的 4 3 * 5 6   m o d   9 7 的 结 果 ， 但 我 们 确 实 认 清 了 在 此 时 如 果 除 数 是 1 0 0 而 不 是 9 7 ， 那 么 我 们 的 计 算 会 轻 松 很 多 。 那 么 既 然 在 我 们 已 认 知 的 世 界 中 没 有 这 种 理 想 的 计 算 环 境 ， 那 么 我 们 就 考 虑 制 造 一 个 ， 这 种 思 维 与 传 统 的 数 学 思 维 非 常 相 似 ： 比 如 当 笛 卡 尔 坐 标 系 无 法 帮 助 我 们 有 效 建 模 时 ， 我 们 便 会 考 虑 采 用 极 坐 标 系 去 建 模 ； 当 时 域 信 息 无 法 进 行 有 效 分 析 时 ， 我 们 便 会 考 虑 转 换 至 频 域 进 行 分 析 。 在 某 一 个 域 类 无 法 解 决 的 问 题 到 另 一 个 域 类 可 能 就 是 1 + 1 = 2 的 难 度 。
M o n t g o m e r y 算 法 就 建 立 了 这 么 一 个 空 间 ， 在 普 通 计 算 域 的 除 数 9 7 ， 转 换 到 M o n t g o m e r y 域 中 除 数 就 变 成 了 1 0 0 ， 因 此 对 于 模 运 算 的 难 度 会 陡 然 下 降 。 用 以 上 例 子 ( 4 3 * 6 5   m o d   9 7 ) 介 绍 M o n t g o m e r y 域 ， 常 规 世 界 的 数 字 形 式 需 要 转 换 成 M o n t g o m e r y 域 中 的 数 字 形 式 ， 首 先 我 们 的 模 数 为 9 7 ， 这 是 一 个 2 位 的 十 进 制 数 ， 那 么 计 算 M o n t g o m e r y 域 中 第 一 个 关 键 变 量 R ， 使 得 ： 图 1 0   计 算 M o n t g o m e r y 域 变 量 R 在 当 前 例 子 中 模 数 为 9 7 ， b 为 1 0 ， 计 算 得 出 m = 2 ， R = 1 0 0 。 另 一 个 关 键 变 换 针 对 两 个 乘 积 因 子 ： 图 1 1   乘 数 因 子 M o n t g o m e r y 表 示 当 前 例 子 中 的 乘 数 4 3 的 M o n t g o m e r y 表 示 法 为 4 3 * 1 0 0 ( m o d   9 7 ) = 3 2 。 当 然 到 现 在 我 们 还 看 不 到 这 种 变 换 有 啥 意 义 ， 貌 似 除 了 增 加 计 算 量 之 外 并 没 有 给 后 续 的 计 算 带 来 什 么 方 便 ， 我 们 接 着 看 后 续 的 变 换 。 考 虑 以 下 计 算 ： 图 1 2   计 算 x * y ( m o d   p ) 在 M o n t g o m e r y 域 的 等 价 表 达 式 但 在 大 数 乘 模 运 算 中 ， 通 常 我 们 希 望 中 间 结 果 仍 然 保 留 在 M o n t g o m e r y 域 中 ， 因 为 后 续 还 有 很 多 乘 法 操 作 需 要 进 行 ， 在 此 时 直 接 将 结 果 表 示 为 现 实 域 结 果 将 导 致 很 大 的 中 间 转 换 开 销 且 并 不 符 合 我 们 的 意 愿 ， 因 此 我 们 实 际 希 望 在 M o n t g o m e r y 域 中 计 算 x y R ( m o d   p ) ， 也 就 是 现 实 域 中 的 x y 。 所 以 在 M o n t g o m e r y 域 中 每 次 计 算 两 个 因 子 的 乘 积 后 需 要 除 以 R ， 调 整 参 数 后 的 结 果 才 是 x y 在 M o n t g o m e r y 域 中 的 中 间 结 果 。 图 1 3   x * y 在 M o n t g o m e r y 域 中 的 计 算 结 果 在 本 次 列 举 的 实 例 中 ( 4 3 * 6 5   m o d   9 7 ) 即 是 中 间 乘 积 的 结 果 除 以 R = 1 0 0 。 以 实 例 解 释 上 述 推 导 ：
图 1 4   计 算 x * y 的 实 例 其 中 图 1 5   M o n t g o m e r y 域 中 形 式 变 换 基 于 一 个 数 学 事 实 ： 图 1 6   M o n t g o m e r y 域 变 换 中 的 数 学 原 理 在 上 述 例 子 中 我 们 计 算 出 一 个 在 M o n t g o m e r y 域 中 x y ( m o d   p ) 的 结 果 4 6 ， 对 应 现 实 域 的 x y R ( m o d   p ) ， 因 此 结 果 必 然 不 是 现 实 域 中 ( 4 3 * 6 5   m o d   9 7 ) 的 结 果 ， 需 要 经 过 逆 变 换 后 才 能 代 表 现 实 域 的 结 果 ， 变 换 公 式 为 ： 图 1 7   M o n t g o m e r y 域 结 果 转 换 成 现 实 域 结 果 其 中 ：
图 1 8   R ^ - 1 的 计 算 方 法 因 此 将 实 例 中 的 结 果 转 换 后 得 到 结 果 ： 图 1 9   验 证 转 换 后 的 结 果 是 否 符 合 计 算 结 果 我 们 发 现 此 算 法 的 特 点 是 在 算 法 首 端 会 将 现 实 域 的 数 字 转 换 成 M o n t g o m e r y 域 中 的 表 达 形 式 ， 在 M o n t g o m e r y 域 进 行 整 个 求 解 过 程 后 再 将 M o n t g o m e r y 域 中 的 结 果 转 换 成 现 实 域 中 的 结 果 ， 从 而 完 成 整 个 计 算 ， 其 中 巧 妙 之 处 在 于 M o n t g o m e r y 域 的 创 建 使 我 们 需 要 进 行 2 2 7 2 / 9 7 运 算 变 成 了 4 6 0 0 / 1 0 0 的 运 算 ， 因 此 加 快 了 我 们 人 脑 的 运 算 ， 其 在 转 换 过 程 中 的 计 算 则 又 加 大 了 我 们 的 运 算 量 ， 但 考 虑 幂 模 的 形 式 a a a a … . a ( m o d   p ) 的 进 行 中 所 消 耗 的 运 算 量 ， 则 这 两 次 转 换 的 计 算 量 其 实 并 不 算 什 么 。 上 述 思 维 也 就 是 M o n t g o m e r y 论 文 中 提 及 的 第 一 个 约 简 算 法 ： 图 2 0   摘 自 M o n t g o m e r y 论 文 其 中 为 了 将 不 好 运 算 的 2 2 7 2 转 换 成 4 6 0 0 格 式 ， 采 用 了 ( T   m o d   R ) N ’   m o d   R 公 式 来 实 现 ， 其 中 N ’ 满 足 图 1 8 的 公 式 ， 可 以 用 扩 展 欧 几 里 得 算 法 求 得 ， 将 上 述 思 想 转 换 成 C 语 言 格 式 ： 图 2 1   M o n t g o m e r y   R E D C 函 数 C 语 言 其 中 C 语 言 中 r e d u c e 函 数 中 n = 6 7 即 是 上 面 提 到 的 N ’ 变 量 ， 可 以 用 扩 展 欧 几 里 得 算 法 得 到 ： 图 2 2   扩 展 欧 几 里 得 求 N ‘ 变 量 我 可 以 反 汇 编 调 试 该 代 码 看 看 计 算 机 到 底 怎 么 思 考 这 段 代 码 ， 可 以 看 到 计 算 机 思 考 这 段 代 码 非 常 艰 难 ， 我 们 眼 中 的 4 6 0 0 / 1 0 0 ， 它 完 全 无 法 理 解 ， 以 至 于 它 最 后 还 是 选 择 了 用 除 法 解 决 问 题 ， 而 我 们 人 脑 面 对 这 个 算 式 时 几 乎 不 用 除 法 ，
通 常 的 做 法 都 是 ” 抹 零 ” 操 作 ， 我 们 可 以 用 一 种 更 书 面 一 点 的 描 述 ， 4 6 0 0 / 1 0 0 时 我 们 其 实 对 被 除 数 进 行 了 移 位 操 作 ， 后 面 的 除 数 是 1 0 0 ， 因 此 我 们 决 定 将 4 6 0 0 右 移 两 位 最 终 得 到 了 4 6 。 而 计 算 机 无 法 体 会 这 种 思 维 ， 因 为 4 6 0 0 对 于 它 来 说 就 如 图 2 4 一 样 ， 他 没 法 进 行 ” 抹 零 ” 操 作 完 成 运 算 。 图 2 3   反 汇 编 关 键 代 码 处 图 2 4   计 算 机 思 维 中 的 4 6 0 0 对 于 人 脑 来 说 大 家 习 惯 了 1 0 进 制 的 计 算 世 界 ， 看 待 4 6 0 0 / 1 0 0 非 常 简 单 ， 但 在 计 算 机 的 世 界 它 们 并 不 喜 欢 十 进 制 ， 而 是 更 喜 欢 二 进 制 的 计 算 方 式 ， 因 此 M o n t g o m e r y 域 中 用 于 简 化 计 算 的 R 值 针 对 人 类 思 维 模 式 是 1 0 ^ m ， 而 针 对 计 算 机 的 思 维 模 式 就 是 2 ^ n 。 因 此 在 变 换 中 应 该 使 用 R = 2 ^ 7 = 1 2 8 > 9 7 进 行 变 换 操 作 ， 以 R = 1 2 8 对 上 述 实 例 计 算 进 行 变 换 ， 带 入 C 语 言 程 序 中 ： 图 2 5   以 R = 1 2 8 对 实 例 计 算 进 行 变 换 图 2 6   计 算 此 时 的 N ‘ 变 量
图 2 7   将 M o n t g o m e r y 域 结 果 转 换 成 真 实 域 结 果 此 时 的 我 们 在 M o n t g o m e r y 域 中 产 生 了 机 器 非 常 喜 欢 的 结 果 7 0 4 0 ( 7 2 8 7   +   ( 7 2 8 7 ) m o d 1 2 8   9 5   m o d 1 2 8   9 7 ) ， 机 器 在 这 时 就 可 以 模 拟 人 类 的 处 理 方 法 使 用 ” 抹 零 ” 操 作 快 速 完 成 除 法 运 算 ， 抹 掉 后 续 的 零 后 机 器 得 到 了 1 1 0 1 1 1 的 结 果 ， 换 算 成 我 们 青 睐 的 1 0 进 制 也 就 是 5 5 ， 再 用 M o n t g o m e r y 逆 变 换 将 结 果 转 回 现 实 域 即 得 到 真 实 的 运 算 结 果 。 图 2 8   M o n t g o m e r y 域 中 机 器 青 睐 的 结 果 所 以 根 据 机 器 对 待 这 种 算 法 的 方 式 我 们 优 化 C 语 言 代 码 ， 经 过 优 化 后 我 们 将 传 递 给 我 们 的 关 键 函 数 以 m 值 ( 即 R = 2 ^ m 中 的 m ) 而 不 是 直 接 将 R 值 传 递 进 去 ， 那 么 内 部 我 们 的 关 于 取 模 和 除 法 函 数 全 以 & 和 > > 运 算 取 代 ， 通 过 关 键 函 数 的 反 汇 编 可 以 与 之 前 图 2 3 进 行 对 比 ， 里 面 的 除 法 指 令 d i v 已 经 全 部 消 失 ， 实 现 了 不 使 用 除 法 而 进 行 模 计 算 的 目 标 ， 且 我 们 依 旧 得 到 了 我 们 想 要 的 结 果 。 此 代 码 得 到 了 有 效 的 改 善 ， 且 当 在 大 数 幂 模 计 算 时 性 能 上 的 优 势 会 随 着 运 算 量 的 增 大 而 进 一 步 凸 显 出 来 。 图 2 9   针 对 机 器 思 维 优 化 的 代 码
图 3 0   优 化 代 码 的 反 汇 编 结 合 加 法 链 的 思 想 在 这 里 我 们 就 可 以 完 成 一 个 简 单 版 本 的 M o n t g o m e r y 快 速 幂 模 C 语 言 程 序 ， 其 中 E x t B i n E u c l i d 函 数 为 扩 展 欧 几 里 得 算 法 ， 在 此 不 再 进 一 步 做 深 入 探 究 ： 图 3 1   结 合 加 法 链 思 想 的 M o n t g o m e r y 幂 模 程 序
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

使用Markdown编辑器编辑 使用富文本编辑器编辑

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理