support@assignmenthelp.net
+1-617-874-1011 (US)
+44-117-230-1145 (UK)
+61-7-5641-0117 (AU)
+44-117-230-1145 (UK)
+61-7-5641-0117 (AU)
The extension of standard Euclid algorithm is the Extended Euclidean algorithm. This algorithm computes the greatest common divisor (gcd) of two numbers and expresses the result (greatest common divisor) as a linear combination of the numbers used to calculate the gcd. The algorithm does not make use of factorization to compute the gcd of the numbers and is incredibly fast, even on extremely large numbers with thousands of digits.
In the context of computer algorithms, many textbooks consider recursive algorithms better than iterative ones. It is easy to establish the correctness of Recursive algorithms than the iterative version, forming the basis of the reason behind the previous theory. The recursive and iterative versions of extended Euclid’s algorithm vary up to a great degree. In most of the journals and publications, either the recursive or iterative version of an algorithm is presented, but not both. For example, the numbers involved are of hundreds of bits in length in case of implementation of RSA cryptosystems. In such cases, a recursive algorithm may be unacceptably slow. Let’s go through the basic concepts and implementation of standard and extended Euclidean algorithm.
Let’s say i1 and i2 are the largest integer that divides both i1 and i2. The Basic Euclidean Algorithm is a way to quickly find the greatest common divisor of integer i1 and i2. The time complexity of Euclid’s Algorithm is O (log min (i1, i2)).
The Euclid’s Algorithm for finding GCD (i1, i2) is as follows:
Let i1 = 250, i2 = 30. 250 = 30·8 + 10 gcd(250, 30) = gcd(30, 10) 30 = 10·3 + 0 gcd(30, 10) = 10 Therefore, gcd(250, 30) = 10. Let i1 = 420, i2 = 45. 420 = 45·9 + 15 gcd(420, 45) = gcd(45, 15) 45 = 15·3 + 0 gcd(45, 15) = 15 Therefore, gcd(420, 45) = 15. Let i1=2530, i2 = 56 2530 = 56.45 + 10 gcd(2530, 56) = gcd(56, 10) 56 = 10.5 + 6 gcd(56, 10) = gcd(10, 6) 10 = 6.1 + 4 gcd(10, 6) = gcd(6, 4) 6 = 4.1 + 2 gcd(6, 4) = gcd(4, 2) 4 = 2.2 + 0 gcd(4, 2) = 2 Therefore, gcd(2530, 56) = 2
PROGRAM:
#include < stdio.h >
// Function to calculate greatest common divisor of i1 and i2
int basic_euclid(int i1, int i2)
{
if (i1 == 0)
return i2;
return basic_euclid(i2%i1, i1);
}
// Program to implement Euclid’s Algorithm.
int main()
{
int i1 = 25, i2 = 35;
printf("basic_euclid(%d, %d) = %d\n", i1, i2, basic_euclid(i1, i2));
i1 = 15, i2 = 10;
printf("basic_euclid(%d, %d) = %d\n", i1, i2, basic_euclid(i1, i2));
i1 = 18, i2 = 24;
printf("basic_euclid(%d, %d) = %d\n", i1, i2, basic_euclid(i1, i2));
return 0;
}
OUTPUT:
basic_euclid(25, 35) = 5
basic_euclid(15, 10) = 5
basic_euclid(18, 24) = 6
The Extended Euclidean algorithm is also used to find integer coefficients c and d of integers i1 and i2 such that:
i1c + i2d = GCD (i1, i2)
This theorem tells us that if i1 and i2 are relatively prime, then the numbers, c, and d, can be determined such that:
i1c + i2d = 1
As a consequence of this, if i1 and i2 are not relatively prime and have a greatest common divisor g, then the numbers, c and d, can be determined such that:
i1c + i2d = g
The time complexity of Extended Euclidean Algorithm is O (log (m)^2), assuming |i1| < m.
The theory behind Standard Euclidean Algorithm is to preserve, at the end of every step, the value of r using the integers i1 and i2. This can be done using the division algorithm.
r can be expressed using i1, q, and i2:
r = i1 – qi2
where q is the quotient when i1 is divided by i2.
As we know, gcd(56, 10) = gcd(10, 6) = gcd(6, 4) = gcd(4, 2) = gcd(2, 0) = 2 Let’s, make computations in a backward direction to write 2 as a linear combination of 2530 and 56: 2 = 6 - 4 We are getting 2 as a linear combination of 6 and 4, i.e. = 6 − (10 − 6) = 2(6) − 10 We are getting 2 as a linear combination of 6 and 10, i.e. = 2(56 − 5 × 10)) − 10 = 2 × 56 − 11 × 10 Now 2 is a linear combination of 56 and 10
PROGRAM:
#include < stdio.h >
// function to calculate Extended Euclidean algorithm
int gcdExtended(int i1, int i2, int *c, int *d)
{
// when the value of i1 = 0 (base case)
if (i1 == 0)
{
*c = 0;
*d = 1;
return i2;
}
int c1, d1;
int val = gcdExtended(i2%i1, i1, &c1, &d1);
*c = d1 - (i2/i1) * c1;
*d = c1;
return val;
}
// Program to implement Extended Euclid’s Algorithm.
int main()
{
int c, d;
int i1 = 25, i2 = 35;
int val1 = gcdExtended(i1, i2, &c, &d);
printf("gcd(%d, %d) = %d,\n c = %d, d = %d",
i1, i2, val1, c, d);
return 0;
}
OUTPUT:
gcd(25, 35) = 5,
c = 3, d = -2
According to the Bezout's Identity,
For any pair of positive integers, i1 and i2, there exist c, d ∈ Z
so that,
i1 c + i2 d = gcd (i1, i2)
Proof:
As per the below set,
k = { i1 c + i2 d | c, d ∈ Z} (1)
Let k be the smallest positive element of K. Since k ∈ K, there are c, d ∈ Z, so that
k = i1 c + i2 d (2)
Z belongs to Euclidean Domain, hence it can be formulated that
i1 = q k + r with 0 ≤ r < k (3)
Therefore, the value of r can be substituted as,
r = i1 – q k
= i1 – q ( i1 c + i2 d )
= i1 ( 1 – q c ) + i2 ( −q d ) ∈ K (4)
Since k is the smallest positive element in K, (3) and (4) imply that r must be 0.
Thus, i1 = q k, and therefore, k divides i1. Similarly, k divides i2. Thus, k is a common divisor of i1 and i2,
Therefore,
k ≤ gcd ( i1, i2)
Since both i1 and i2 are divisible by gcd ( i1, i2), and k = i1 c + i2 d, gcd ( i1, i2 ) divides k.
Since both k and k ≤ gcd ( i1, i2) is divisible by gcd ( i1, i2), it can be computed that k = gcd ( i1, i2).
Thus, (2) becomes,
gcd ( i1, i2) = i1 c + i2 d (5)
Calculating the inverse of the modulus function of one number to another is a common practice in cryptography.
Let’s take an example where
x y = 1 mod 317
In such expressions, it is very difficult and time-consuming process to calculate the value of x for any given value of y.
The value of this inverse function can be computed elegantly using the Extended Euclidean Algorithm. It does so by calculating the greatest common divisor (gcd) of two integers x and y.
The inverse of x exists if and only if gcd(x, n) = 1.
This tells us that there exists an integer y, for an integer s, such that xy + sn =1, and y is the modular inverse, i.e. the inverse of x mod n.
The above steps can be followed to calculate y, using the Extended Euclidean function:
We will be using “qi” at step number i to denote the quotient obtained. While proceeding with the steps of the Euclidean algorithm, the value of an auxiliary number “yi” will be calculated as well.
In the first and second step, the value of the auxiliary number is given as:
y0 = 0 and y1 = 1.
While in all the further steps, the value of the auxiliary number will be calculated recursively as:
yi = yi-2 - yi-1 qi-2 (mod n).
This calculation is continued using Euclidean algorithm till the last step and one step beyond the last step.
The algorithm works by dividing the value of n by the value of x. The number x does not have an inverse if the value of the last non-zero remainder is not 1. Whereas, If the remainder is one and the last non-zero remainder occurs at step k, x has an inverse and the value of the inverse is yk+2.
Let’s go through the below example to calculate the inverse of 10 mod 56.
Step 0: 56 = 5(10) + 6 Step 1: 10 = 1(6) + 4 Step 2: 6 = 1(4) + 2 Step 3: 4 = 2(2) + 0
It can be seen from the step number 2, that the value of last non-zero remainder is not equal to 1. Hence the inverse of i1 i.e. 56 does not exists.
The Extended Euclidean Algorithm works exceptionally in the case of cryptography and has a wide range of applications other than cryptography.
Assignment Writing Help
Engineering Assignment Services
Do My Assignment Help
Write My Essay Services