指定的图片不存在

Extended Euclidean Algorithm

释义 Definition（中文）

扩展欧几里得算法：在计算两个整数 \(a\) 和 \(b\) 的最大公约数 \(\gcd(a,b)\) 的同时，求出整数 \(x, y\)，使得满足贝祖等式：
\[ ax + by = \gcd(a,b) \]
它常用于求模逆元、解线性丢番图方程等。（除“求最大公约数”外，“扩展”之处在于还返回系数 \(x,y\)。）

发音 Pronunciation（IPA）

/ɪkˈstɛndɪd juːˈklɪdiən ˈælɡəˌrɪðəm/

例句 Examples

The extended Euclidean algorithm finds the gcd and the coefficients \(x\) and \(y\).
扩展欧几里得算法能求最大公约数，并给出系数 \(x\) 和 \(y\)。

In RSA, we use the extended Euclidean algorithm to compute the modular inverse needed for the private key.
在 RSA 中，我们用扩展欧几里得算法计算生成私钥所需的模逆元。

词源 Etymology（中文）

“Euclidean”源自古希腊数学家欧几里得（Euclid），其《几何原本》奠定了古典数学传统；“algorithm”一词与中世纪学者花剌子密（al-Khwārizmī）的名字相关，后来在欧洲语言中演变为“算法”。“extended（扩展的）”强调：不仅执行欧几里得算法的辗转相除来求 \(\gcd\)，还“扩展”到回代过程，得到满足贝祖等式的系数。

文学与经典著作 Literary Works（出现示例）

Introduction to Algorithms（CLRS，《算法导论》）：在数论/模运算相关内容中常用扩展欧几里得算法求模逆。
Concrete Mathematics（《具体数学》）：在整数与数论技巧讨论中涉及欧几里得算法及其推广思路。
The Art of Computer Programming, Vol. 2: Seminumerical Algorithms（Knuth，《计算机程序设计艺术》第二卷）：讨论整数算法与欧几里得算法相关方法。
Handbook of Applied Cryptography（《应用密码学手册》）：在公钥密码体制与模逆计算处使用扩展欧几里得算法。
An Introduction to Mathematical Cryptography（《数学密码学导论》）：讲解 RSA、同余与逆元时常明确使用扩展欧几里得算法。