(2)
The Euclidean Algorithm
Introduction
The Euclidean Algorithm is used to discover the greatest common divisor of two integers. In cryptography, it is most often used to determine if two integers are coprime, i.e. - .
In order to find where efficiently when working with very large numbers, as with cryptosystems, a method exists to do so. The Euclidean algorithm operates as follows - First, divide by , writing the quotient , and the remainder . Note this can be written in equation form as . Next perform the same operation using in s place: . Continue with this pattern until the final remainder is zero. Numerical examples and a formal algorithm follow which should make this inherent pattern clear.
Mathematical Description
When , stop with .
Numerical Examples
Example 1 - To find gcd(17,043,12,660)
17,043 = 1 12,660 + 4383
12,660 = 2 4,383 + 3894
4,383 = 1 3,894 + 489
3,894 = 7 489 + 471
489 = 1 471 + 18
471 = 26 18 + 3
18 = 6 3 + 0
gcd (17,043,12,660) = 3 \
Example 2 - To find gcd(2,008,1,963)
2,008 = 1 1,963 + 45
1,963 = 43 45 + 28
45 = 1 28 + 17
28 = 1 17 + 11
17 = 1 11 + 6
11 = 1 6 + 5
6 = 1 5 + 1
5 = 5 1 + 0
gcd (2,008,1963) = 1 Note: the two number are coprime.
Algorithmic Representation
Euclidean Algorithm(a,b)
Input: Two integers a and b such that a > b
Output: An integer r = gcd(a,b)
1. Set a0 = a, r1 = r
2. r = a0 mod r1
3. While(r1 mod r 0) do:
4. a0 = r1
5. r1 = r
6. r = a0 mod r1
7. Output r and halt
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
|