type
status
date
slug
summary
tags
category
icon
password
介绍
扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。已知整数，扩展欧几里得算法可以在求得，的最大公约数的同时，找到整数，（其中一个可能是负数），使它们满足。如果a是负数，可以把问题转化成，然后令。
扩展欧几里得算法可以用来计算模反元素(也叫模逆元)，求出模反元素是RSA加密算法中获得所需公钥、私钥的必要步骤。
裴蜀定理
证明
我们知道，即该表达式最后总能化简成的形式，而当时该式子恒成立，C得证。
代码
C++版本
Python版本
应用
- 求解不定方程
- 求解模的逆元
在啊互质的情况下可转化为进行求解。
- 求解线性同余方程
- Author:Serendipity
- URL:https://serendipity565.netlify.app//article/%E6%8B%93%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!