| dbo:abstract
|
- L'algorisme d'Euclides ampliat o algorisme d'Euclides estès és una millora de l'algorisme d'Euclides de càlcul del màxim comú divisor de dos nombres enters, que dona, a més del màxim comú divisor dels dos nombres, els coeficients de cadascun d'aquests dos nombres a la identitat de Bézout. (ca)
- في الحسابيات وفي برمجة الحاسوب، خوارزمية إقليدس الممددة (بالإنجليزية: Extended Euclidean algorithm) هي امتداد لخوارزمية أقليدس حيث تحسب بالإضافة إلى القاسم المشترك الأكبر لعددين صحيحين a و b، المعاملين اللذين يظهران في متطابقة بوزو. (ar)
- Rozšířený Eukleidův algoritmus je algoritmus, kterým lze nalézt Bézoutovu rovnost, neboli vyjádření největšího společného dělitele dvou čísel jejich lineární kombinací. (cs)
- Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er berechnet neben dem größten gemeinsamen Teiler zweier natürlicher Zahlen und noch zwei ganze Zahlen und , die die folgende Gleichung erfüllen: Der Algorithmus ist eine Erweiterung des bereits in der Antike bekannten euklidischen Algorithmus, der nur den größten gemeinsamen Teiler berechnet. Das Haupteinsatzgebiet des erweiterten euklidischen Algorithmus ist die Berechnung der inversen Elemente in ganzzahligen Restklassenringen, denn wenn der Algorithmus das Tripel ermittelt, ist entweder und damit , also das multiplikative Inverse von modulo oder aber was bedeutet, dass modulo kein Inverses hat.Dies ist die Grundlage für die Lösung von diophantischen Gleichungen oder allgemeiner von ganzzahligen linearen Gleichungssystemen. Ebenso ist die Bestimmung inverser Elemente eine Grundlage für den chinesischen Restsatz, welcher wiederum Grundlage des bedeutenden Tricks der kleinen Primzahlen in der berechenbaren Algebra ist. Dabei wird eine Aufgabe in mehreren endlichen Körpern gelöst und diese Teillösungen in immer größere Restklassenringe gehoben, bis sich eine ganzzahlige Lösung ablesen lässt. Der Algorithmus liefert zudem einen konstruktiven Beweis für das Lemma von Bézout, also . (de)
- In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs.It allows one to compute also, with almost no extra cost, the quotients of a and b by their greatest common divisor. Extended Euclidean algorithm also refers to a very similar algorithm for computing the polynomial greatest common divisor and the coefficients of Bézout's identity of two univariate polynomials. The extended Euclidean algorithm is particularly useful when a and b are coprime. With that provision, x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a. Similarly, the polynomial extended Euclidean algorithm allows one to compute the multiplicative inverse in algebraic field extensions and, in particular in finite fields of non prime order. It follows that both extended Euclidean algorithms are widely used in cryptography. In particular, the computation of the modular multiplicative inverse is an essential step in the derivation of key-pairs in the RSA public-key encryption method. (en)
- En mathématiques, l'algorithme d'Euclide étendu est une variante de l'algorithme d'Euclide. À partir de deux entiers a et b, il calcule non seulement leur plus grand commun diviseur (PGCD), mais aussi un de leurs couples de coefficients de Bézout, c'est-à-dire deux entiers u et v tels que au + bv = PGCD(a, b). Quand a et b sont premiers entre eux, u est alors l'inverse pour la multiplication de a modulo b (et v est de la même façon l'inverse modulaire de b, modulo a), ce qui est un cas particulièrement utile. Alors que l'algorithme d'Euclide détermine quand une équation diophantienne ax + by = c possède une solution, l'algorithme d'Euclide étendu en fournit également une solution particulière, dont on déduit facilement la solution générale. Comme l'algorithme d'Euclide, l'algorithme étendu se généralise aux anneaux euclidiens, tels celui des polynômes à une variable sur un corps commutatif. De même que pour les entiers, il permet alors de calculer l'inverse d'un polynôme modulo un polynôme avec lequel il est premier et donc des calculs d'inverse dans les anneaux ou corps construits par quotient sur l'anneau des polynômes : corps de rupture, corps finis, etc. (fr)
- Het uitgebreide algoritme van Euclides is een uitbreiding van het algoritme van Euclides, die niet alleen de grootste gemene deler g.g.d. van twee natuurlijke getallen en bepaalt, maar ook een oplossing geeft van de identiteit van Bézout, een lineaire diofantische vergelijking in gehele en : , waarin ggd staat voor grootste gemene deler. De uitbreiding bestaat daarin dat behalve de berekening van de g.g.d. van de getallen en met het algoritme van Euclides, ook de g.g.d. wordt uitgedrukt als gehele lineaire combinatie van en . Het bewijs van de stelling van Bachet-Bézout steunt op de constructie door het algoritme. Aan de hand van een voorbeeld zal duidelijk worden hoe het algoritme tot stand komt. (nl)
- In aritmetica e nella programmazione l'algoritmo esteso di Euclide è un'estensione dell'algoritmo di Euclide che calcola non solo il massimo comun divisore (indicato con MCD nel seguito) tra due interi a e b, ma anche i coefficienti dell'identità di Bézout x e y tali che: L'algoritmo esteso di Euclide è particolarmente utile quando a e b sono interi coprimi: in questo caso x è l'inverso moltiplicativo di a modulo b e y è l'inverso moltiplicativo di b modulo a. Spesso si indica con l'espressione algoritmo esteso di Euclide anche un altro algoritmo, molto simile al precedente, per il calcolo del massimo comun divisore tra polinomi e i loro coefficienti dell'identità di Bézout. Entrambi gli algoritmi trovano applicazione nella crittografia, in particolare il calcolo dell'inverso moltiplicativo modulare è un passo fondamentale per criptare i messaggi con l'algoritmo a chiave pubblica RSA. Le prime documentazioni sull'algoritmo risalgono al V-VI secolo a.C., ad opera del matematico indiano Aryabhata. Fu poi riscoperto più volte indipendentemente, ad esempio dal francese Bachet nel 1621 e poi da Eulero intorno al 1731. (it)
- O Algoritmo de Euclides estendido é uma extensão do algoritmo de Euclides, que, além de calcular o máximo divisor comum (MDC) entre fornece os coeficientes tais que O algoritmo é utilizado, em especial, para o cálculo de inverso modular. Se e são coprimos, então é o inverso modular de módulo e é o inverso modular de módulo Essa propriedade é amplamente utilizada no estudo em Criptografia, mais especificamente, no processo de quebra de chaves privadas do método de encriptação RSA. (pt)
- Расширенный алгоритм Евклида — это расширение алгоритма Евклида, которое вычисляет кроме наибольшего общего делителя (НОД) целых чисел a и b ещё и коэффициенты соотношения Безу, то есть целые x и y, такие что Алгоритм является , поскольку НОД является единственным числом, которое одновременно удовлетворяет уравнению и делит входные числа. Алгоритм позволяет также почти без дополнительных затрат вычислять частные от деления a и b на их наибольший общий делитель. Под Расширенным алгоритмом Евклида также понимается для вычисления и вычисления коэффициентов соотношения Безу двух многочленов от одной переменной. Расширенный алгоритм Евклида особенно полезен, когда a и b взаимно просты. При таких условиях x является модульным обратным числа a по модулю b, а y является модульным обратным числа b по модулю a. Аналогично, расширенный алгоритм Евклида для многочленов позволяет вычислить обратное число в алгебраических расширениях и, в частности, в конечных полях непростого порядка. Поэтому оба расширенных алгоритма Евклида широко используются в криптографии. В частности, вычисление обратного элемента по модулю является существенным шагом в получении пары ключей в методе RSA шифрования с открытым ключом. (ru)
- 扩展欧几里得算法（英語：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足貝祖等式 如果a是负数，可以把问题转化成 （为a的绝对值），然后令。 通常談到最大公因數時，我們都會提到一個非常基本的事實（由貝祖等式给出）：給定二个整數a、b，必存在整數x、y使得ax + by = gcd(a,b)。 众所周知，已知两个数和，对它们进行辗转相除（欧几里得算法），可得它们的最大公约数。不过，在欧几里得算法中，我们仅仅利用了每步带余除法所得的余数。扩展欧几里得算法还利用了带余除法所得的商，在辗转相除的同时也能得到貝祖等式（貝祖定理中描述的等式）中的x、y两个系数。以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数。 另外，扩展欧几里得算法是一种自验证算法，最后一步得到的和（和的含义见下文）乘以后恰为和，可以用来验证计算结果是否正确。 扩展欧几里得算法可以用来计算模反元素(也叫模逆元)，求出模反元素是RSA加密算法中获得所需公钥、私钥的必要步骤。 (zh)
- Розширений алгоритм Евкліда —це розширення алгоритму Евкліда. Окрім знаходження найбільшого спільного дільника для цілих a і b, як це робить алгоритм Евкліда, він також знаходить цілі x і y (одне з яких зазвичай від'ємне), які задовольняють рівнянню Безу. Розширений алгоритм Евкліда особливо корисний коли a і b взаємно прості числа, бо x — обернене щодо a за модулем b, а y — обернене щодо b за модулем a. (uk)
|
| rdfs:comment
|
- L'algorisme d'Euclides ampliat o algorisme d'Euclides estès és una millora de l'algorisme d'Euclides de càlcul del màxim comú divisor de dos nombres enters, que dona, a més del màxim comú divisor dels dos nombres, els coeficients de cadascun d'aquests dos nombres a la identitat de Bézout. (ca)
- في الحسابيات وفي برمجة الحاسوب، خوارزمية إقليدس الممددة (بالإنجليزية: Extended Euclidean algorithm) هي امتداد لخوارزمية أقليدس حيث تحسب بالإضافة إلى القاسم المشترك الأكبر لعددين صحيحين a و b، المعاملين اللذين يظهران في متطابقة بوزو. (ar)
- Rozšířený Eukleidův algoritmus je algoritmus, kterým lze nalézt Bézoutovu rovnost, neboli vyjádření největšího společného dělitele dvou čísel jejich lineární kombinací. (cs)
- O Algoritmo de Euclides estendido é uma extensão do algoritmo de Euclides, que, além de calcular o máximo divisor comum (MDC) entre fornece os coeficientes tais que O algoritmo é utilizado, em especial, para o cálculo de inverso modular. Se e são coprimos, então é o inverso modular de módulo e é o inverso modular de módulo Essa propriedade é amplamente utilizada no estudo em Criptografia, mais especificamente, no processo de quebra de chaves privadas do método de encriptação RSA. (pt)
- 扩展欧几里得算法（英語：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足貝祖等式 如果a是负数，可以把问题转化成 （为a的绝对值），然后令。 通常談到最大公因數時，我們都會提到一個非常基本的事實（由貝祖等式给出）：給定二个整數a、b，必存在整數x、y使得ax + by = gcd(a,b)。 众所周知，已知两个数和，对它们进行辗转相除（欧几里得算法），可得它们的最大公约数。不过，在欧几里得算法中，我们仅仅利用了每步带余除法所得的余数。扩展欧几里得算法还利用了带余除法所得的商，在辗转相除的同时也能得到貝祖等式（貝祖定理中描述的等式）中的x、y两个系数。以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数。 另外，扩展欧几里得算法是一种自验证算法，最后一步得到的和（和的含义见下文）乘以后恰为和，可以用来验证计算结果是否正确。 扩展欧几里得算法可以用来计算模反元素(也叫模逆元)，求出模反元素是RSA加密算法中获得所需公钥、私钥的必要步骤。 (zh)
- Розширений алгоритм Евкліда —це розширення алгоритму Евкліда. Окрім знаходження найбільшого спільного дільника для цілих a і b, як це робить алгоритм Евкліда, він також знаходить цілі x і y (одне з яких зазвичай від'ємне), які задовольняють рівнянню Безу. Розширений алгоритм Евкліда особливо корисний коли a і b взаємно прості числа, бо x — обернене щодо a за модулем b, а y — обернене щодо b за модулем a. (uk)
- In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs.It allows one to compute also, with almost no extra cost, the quotients of a and b by their greatest common divisor. (en)
- Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er berechnet neben dem größten gemeinsamen Teiler zweier natürlicher Zahlen und noch zwei ganze Zahlen und , die die folgende Gleichung erfüllen: Der Algorithmus ist eine Erweiterung des bereits in der Antike bekannten euklidischen Algorithmus, der nur den größten gemeinsamen Teiler berechnet. (de)
- En mathématiques, l'algorithme d'Euclide étendu est une variante de l'algorithme d'Euclide. À partir de deux entiers a et b, il calcule non seulement leur plus grand commun diviseur (PGCD), mais aussi un de leurs couples de coefficients de Bézout, c'est-à-dire deux entiers u et v tels que au + bv = PGCD(a, b). Quand a et b sont premiers entre eux, u est alors l'inverse pour la multiplication de a modulo b (et v est de la même façon l'inverse modulaire de b, modulo a), ce qui est un cas particulièrement utile. Alors que l'algorithme d'Euclide détermine quand une équation diophantienne ax + by = c possède une solution, l'algorithme d'Euclide étendu en fournit également une solution particulière, dont on déduit facilement la solution générale. (fr)
- In aritmetica e nella programmazione l'algoritmo esteso di Euclide è un'estensione dell'algoritmo di Euclide che calcola non solo il massimo comun divisore (indicato con MCD nel seguito) tra due interi a e b, ma anche i coefficienti dell'identità di Bézout x e y tali che: L'algoritmo esteso di Euclide è particolarmente utile quando a e b sono interi coprimi: in questo caso x è l'inverso moltiplicativo di a modulo b e y è l'inverso moltiplicativo di b modulo a. (it)
- Het uitgebreide algoritme van Euclides is een uitbreiding van het algoritme van Euclides, die niet alleen de grootste gemene deler g.g.d. van twee natuurlijke getallen en bepaalt, maar ook een oplossing geeft van de identiteit van Bézout, een lineaire diofantische vergelijking in gehele en : , waarin ggd staat voor grootste gemene deler. De uitbreiding bestaat daarin dat behalve de berekening van de g.g.d. van de getallen en met het algoritme van Euclides, ook de g.g.d. wordt uitgedrukt als gehele lineaire combinatie van en . (nl)
- Расширенный алгоритм Евклида — это расширение алгоритма Евклида, которое вычисляет кроме наибольшего общего делителя (НОД) целых чисел a и b ещё и коэффициенты соотношения Безу, то есть целые x и y, такие что Алгоритм является , поскольку НОД является единственным числом, которое одновременно удовлетворяет уравнению и делит входные числа. Алгоритм позволяет также почти без дополнительных затрат вычислять частные от деления a и b на их наибольший общий делитель. (ru)
|
