吾萌百科 - 用户贡献 [zh-cn]

算法: 求模意义下的乘法逆元

2025-01-09T12:15:25Z

Luke li：

==预备知识==
[[模运算]]

==定义==
这里我们只讨论整数中的乘法逆元。<ref>OI-wiki中更详细的介绍</ref>
具体而言，如果在模 <math>p</math> 意义下，<math>ax\equiv 1(mod\ p)</math> ，我们就称 <math>x</math> 是 <math>a</math> 的乘法逆元。记作 <math>a^{-1}=x</math> 。

如果 <math>p</math> 是质数，那么对于任意的 <math>a\ne 0</math> 都一定存在乘法逆元；如果 <math>p</math> 不是质数，那么可能存在 <math>a\ne 0</math> 不存在乘法逆元。

== 用途 ==
在处理过程中需要取模的问题时，可能会遇到除法。我们都知道，把取模过的数字相除无法得出原来的结果（即 <math>\frac{a\mod c}{b\mod c}\ne \frac{a}{b}</math> ），此时我们就需要用 <math>\times a^{-1}</math> 代替 <math>\div a</math> 。

另外，乘法逆元在加密算法（如[[RSA]]），[[扩展中国剩余定理算法]]等算法中有着重要意义。

== 做法 ==
如何求取乘法逆元呢？这里介绍两种简单的方法。
=== 费马小定理 ===
根据[[费马小定理]]，我们有 <math>a^p\equiv a(mod\ p),\ p \is\mathbb{Prime}</math> 。因此对于 <math>p</math> 是质数的情形，我们可以使用 <math>a^{p-2}</math> 作为 <math>a</math> 在模 <math>p</math> 意义下的乘法逆元。

这可以使用[[快速幂]]在时间复杂度 <math>O(\log p)</math> 内计算出来。
=== 扩展欧几里得 ===
我们都知道欧几里得的[[辗转相除法]]，有人从这一算法中得到启发发明了[[扩展欧几里得]]算法。

这一算法与[[裴蜀定理]]息息相关。裴蜀定理是说：<math>ax+by=c</math> 有解，当且仅当 <math>\gcd(a,b)|c</math> 。因此我们可以先解出 <math>ax+by=\gcd(a,b)</math> 的解集，然后再把 <math>x,y</math> 乘 <math>\frac{c}{\gcd(a,b)}</math> ，即可得出最后的解。 <ref>详情见 oi-wiki贝祖定理</ref>

在辗转相除法中，我们知道 <math>\gcd(a,b)=\gcd(b,a\ mod\ b) , b\ne 0</math> 。运用[[递归]]的思想，先求出 <math>bx'+(a\ mod\ b)y'=\gcd(b,a\ mod\ b)=\gcd(a,b)</math> 的解，然后再转化为原方程的解即可。

可以列出方程式 <math>ax+by=bx'+(a\ mod\ b)y'</math> ，其中 <math>x,y</math> 是未知数，其余的字母都是已知数。因为 <math>a\ mod\ b=a-a\lfloor \frac{a}{b} \rfloor</math> ，移项得到 <math>ax+by=a(y'-\lfloor \frac{a}{b}\rfloor y')+bx'</math> ，所以 <math>x=y'-\lfloor \frac{a}{b}\rfloor y',\ y=x'</math> 是原方程一组可行的解。

这样我们就得到了解方程 <math>ax+by=c</math> 的方法。

将“求模 <math>p</math> 意义下 <math>a</math> 的乘法逆元”这个问题转化一下，就可以改为求 <math>ax+py=1</math> 这一问题中 <math>x</math>的解。显然可以使用裴蜀定理判断是否有解，然后使用exgcd（扩展欧几里得）解决。

词条

2025-01-09T12:13:45Z

Luke li：增加词条

{{警告|此为已存档的部分词条。}}{{卡片|header=医学和伪医学|content=[[双相情感障碍]] [[抑郁障碍]] [[狼化妄想症]] [[性身份障碍]] [[性偏好障碍]] [[鲁拉西酮]] [[抗雄激素]] [[醋酸环丙孕酮]] [[玉玉症]]}}
{{卡片|header=计算机|content=[[计算机的发展史]] [[存储器]] [[中央处理器]] [[Y组合子]] [[递归]] [[栈]] [[队列]] [[前缀和]] [[有穷自动机]] [[差分]] [[离散化]]}}
{{卡片
| header = 数学
| content = [[二次剩余]] [[素数]] [[算数基本定理]] [[约数]] [[欧几里得算法]] [[NFS@Home]] [[算法: 求模意义下的乘法逆元]]
}}
{{卡片|header=自然科学|content=[[生物化学]] [[氨基酸]] [[肽]] [[蛋白质]] [[DNA的复制]]}}
{{卡片|header=NBA|content=[[Lebron James]] [[皇帝的三个决定]]}}
{{卡片|header=编程语言|content=[[Hime]]}}
{{卡片|header=游戏|content= [[光遇]] [[原神]] [[冰与火之舞]] [[我的世界]] [[元气骑士]] [[Mirror]] [[Project Sekai]]}}
{{卡片|header=二次元|content=[[吾萌娘]] [[梅露露]] [[绪山真寻]] [[绪山美波里]] [[关于我被小学女生绑架这件事]] [[电锯人]] [[某科学的超电磁炮]]}}
{{卡片|header=其他|content=[[容克]] [[废话文学]] [[摆烂]] [[猫]] [[Yyds]] [[Tyvj]] [[HYZVijos]] [[五十音]] [[Emo]] [[燕之子安贝]] [[自动挡科目二]] [[CACO]]}}
{{卡片
| header = 世界名人
| content = [[用户:Nomodeset|html]] [[sjq]]
}}
== 音视频 ==
{{卡片|header=音乐|content= [[吾萌:歌词|歌词]]<br>
以下为音视频推荐：
[[音视频推荐|音视频推荐]]}}
== 故事 ==
{{卡片|header=惊悚故事|content=[[故事:妈妈怪谈|妈妈怪谈]] [[故事:公墓怪谈|公墓怪谈]]}}
{{卡片|header=其他故事|content=[[故事:公主与青蛙|公主与青蛙]] [[故事:星辰夜空|星辰夜空]]}}
{{卡片|header=童话故事|content=[[故事:白色妖姬|白色妖姬]] [[故事:奇怪拟人故事黑色菊花|奇怪拟人故事黑色菊花]] [[故事:小红帽与木匠|小红帽与木匠]]}}
== 文章 ==
{{卡片
| header = 其他
| content = [[文章:理想的世界|强烈推荐：理想的世界]]

[[文章:日本青年中所流行的偽中国語|日本青年中所流行的偽中国語]]

[[文章:对于日语中外来词泛滥的个人看法|对于日语中外来词泛滥的个人看法]]

[[文章:贝多芬《欢乐颂》德语版听后感|贝多芬《欢乐颂》德语版听后感]]

[[文章:中世纪啤酒|中世纪啤酒]]

[[文章:铁十字勋章|铁十字勋章]]

[[文章:牡丹|牡丹]]

[[文章:未成年人该如何呼吸|未成年人该如何呼吸]]

[[文章:未成年人该如何睡眠|未成年人该如何睡眠]]

[[文章: 农业的光芒| 农业的光芒]]
}}

算法: 求模意义下的乘法逆元

2024-10-24T01:01:31Z

Luke li：模意义下的乘法逆元是一种重要的数论算法，可用于密码加密等领域。有主要的两种求乘法逆元的方法：费马小定理法，和扩展欧几里得法。

==预备知识==
[[模运算]]

==定义==
这里我们只讨论整数中的乘法逆元。<ref>OI-wiki中更详细的介绍</ref>
具体而言，如果在模 <math>p</math> 意义下，<math>ax\equiv 1(mod\ p)</math> ，我们就称 <math>x</math> 是 <math>a</math> 的乘法逆元。记作 <math>a^{-1}=x</math> 。

如果 <math>p</math> 是质数，那么对于任意的 <math>a\ne 0</math> 都一定存在乘法逆元；如果 <math>p</math> 不是质数，那么可能存在 <math>a\ne 0</math> 不存在乘法逆元。

== 用途 ==
在处理过程中需要取模的问题时，可能会遇到除法。我们都知道，把取模过的数字相除无法得出原来的结果（即 <math>\frac{a\mod c}{b\mod c}\ne \frac{a}{b}</math> ），此时我们就需要用 <math>\times a^{-1}</math> 代替 <math>\div a</math> 。

另外，乘法逆元在加密算法（如[[RSA]]），[[扩展中国剩余定理算法]]等算法中有着重要意义。

== 做法 ==
如何求取乘法逆元呢？这里介绍两种简单的方法。
=== 费马小定理 ===
根据[[费马小定理]]，我们有 <math>a^p\equiv a(mod\ p),\ p\ \ is\ \ prime</math> 。因此对于 <math>p</math> 是质数的情形，我们可以使用 <math>a^{p-2}</math> 作为 <math>a</math> 在模 <math>p</math> 意义下的乘法逆元。

这可以使用[[快速幂]]在时间复杂度 <math>O(\log p)</math> 内计算出来。
=== 扩展欧几里得 ===
我们都知道欧几里得的[[辗转相除法]]，有人从这一算法中得到启发发明了[[扩展欧几里得]]算法。

这一算法与[[裴蜀定理]]息息相关。裴蜀定理是说：<math>ax+by=c</math> 有解，当且仅当 <math>\gcd(a,b)|c</math> 。因此我们可以先解出 <math>ax+by=\gcd(a,b)</math> 的解集，然后再把 <math>x,y</math> 乘 <math>\frac{c}{\gcd(a,b)}</math> ，即可得出最后的解。 <ref>详情见 oi-wiki贝祖定理</ref>

在辗转相除法中，我们知道 <math>\gcd(a,b)=\gcd(b,a\ mod\ b) , b\ne 0</math> 。运用[[递归]]的思想，先求出 <math>bx'+(a\ mod\ b)y'=\gcd(b,a\ mod\ b)=\gcd(a,b)</math> 的解，然后再转化为原方程的解即可。

可以列出方程式 <math>ax+by=bx'+(a\ mod\ b)y'</math> ，其中 <math>x,y</math> 是未知数，其余的字母都是已知数。因为 <math>a\ mod\ b=a-a\lfloor \frac{a}{b} \rfloor</math> ，移项得到 <math>ax+by=a(y'-\lfloor \frac{a}{b}\rfloor y')+bx'</math> ，所以 <math>x=y'-\lfloor \frac{a}{b}\rfloor y',\ y=x'</math> 是原方程一组可行的解。

这样我们就得到了解方程 <math>ax+by=c</math> 的方法。

将“求模 <math>p</math> 意义下 <math>a</math> 的乘法逆元”这个问题转化一下，就可以改为求 <math>ax+py=1</math> 这一问题中 <math>x</math>的解。显然可以使用裴蜀定理判断是否有解，然后使用exgcd（扩展欧几里得）解决。