| dbo:abstract
|
- في الرياضيات، خوارزمية أقليدس (بالإنجليزية: Euclidean algorithm) هي طريقة فعالة تمكن من إيجاد القاسم المشترك الأكبر لعددين وهو أكبر عدد يقسم في نفس الوقت العددين معا بدون أي باق من القسمة. يُرمز له بالفرنسية ب PGCD وبالإنجليزية GCD. سميت هذه الخوارزمية هكذا نسبة إلى عالم الرياضيات الإغريقي أقليدس الذي وصف الخوارزمية لأول مرة في كتابه المعروف باسم الأصول (حوالي عام 300 ق.م). هي مثال عن الخوارزميات (الخوارزمية طريقةٌ تمكن من القيام بعملية ما، خطوة خطوة طِبقا لقواعد معينة محددة مسبقا). وهو من أقدم الخوارزميات اللائي ما زلن قيد الاستعمال. قد تستعمل من أجل اختزال كسر إلى شكله المبسط غير القابل للاختزال، وهي جزء من الحسابات المتعلقة بنظرية الأعداد والتشفير. تعتمد خوارزمية أقليدس على مبدأ أن القاسم المشترك الأكبر لعددين لا يتغير إذا عُوض أكبرهما بالفرق بينه وبين أصغرهما. على سبيل المثال، 21 هو القاسم المشترك الأكبر للعددين 252 و 105 (نظرا إلى أن 252 = 21 * 12 و 105 = 21 * 5)، وأن 21 هو أيضا القاسم المشترك الأكبر ل 105 و 252 - 105 = 147. بقلب مراحل خوارزمية أقليدس، الأخيرة، فما قبلها، فما قبلها وهكذا، يُحصل على صيغة يُعبر فيها عن القاسم المشترك الأكبر بتأليفة خطية للعددين الأصليين، أي على شكل مجموعهما بعد ضرب كل واحد منهما في عدد صحيح ما. على سبيل المثال، . تعرف هذه المسألة بمتطابقة بيزو نسبة إلى عالم الرياضيات الفرنسي إيتيان بيزو. الصيغة التي وُصفت أعلاه لخوارزمية أقليدس (وهكذا وصفها إقليدس) قد تتأخر أثناء عملية حساب الفرق بين أكبر العددين وأصغرهما، خصوصا إذا كان العدد الأكبر أكبر بكثير من العدد الأصغر. هناك صيغة أكثر سرعة من هذه الصيغة، تمكن من اختصار هذه المراحل. بدلا من تعويض أكبر العددين بالفرق بينه وبين أصغر العددين، يُعوض أكبر العددين بباقي قسمته على أصغر العددين. في هذه الطريقة، الخوارزمية تتوقف عندما يصيرا الباقي مساويا للصفر. تطبيقا لهذه الطريقة، الخوارزمية لا تتطلب أبدا، من الخطوات ما يتجاوز خمسة أضعاف عدد أرقام العدد المقسوم عليه، مكتوبا في القاعدة 10. برهن على هذه المسألة عالم الرياضيات الفرنسي غابرييل لامي. كان ذلك عام 1844، غارسا بذلك البذرة الأولى لعلم التعقد الحسابي. رأت النور خلال القرن العشرين طرق إضافية مكنت من جعل الخوارزمية أكثر قوة وسرعة. لخوارزمية أقليدس العديد من التطبيقات النظرية والعملية. تستعمل من أجل اختزال الكسور إلى شكلها المبسط. تستعمل أيضا في أثناء القسمة في إطار الحسابيات النمطية. قد تشكل بعض من الحسابات المستعملة لهذه الخوارزمية، جزءا من بروتوكولات التعمية التي بفضلها تؤمن الاتصالات عبر الأنترنيت. وتستعمل أيضا في طرق تمكن من كسر هذه الأنظمة التشفيرية؛ وذلك بتحليل عدد صحيح إلى عوامل. تستعمل خوارزمية أقليدس في حلحلة بعض الأشكال الخاصة من المعادلات الديوفانتية، من قبيل ايجاد أعداد صحيحة تحقق معادلات تردُدية عدة في إطار مبرهنة الباقي الصينية، ومن قبيل إنشاء الكسور المستمرة ومن أجل ايجاد لأعداد حقيقية. أضف إلى ذلك أنها تستعمل حجرَ أساس في البرهان على مبرهنات في نظرية الأعداد من قبيل مبرهنة المربعات الأربع للاغرانج والمبرهنة الأساسية في الحسابيات. صُممت الخوارزمية في الأصل من أجل العمل على قسمة الأعداد الطبيعية والقياسات الهندسية، ولكنها عُممت خلال القرن التاسع عشر على كائنات ر ياضية أخرى. الأعداد الصحيحة الغاوسية ومتعددات الحدود ذات متغير واحد مثالان على ذلك. (ar)
- L'algorisme d'Euclides és un mètode eficaç per a calcular el màxim comú divisor (mcd) entre dos nombres enters. Rep el nom del matemàtic grec Euclides el qual el va descriure en els volums VII i X del llibre Elements. L'algorisme consisteix en diverses divisions enteres successives. En la primera divisió, es pren com a dividend el major dels nombres i com a divisor l'altre. Després, el divisor i el residu serveixen respectivament de dividend i divisor de la següent divisió. El procés es para quan s'obté un residu nul. El mcd és llavors el penúltim residu de l'algorisme. Formalment, si anomenem a, b els enters inicials, r1, rn ... rn-1 i rn = 0 els residus successius, llavors: mcd (a, b) = mcd (b, r1), amb r1 = a - b·q (q és el quocient de a per b) Després el menor dels divisors comuns és el mateix, i repetint l'operació: mcd (b, r1) = mcd (r1, r₂) = mcd (r₂, r₃) = ... = mcd (rn-1, rn) = mcd (rn-1, 0) = rn-1. Això permet detallar l'algorisme efectiu: Aquest algorisme dona com a resultat 0 si a i b són nuls, mentre que en matemàtiques el major divisor de zero no existix. (ca)
- Eukleidův algoritmus (též Euklidův) je algoritmus, kterým lze určit největší společný dělitel dvou přirozených čísel, tedy největší číslo takové, že beze zbytku dělí obě čísla. Jedná se o jeden z nejstarších známých netriviálních algoritmů a postupně vznikla řada jeho modifikací například pro příbuzné úlohy. Z nich nejdůležitější je rozšířený Eukleidův 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í. Algoritmus lze také použít i v jiných algebraických strukturách, než jsou přirozená čísla. Takové struktury se nazývají Eukleidovské obory a jedná se například o některé okruhy mnohočlenů nebo o Eisensteinova čísla. (cs)
- Στα μαθηματικά, ο αλγόριθμος του Ευκλείδη ή Ευκλείδειος αλγόριθμος είναι μια αποτελεσματική μέθοδος για τον υπολογισμό του μέγιστου κοινού διαιρέτη (ΜΚΔ) δύο ακέραιων αριθμών, είναι επίσης γνωστός ως ο μεγαλύτερος κοινός παράγοντας ή υψηλότερος κοινός παρονομαστής. Το όνομά του προέρχεται από τον Έλληνα μαθηματικό Ευκλείδη, ο οποίος τον περιγράφει στα βιβλία VII και X του βιβλίου του Στοιχεία. Στην απλούστερη μορφή του, ο αλγόριθμος του Ευκλείδη ξεκινά με ένα ζεύγος θετικών ακεραίων και σχηματίζει ένα νέο ζευγάρι που αποτελείται από το μικρότερο αριθμό και τη διαφορά μεταξύ των μεγαλύτερων και των μικρότερων αριθμών. Η διαδικασία επαναλαμβάνεται έως ότου οι αριθμοί είναι ίσοι. Αυτός ο αριθμός είναι τότε ο μέγιστος κοινός διαιρέτης του αρχικού ζεύγους. Η παλαιότερη περιγραφή που υπάρχει για τον Ευκλείδειο αλγόριθμο είναι στα Στοιχεία του Ευκλείδη (περ. 300 π.Χ.), καθιστώντας τον ένα από τους παλαιότερους αριθμητικούς αλγορίθμους ακόμα σε κοινή χρήση. Ο αρχικός αλγόριθμος αφορούσε μόνο φυσικούς αριθμούς και γεωμετρικά μήκη (πραγματικοί αριθμοί), αλλά ο αλγόριθμος γενικεύτηκε τον 19ο αιώνα και σε άλλους τύπους αριθμών, όπως Gaussian ακέραιοι και πολυώνυμα μιας μεταβλητής. Αυτό οδήγησε στις σύγχρονες αφηρημένες αλγεβρικές έννοιες, όπως οι . Ο Ευκλείδειος αλγόριθμος έχει γενικευτεί περαιτέρω και σε άλλες μαθηματικές δομές, όπως κόμβους κύκλων και . Ο αλγόριθμος έχει πολλές θεωρητικές και πρακτικές εφαρμογές. Μπορεί να χρησιμοποιηθεί για να δημιουργήσει σχεδόν όλους τους πιο σημαντικούς παραδοσιακούς μουσικούς ρυθμούς που χρησιμοποιούνται σε διαφορετικούς πολιτισμούς σε όλο τον κόσμο.Πρόκειται για ένα βασικό στοιχείο του RSA αλγορίθμου, μια μέθοδο κρυπτογράφησης δημόσιου κλειδιού που χρησιμοποιείται ευρέως στο ηλεκτρονικό εμπόριο. Χρησιμοποιείται για την επίλυση Διοφαντικών εξισώσεων, όπως η εξεύρεση αριθμών που ικανοποιούν πολλαπλά σχήματα με ίδιο ύψος και μέγεθος ή ενός πεπερασμένου σώματος. Μπορεί επίσης να χρησιμοποιηθεί για την κατασκευή συνεχών κλασμάτων , ,μέθοδο για την εύρεση πραγματικών ριζών ενός πολυωνύμου, και σε πολλές σύγχρονες ακέραιες παραγοντοποιήσεις αλγορίθμων. Τέλος, είναι ένα βασικό εργαλείο για την απόδειξη θεωρημάτων στη σύγχρονη θεωρία αριθμών, όπως το το θεμελιώδες θεώρημα της αριθμητικής (μοναδική παραγοντοποίηση). Εάν υλοποιηθεί με τη χρήση της Ευκλείδειας διαίρεσης και όχι με αφαιρέσεις, ο αλγόριθμος του Ευκλείδη υπολογίζει το ΜΚΔ μεγάλων αριθμών αποτελεσματικά: Ποτέ δεν απαιτεί περισσότερα βήματα διαίρεσης από πέντε φορές τον αριθμό των ψηφίων (με βάση το 10) από τον μικρότερο ακέραιο. Αυτό αποδείχθηκε από τον το 1844 και σηματοδοτεί την έναρξη της . Μέθοδοι για τη βελτίωση της απόδοσης του αλγορίθμου αναπτύχθηκαν τον 20ο αιώνα. Ο ΜΚΔ των δύο αριθμών είναι ο μεγαλύτερος αριθμός που διαιρεί τους δύο χωρίς να αφήνει . Ο Ευκλείδειος αλγόριθμος βασίζεται στην αρχή ότι ο μέγιστος κοινός διαιρέτης των δύο αριθμών δεν αλλάζει εάν ο μικρότερος αριθμός αφαιρείται από το μεγαλύτερο αριθμό. Αν k , m και n είναι ακέραιοι, και το k είναι ένας κοινός παράγοντας των δύο ακεραίων αριθμών Α και Β , τότε Α = ΝΚ και Β = mk συνεπάγεται A − B = (n − m)k, συνεπώς, k είναι επίσης ένας κοινός παράγοντας της διαφοράς. Αυτό το k μπορεί επίσης να αντιπροσωπεύει τον μέγιστο κοινό διαιρέτη όπως αποδεικνύεται παρακάτω. Για παράδειγμα, το 21 είναι ο ΜΚΔ των 105 και 252 (252 = 12 × 21; 105 = 5 × 21). Από το 252 − 105 = (12 − 5) × 21 = 147, ο ΜΚΔ των 147 και 105 είναι επίσης 21. Δεδομένου ότι ο μεγαλύτερος από τους δύο αριθμούς μειώνεται, επαναλαμβάνοντας τη διαδικασία, αυτή θα δίνει διαδοχικά μικρότερους αριθμούς μέχρι ένας από αυτούς να γίνει μηδέν. Όταν αυτό συμβεί, ο ΜΚΔ είναι ο μη μηδενικός αριθμός που απομένει. Αντιστρέφοντας τα βήματα του αλγόριθμου του Ευκλείδη , ο ΜΚΔ μπορεί να εκφραστεί ως το άθροισμα/ των δύο αρχικών αριθμών καθώς πολλαπλασιάζεται με ένα θετικό ή αρνητικό , π.χ. 21 = [5 × 105] + [(−2) × 252]. Αυτή η σημαντική ιδιότητα είναι γνωστή ως . (el)
- En matematiko, eŭklida algoritmo estas algoritmo por kalkuli la plej grandan komunan divizoron (PGKD) de du entjeroj aŭ pli ĝenerale de du eroj de . Ĝia avantaĝo estas tio ke ĝi ne postulas faktorigon de la entjeroj. Ĝi estas unu el la plej malnovaj sciataj algoritmoj, datata al la antikvaj grekoj. (eo)
- Der euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Mit ihm lässt sich der größte gemeinsame Teiler zweier natürlicher Zahlen berechnen. Das Verfahren ist nach dem griechischen Mathematiker Euklid benannt, der es in seinem Werk „Die Elemente“ beschrieben hat. Der größte gemeinsame Teiler zweier Zahlen kann auch aus ihren Primfaktorzerlegungen ermittelt werden. Ist aber von keiner der beiden Zahlen die Primfaktorzerlegung bekannt, so ist der euklidische Algorithmus das schnellste Verfahren zur Berechnung des größten gemeinsamen Teilers. Der euklidische Algorithmus lässt sich nicht nur auf natürliche Zahlen anwenden. Vielmehr kann damit der größte gemeinsame Teiler von zwei Elementen eines jeden euklidischen Rings berechnet werden. Dazu zählen beispielsweise Polynome über einem Körper. (de)
- In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC).It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules,and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. By or using the extended Euclidean algorithm, the GCD can be expressed as a linear combination of the two original numbers, that is the sum of the two numbers, each multiplied by an integer (for example, 21 = 5 × 105 + (−2) × 252). The fact that the GCD can always be expressed in this way is known as Bézout's identity. The version of the Euclidean algorithm described above (and by Euclid) can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844, and marks the beginning of computational complexity theory. Additional methods for improving the algorithm's efficiency were developed in the 20th century. The Euclidean algorithm has many theoretical and practical applications. It is used for reducing fractions to their simplest form and for performing division in modular arithmetic. Computations using this algorithm form part of the cryptographic protocols that are used to secure internet communications, and in methods for breaking these cryptosystems by factoring large composite numbers. The Euclidean algorithm may be used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem, to construct continued fractions, and to find accurate rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in number theory such as Lagrange's four-square theorem and the uniqueness of prime factorizations. The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. This led to modern abstract algebraic notions such as Euclidean domains. (en)
- El algoritmo de Euclides es un método antiguo y eficiente para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación, entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia. (es)
- Euklidesen algoritmoa, matematikan, bi zenbakiren zatitzaile komunetako handiena kalkulatzeko erabiltzen den metodo bat da. Euklidesek deskribatu zuen lehenengo aldiz bere Elementuak obran (K.a. 300). Euklidesen algoritmo hedatuarekin, gainera, zatitzaile komunetako handiena emandako bi zenbakien konbinazio lineal moduan adierazteko koefizienteak kalkula daitezke. Algoritmoa hainbat arlotan aplikatzen da; aljebran, zenbaki-teorian eta informatikan, esaterako. (eu)
- En mathématiques, l'algorithme d'Euclide est un algorithme qui calcule le plus grand commun diviseur (PGCD) de deux entiers, c'est-à-dire le plus grand entier qui divise les deux entiers, en laissant un reste nul. L'algorithme ne requiert pas de connaître la factorisation de ces deux nombres. (fr)
- Dalam matematika, algoritme Euklides adalah suatu algoritme untuk menentukan faktor persekutuan terbesar (FPB) dari dua bilangan bulat. Algoritme ini dinamai setelah matematikawan Yunani Euklides menuliskannya dalam Buku VII dan Buku X Elemen Euklides. Algoritme Euklides muncul dalam buku Elemen Euklides sekitar tahun 300 SM, menjadikannya salah satu algoritme numerik yang tertua dan masih digunakan secara luas. Algoritme Euklides tidak memerlukan faktorisasi. (in)
- L'algoritmo di Euclide è un algoritmo per trovare il massimo comune divisore (indicato di seguito con MCD) tra due numeri interi. È uno degli algoritmi più antichi conosciuti, essendo presente negli Elementi di Euclide intorno al 300 a.C.; tuttavia, probabilmente l'algoritmo non è stato scoperto da Euclide, ma potrebbe essere stato conosciuto anche 200 anni prima. Certamente era conosciuto da Eudosso di Cnido intorno al 375 a.C.; Aristotele (intorno al 330 a.C.) ne ha fatto cenno ne , 158b, 29-35. L'algoritmo non richiede la fattorizzazione dei due interi. Dati due numeri naturali e , l'algoritmo prevede che si controlli se è zero (questa prima fase rientra ovviamente nell'ambito di un uso moderno dell'algoritmo ed era ignorata da Euclide e dai suoi predecessori, che non conoscevano il concetto di zero). Se lo è, è il MCD. Se non lo è, sideve dividere e definire come il resto della divisione (operazione indicata con "a modulo b" più sotto). Se allora si può affermare che è il MCD cercato, altrimenti occorre assegnare e e ripetere nuovamente la divisione.L'algoritmo può essere espresso in modo naturale utilizzando la ricorsione in coda. Tenendo nota dei quozienti ottenuti durante lo svolgimento dell'algoritmo, si possono determinare due interi e tali che .Questo è noto con il nome di algoritmo di Euclide esteso. Questi algoritmi possono essere usati, oltre che con i numeri interi, in ogni contesto in cui è possibile eseguire la divisione col resto. Ad esempio, l'algoritmo funziona per i polinomi ad una indeterminata su un campo K, o polinomi omogenei a due indeterminate su un campo, o gli interi gaussiani. Un oggetto algebrico in cui è possibile eseguire la divisione col resto è chiamato anello euclideo. Euclide originariamente formulò il problema geometricamente, per trovare una "misura" comune per la lunghezza di due segmenti, e il suo algoritmo procedeva sottraendo ripetutamente il più corto dal più lungo. Questo procedimento è equivalente alla implementazione seguente, che è molto meno efficiente del metodo indicato sopra. (it)
- 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 《원론》 제7권, 명제 1부터 3까지에 해당한다. 최소공배수, 최대공약수를 구하기 위해서는 다음과 같은 표를 쓴다. (ko)
- ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。 2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。 明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである。 (ja)
- In de getaltheorie, een deelgebied van de wiskunde, is het algoritme van Euclides een efficiënte methode voor het berekenen van de grootste gemene deler (ggd) van twee positieve gehele getallen. Het algoritme is vernoemd naar de Oud-Griekse wiskundige Euclides van Alexandrië, die het algoritme in de boeken VII en X van zijn Elementen beschreef. Het algoritme berust erop dat de ggd van twee gehele getallen ook de ggd is van zowel het kleinste getal als van de rest die overblijft bij deling van het grootste getal door het kleinste. Zo ontstaat er een aflopend iteratief proces. Er bestaat ook een uitgebreide variant van dit algoritme. (nl)
- Algorytm Euklidesa – algorytm wyznaczania największego wspólnego dzielnika dwóch liczb. Został opisany przez greckiego matematyka, Euklidesa w jego dziele „Elementy”, w księgach siódmej oraz dziesiątej. Pierwsze wzmianki na temat tego algorytmu pojawiły się w dziele Euklidesa zatytułowanym „Elementy”, około trzysetnego roku przed naszą erą, co sprawia, że jest jednym z najstarszych, wciąż używanych algorytmów numerycznych. Pierwsza wersja algorytmu została opisana tylko dla liczb naturalnych. W XIX wieku powstały odmiany algorytmu dla liczb całkowitych Gaussa oraz wielomianów z jedną niewiadomą. Doprowadziło to do powstania współczesnych pojęć algebry abstrakcyjnej, takich jak dziedzina Euklidesa. W późniejszych czasach opracowano odmiany algorytmu dla innych struktur matematycznych, jak węzły czy wielomiany z wieloma niewiadomymi. Istnieje wiele teoretycznych i praktycznych zastosowań algorytmu. Może on zostać wykorzystany do generowania rytmów muzycznych, stosowanych jako ostinato w muzyce. Jest wykorzystywany w algorytmie RSA. Algorytm Euklidesa używany jest też do rozwiązywania równań diofantycznych, na przykład do znajdowania liczb spełniających zadany układ kongruencji (chińskie twierdzenie o resztach) czy znajdowania liczb odwrotnych w ciele skończonym. Może być także stosowany do generowania ułamków łańcuchowych w metodzie Sturma do obliczania pierwiastków rzeczywistych wielomianu. Wykorzystywany jest również w kilku współczesnych algorytmach do faktoryzacji liczb całkowitych. Jeżeli algorytm zostanie zaimplementowany poprzez obliczanie reszt z dzielenia, a nie odejmowanie, to jest wydajny dla dużych liczb: nigdy nie wymaga więcej dzieleń niż liczba cyfr (w systemie dziesiętnym) mniejszej liczby pomnożona przez 5. Zostało to udowodnione przez Gabriela Lamé w 1844 i uważane jest za pierwszy przypadek analizy złożoności obliczeniowej algorytmu. Sposoby zwiększenia wydajności algorytmów zostały opracowane w XX wieku. Największym wspólnym dzielnikiem dwóch liczb jest największa z liczb, która dzieli obie te liczby bez reszty. Algorytm Euklidesa opiera się na założeniu, że największy wspólny dzielnik dwóch liczb nie zmienia się, jeżeli od większej liczby odejmujemy mniejszą. Dla liczb całkowitych k, m oraz n załóżmy, że k jest wspólnym czynnikiem liczb A oraz B; załóżmy też, że oraz Możemy teraz dokonać działania wiemy więc, że k jest także wspólnym czynnikiem różnicy tych liczb. (pl)
- Em matemática, o algoritmo de Euclides é um método simples e eficiente de encontrar o máximo divisor comum entre dois números inteiros diferentes de zero. É um dos algoritmos mais antigos, conhecido desde que surgiu nos Livros VII e X da obra Elementos de Euclides por volta de 300 a.C.. O algoritmo não exige qualquer fatoração. O MDC de dois números inteiros é o maior número inteiro que divide ambos sem deixar resto. O algoritmo de Euclides é baseado no princípio de que o MDC não muda se o menor número for subtraído ao maior. Por exemplo, 21 é o MDC de 252 e 105 (252 = 21 × 12; 105 = 21 × 5); já que 252 − 105 = 147, o MDC de 147 e 105 é também 21. Como o maior dos dois números é reduzido, a repetição deste processo irá gerar sucessivamente números menores, até convergir em zero. Nesse momento, o MDC é o outro número inteiro, maior que zero. Ao reverter os passos do algoritmo de Euclides, o MDC pode ser expresso como soma dos dois números originais, cada um multiplicado por um número inteiro positivo ou negativo, por exemplo: 21 = 5 × 105 + (−2) × 252. Esta importante propriedade é denominada identidade de Bézout. A mais antiga descrição que se conhece do método usado no algoritmo de Euclides é da sua obra Elementos (c. 300 a.C.), o que o torna um dos algoritmos numéricos mais antigos ainda em uso corrente. O algoritmo original foi descrito apenas para números naturais e comprimentos geométricos, mas foi generalizado no século XIX para outras classes de números como os inteiros gaussianos e polinómios de uma variável. Isto conduziu a noções da moderna álgebra abstrata tais como os domínios euclidianos. O algoritmo de Euclides foi ainda generalizado mais a outras estruturas matemáticas, como os nós e polinómios multivariados. O algoritmo tem muitas aplicações teóricas e práticas. Ele pode ser usado para gerar quase todas as importantes aplicações tradicionais usados em diferentes culturas em todo o mundo. Ele é um elemento-chave dos algoritmos RSA, um método de criptografia de chave pública usado no comércio eletrônico. Ele é usado para resolver as equações de diofantina, tal como na descoberta de números que seja safistatório em múltiplas congruências (teorema chinês do resto) ou inverso multiplicativo de um . Ele pode também ser usado para construir frações contínuas, em um método para o teorema de Sturm para descobrir raízes reais em um polinômio, e em vários algoritmos modernos em fatoração de inteiros. Finalmente, é uma ferramenta básica para obter na teoria dos números modernas, tal como teorema de Fermat-Lagrange e no teorema fundamental da aritmética. (pt)
- Euklides algoritm är en algoritm för att bestämma största gemensamma delare till två heltal. Det är en av de äldsta kända algoritmerna och beskrivs i Euklides Elementa. Algoritmen kräver inte att man kan dela upp talen i faktorer. Algoritmen kan beskrivas på följande sätt: 1.
* Två heltal a och b, där a > b är givna. 2.
* Om b = 0 är algoritmen klar och svaret är a. 3.
* I annat fall beräknas c, resten när man delat a med b. 4.
* sätt a = b, b = c och börja om från steg 2 igen, (a får det värde b har och b får det värde c har). (sv)
- Алгоритм Евкліда (також називається евклідів алгоритм) — ефективний метод обчислення найбільшого спільного дільника (НСД). Названий на честь грецького математика Евкліда, котрий описав його в книгах VII та X Начал. Найбільший спільний дільник двох чисел це найбільше число, що ділить обидва дані числа без остачі. Алгоритм Евкліда заснований на тому, що НСД не змінюється, якщо від більшого числа відняти менше. Наприклад, 21 є НСД чисел 252 та 105 (252 = 21 × 12; 105 = 21 × 5); оскільки 252 − 105 = 147, НСД 147 та 105 також 21. Оскільки більше з двох чисел постійно зменшується, повторне виконання цього кроку дає все менші числа, поки одне з них не дорівнюватиме нулю. Коли одне з чисел дорівнюватиме нулю, те, що залишилось, і є НСД. Обертаючи кроки алгоритму Евкліда у зворотний порядок, НСД можна виразити як лінійну комбінацію даних чисел помножених на цілі коефіцієнти, наприклад 21 = 5 × 105 + (−2) × 252. Ця важлива властивість відома як рівняння Безу. Найдавніший опис алгоритму знаходиться в Началах Евкліда (біля 300 до н. е.), що робить його найдавнішим чисельним алгоритмом, яким користуються і нині. Оригінальний варіант алгоритму описував роботу лише з натуральними числами та геометричними довжинами (дійсними числами), алгоритм було узагальнено в XIX столітті на роботу з іншими типами чисел, такими як Гаусові числа та поліноми з однією змінною. Це призвело до появи сучасних алгебраїчних понять, таких як Евклідові класи. Алгоритм Евкліда було узагальнено ще далі для роботи з іншими математичними структурами, такими як вузли та поліноми від багатьох змінних. Алгоритм Евкліда має багато застосувань на практиці, та в теорії. З його допомогою можна згенерувати практично всі найважливіші музичні ритми різних культур у всьому світі. Алгоритм Евкліда відіграє ключову роль в алгоритмі RSA, поширеному методі криптографії з відкритим ключем. Його також використовують для пошуку розв'язків Діофантових рівнянь, наприклад, пошук чисел, що задовільняють декільком умовам (Китайська теорема про залишки) або обернені числа в скінченному полі. Алгоритм Евкліда також застосовують для побудови ланцюгових дробів в методі Штурма для пошуку дійсних коренів полінома, та в сучасних методах факторизації цілих. Нарешті, він виступає простим інструментом для доведення теорем в теорії чисел, таких, як Теорема Лагранжа про чотири квадрати та основної теореми арифметики. Алгоритм Евкліда ефективно обчислює НСД великих чисел, оскільки виконує операцій не більше, ніж вп'ятеро більше кількості цифр меншого числа (в десятковій системі). Цю властивість було доведено Ґабріелем Ламе (англ. Gabriel Lamé) в 1844 році, що позначило початок теорії складності обчислень. Методи підвищення ефективності алгоритму були розроблені в XX столітті. (uk)
- Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида (III век до н. э.), который впервые описал его в VII и X книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше время. В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары. Евклид предложил алгоритм только для натуральных чисел и геометрических величин (длин, площадей, объёмов). Однако в XIX веке он был обобщён на другие типы математических объектов, включая целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как евклидово кольцо. Позже алгоритм Евклида был обобщён на другие математические структуры, такие как узлы и многомерные полиномы. Для данного алгоритма существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSA, широко распространённого в электронной коммерции. Также алгоритм используется при решении линейных диофантовых уравнений, при построении непрерывных дробей, в методе Штурма. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например таких как теорема Лагранжа о сумме четырёх квадратов и основная теорема арифметики. (ru)
- 在数学中，辗转相除法，又称欧几里得算法（英語：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。 两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。例如，252和105的最大公约数是21（）；因为，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数为零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如。这个重要的結論叫做貝祖定理。 辗转相除法最早出现在欧几里得的《几何原本》中（大约公元前300年），所以它是现行的算法中歷史最悠久的。这个算法原先只用来处理自然数和几何长度（相當於正實數），但在19世纪，辗转相除法被推广至其他类型的數學對象，如高斯整数和一元多项式。由此，引申出欧几里得整环等等的一些现代抽象代数概念。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。 辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，比如寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。 辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（十进制下）的五倍。拉梅于1844年证明了这点，同時這也標誌著计算复杂性理论的開端。 (zh)
|
| rdfs:comment
|
- En matematiko, eŭklida algoritmo estas algoritmo por kalkuli la plej grandan komunan divizoron (PGKD) de du entjeroj aŭ pli ĝenerale de du eroj de . Ĝia avantaĝo estas tio ke ĝi ne postulas faktorigon de la entjeroj. Ĝi estas unu el la plej malnovaj sciataj algoritmoj, datata al la antikvaj grekoj. (eo)
- El algoritmo de Euclides es un método antiguo y eficiente para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación, entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia. (es)
- Euklidesen algoritmoa, matematikan, bi zenbakiren zatitzaile komunetako handiena kalkulatzeko erabiltzen den metodo bat da. Euklidesek deskribatu zuen lehenengo aldiz bere Elementuak obran (K.a. 300). Euklidesen algoritmo hedatuarekin, gainera, zatitzaile komunetako handiena emandako bi zenbakien konbinazio lineal moduan adierazteko koefizienteak kalkula daitezke. Algoritmoa hainbat arlotan aplikatzen da; aljebran, zenbaki-teorian eta informatikan, esaterako. (eu)
- En mathématiques, l'algorithme d'Euclide est un algorithme qui calcule le plus grand commun diviseur (PGCD) de deux entiers, c'est-à-dire le plus grand entier qui divise les deux entiers, en laissant un reste nul. L'algorithme ne requiert pas de connaître la factorisation de ces deux nombres. (fr)
- Dalam matematika, algoritme Euklides adalah suatu algoritme untuk menentukan faktor persekutuan terbesar (FPB) dari dua bilangan bulat. Algoritme ini dinamai setelah matematikawan Yunani Euklides menuliskannya dalam Buku VII dan Buku X Elemen Euklides. Algoritme Euklides muncul dalam buku Elemen Euklides sekitar tahun 300 SM, menjadikannya salah satu algoritme numerik yang tertua dan masih digunakan secara luas. Algoritme Euklides tidak memerlukan faktorisasi. (in)
- 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 《원론》 제7권, 명제 1부터 3까지에 해당한다. 최소공배수, 최대공약수를 구하기 위해서는 다음과 같은 표를 쓴다. (ko)
- ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。 2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。 明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである。 (ja)
- In de getaltheorie, een deelgebied van de wiskunde, is het algoritme van Euclides een efficiënte methode voor het berekenen van de grootste gemene deler (ggd) van twee positieve gehele getallen. Het algoritme is vernoemd naar de Oud-Griekse wiskundige Euclides van Alexandrië, die het algoritme in de boeken VII en X van zijn Elementen beschreef. Het algoritme berust erop dat de ggd van twee gehele getallen ook de ggd is van zowel het kleinste getal als van de rest die overblijft bij deling van het grootste getal door het kleinste. Zo ontstaat er een aflopend iteratief proces. Er bestaat ook een uitgebreide variant van dit algoritme. (nl)
- Euklides algoritm är en algoritm för att bestämma största gemensamma delare till två heltal. Det är en av de äldsta kända algoritmerna och beskrivs i Euklides Elementa. Algoritmen kräver inte att man kan dela upp talen i faktorer. Algoritmen kan beskrivas på följande sätt: 1.
* Två heltal a och b, där a > b är givna. 2.
* Om b = 0 är algoritmen klar och svaret är a. 3.
* I annat fall beräknas c, resten när man delat a med b. 4.
* sätt a = b, b = c och börja om från steg 2 igen, (a får det värde b har och b får det värde c har). (sv)
- في الرياضيات، خوارزمية أقليدس (بالإنجليزية: Euclidean algorithm) هي طريقة فعالة تمكن من إيجاد القاسم المشترك الأكبر لعددين وهو أكبر عدد يقسم في نفس الوقت العددين معا بدون أي باق من القسمة. يُرمز له بالفرنسية ب PGCD وبالإنجليزية GCD. سميت هذه الخوارزمية هكذا نسبة إلى عالم الرياضيات الإغريقي أقليدس الذي وصف الخوارزمية لأول مرة في كتابه المعروف باسم الأصول (حوالي عام 300 ق.م). هي مثال عن الخوارزميات (الخوارزمية طريقةٌ تمكن من القيام بعملية ما، خطوة خطوة طِبقا لقواعد معينة محددة مسبقا). وهو من أقدم الخوارزميات اللائي ما زلن قيد الاستعمال. قد تستعمل من أجل اختزال كسر إلى شكله المبسط غير القابل للاختزال، وهي جزء من الحسابات المتعلقة بنظرية الأعداد والتشفير. (ar)
- L'algorisme d'Euclides és un mètode eficaç per a calcular el màxim comú divisor (mcd) entre dos nombres enters. Rep el nom del matemàtic grec Euclides el qual el va descriure en els volums VII i X del llibre Elements. mcd (a, b) = mcd (b, r1), amb r1 = a - b·q (q és el quocient de a per b) Després el menor dels divisors comuns és el mateix, i repetint l'operació: mcd (b, r1) = mcd (r1, r₂) = mcd (r₂, r₃) = ... = mcd (rn-1, rn) = mcd (rn-1, 0) = rn-1. Això permet detallar l'algorisme efectiu: (ca)
- Eukleidův algoritmus (též Euklidův) je algoritmus, kterým lze určit největší společný dělitel dvou přirozených čísel, tedy největší číslo takové, že beze zbytku dělí obě čísla. Jedná se o jeden z nejstarších známých netriviálních algoritmů a postupně vznikla řada jeho modifikací například pro příbuzné úlohy. Z nich nejdůležitější je rozšířený Eukleidův 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)
- Στα μαθηματικά, ο αλγόριθμος του Ευκλείδη ή Ευκλείδειος αλγόριθμος είναι μια αποτελεσματική μέθοδος για τον υπολογισμό του μέγιστου κοινού διαιρέτη (ΜΚΔ) δύο ακέραιων αριθμών, είναι επίσης γνωστός ως ο μεγαλύτερος κοινός παράγοντας ή υψηλότερος κοινός παρονομαστής. Το όνομά του προέρχεται από τον Έλληνα μαθηματικό Ευκλείδη, ο οποίος τον περιγράφει στα βιβλία VII και X του βιβλίου του Στοιχεία. (el)
- Der euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Mit ihm lässt sich der größte gemeinsame Teiler zweier natürlicher Zahlen berechnen. Das Verfahren ist nach dem griechischen Mathematiker Euklid benannt, der es in seinem Werk „Die Elemente“ beschrieben hat. Der größte gemeinsame Teiler zweier Zahlen kann auch aus ihren Primfaktorzerlegungen ermittelt werden. Ist aber von keiner der beiden Zahlen die Primfaktorzerlegung bekannt, so ist der euklidische Algorithmus das schnellste Verfahren zur Berechnung des größten gemeinsamen Teilers. (de)
- In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC).It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules,and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations. (en)
- L'algoritmo di Euclide è un algoritmo per trovare il massimo comune divisore (indicato di seguito con MCD) tra due numeri interi. È uno degli algoritmi più antichi conosciuti, essendo presente negli Elementi di Euclide intorno al 300 a.C.; tuttavia, probabilmente l'algoritmo non è stato scoperto da Euclide, ma potrebbe essere stato conosciuto anche 200 anni prima. Certamente era conosciuto da Eudosso di Cnido intorno al 375 a.C.; Aristotele (intorno al 330 a.C.) ne ha fatto cenno ne , 158b, 29-35. L'algoritmo non richiede la fattorizzazione dei due interi. (it)
- Algorytm Euklidesa – algorytm wyznaczania największego wspólnego dzielnika dwóch liczb. Został opisany przez greckiego matematyka, Euklidesa w jego dziele „Elementy”, w księgach siódmej oraz dziesiątej. (pl)
- Em matemática, o algoritmo de Euclides é um método simples e eficiente de encontrar o máximo divisor comum entre dois números inteiros diferentes de zero. É um dos algoritmos mais antigos, conhecido desde que surgiu nos Livros VII e X da obra Elementos de Euclides por volta de 300 a.C.. O algoritmo não exige qualquer fatoração. (pt)
- Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида (III век до н. э.), который впервые описал его в VII и X книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше время. (ru)
- 在数学中，辗转相除法，又称欧几里得算法（英語：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。 两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。例如，252和105的最大公约数是21（）；因为，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数为零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如。这个重要的結論叫做貝祖定理。 辗转相除法最早出现在欧几里得的《几何原本》中（大约公元前300年），所以它是现行的算法中歷史最悠久的。这个算法原先只用来处理自然数和几何长度（相當於正實數），但在19世纪，辗转相除法被推广至其他类型的數學對象，如高斯整数和一元多项式。由此，引申出欧几里得整环等等的一些现代抽象代数概念。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。 (zh)
- Алгоритм Евкліда (також називається евклідів алгоритм) — ефективний метод обчислення найбільшого спільного дільника (НСД). Названий на честь грецького математика Евкліда, котрий описав його в книгах VII та X Начал. Алгоритм Евкліда ефективно обчислює НСД великих чисел, оскільки виконує операцій не більше, ніж вп'ятеро більше кількості цифр меншого числа (в десятковій системі). Цю властивість було доведено Ґабріелем Ламе (англ. Gabriel Lamé) в 1844 році, що позначило початок теорії складності обчислень. Методи підвищення ефективності алгоритму були розроблені в XX столітті. (uk)
|
