Extended Euclidean Algorithm

/ɪkˈstɛndɪd juːˈklɪdiən ˈælɡərɪðəm/ イクステンデッド ユークリディアン アルゴリズム

1. 2つの整数aとbの最大公約数dを計算し、同時にd = ax + by を満たす整数xとy（ベズー係数）を見つけるアルゴリズム。

拡張ユークリッド互除法は、通常のユークリッド互除法が2つの整数の最大公約数を求めるのに対し、さらにその最大公約数を元の2つの整数の線形結合として表すための係数（ベズー係数）も同時に計算するアルゴリズムです。これは数論や暗号学、特にモジュラ逆元の計算などに非常に重要です。

The Extended Euclidean Algorithm is essential for finding modular multiplicative inverses. (拡張ユークリッド互除法は、モジュラ逆元を見つけるために不可欠です。)

• The: 定冠詞。特定のものを指します。
• Extended Euclidean Algorithm: 拡張ユークリッド互除法。2つの整数の最大公約数とベズー係数を求めるアルゴリズムです。
• is essential: 不可欠である、極めて重要である。
• for finding: ～を見つけるために。目的を示します。
• modular multiplicative inverses: モジュラ逆元。特定のモジュロにおける乗法逆元のことです。

By applying the Extended Euclidean Algorithm, we can solve linear Diophantine equations. (拡張ユークリッド互除法を適用することで、線形ディオファントス方程式を解くことができます。)

• By applying: ～を適用することによって。手段や方法を表します。
• the Extended Euclidean Algorithm: 拡張ユークリッド互除法。この文脈では既知のアルゴリズムを指します。
• we: 私たち。この文脈では一般的な主体を指します。
• can solve: 解くことができる。能力や可能性を表します。
• linear Diophantine equations: 線形ディオファントス方程式。整数解を求めることを目的とする線形方程式のことです。

A key step in the RSA algorithm involves using the Extended Euclidean Algorithm. (RSAアルゴリズムにおける重要なステップの一つに、拡張ユークリッド互除法の使用が含まれます。)

• A key step: 重要なステップの一つ。
• in the RSA algorithm: RSAアルゴリズムにおいて。公開鍵暗号アルゴリズムの一種です。
• involves using: ～を使うことを含む、関わる。
• the Extended Euclidean Algorithm: 拡張ユークリッド互除法。この文脈では特定のアルゴリズムを指します。

関連

• Euclidean Algorithm
• Greatest Common Divisor (GCD)
• Modular Inverse
• Diophantine Equation
• Bezout's Identity
• Cryptography
• Number Theory