Cryptography: The Extened Euclidean Algorithm

Important for later computations in the area of finite fields and in encryption algorithms, such as RSA

For given integers a and b, the extended Euclidean algorithm not only calculate the greatest common divisor d but also two additional integers x and y that satisfy the following equation.
                ax + by = d = gcd(a,b)
x and y will have opposite signs

Now let us show how to extend the Euclidean algorithm to determine (x, y, d) given a and b.
we assume that at each step i we can find integers xi and yi that satisfy ri = axi + byi.
We end up with the following sequence.

Now, we can rearrange terms to write ri = ri-2 - ri-1qi

Also, in rows i – 1 and i - 2, we find the values
ri-2 = axi-2 + byi-2 and ri-1 = axi-1 + byi-1

Substituting into ri, we have
ri = (axi-2 + byi-2) - (axi-1 + byi-1)qi

    = a(xi-2 – qi xi-1) + b(yi-2 – qi yi-1)

But we have already assumed that ri = axi + byi. Therefore,

  xi = xi-2 – qi xi-1 and yi = yi-2 – qi yi-1

In each row, we calculate a new remainder ri based on the remainders of the previous two rows, namely ri - 1 and ri - 2.

To start the algorithm, we need values for r0 and r- 1, which are just a and b.

It is then straightforward to determine the required values for x - 1, y- 1, x0, and y0.

We know from the original Euclidean algorithm that the process ends with a remainder of zero and that the greatest common divisor of a and b is d = gcd(a,b) = rn.

But we also have determined that d = rn = axn + byn.

As an example, let us use a=1759 and b=550 and solve for 1759x + 550y = gcd(1759, 550). The results are shown in Table below.

Thus, we have 1759 × (–111) + 550 × 355 = –195249 + 195250 = 1.

Cryptography: The Euclidean Algorithm

The Euclidean Algorithm finds the greatest common divisor of two integers a and b.

For example,
If we want to find gcd(287, 91), we divide 287 by 91:

                            287 = 91*3 + 14

We know that for integers a, b and c, if a | b and a | c, then a | (b + c).

Therefore, any divisor of 287 and 91 must also be a divisor of 287 - 91*3 = 14.

Consequently, gcd(287, 91) = gcd(14, 91).

In the next step, we divide 91 by 14:

91 = 14*6 + 7

This means that gcd(14, 91) = gcd(14, 7).

So we divide 14 by 7:

14 = 7*2 + 0
We find that 7 | 14, and thus gcd(14, 7) = 7.

Therefore, gcd(287, 91) = 7.

So, what is gcd( 70, 38 )?

------------------------------------------------------------------------------------------------------------------------
The Euclidean algorithm can be based on the following theorem: For any nonnegative integer a and any positive integer b,
            gcd(a, b) = gcd(b, a mod b)
        gcd(55, 22) = gcd(22, 55 mod 22) = gcd(22, 11) = 11

Cryptography: Number Theory - Euclidean Algorithm

Euclidean Algorithm 

•One of the basic techniques of number theory is the Euclidean algorithm, which is a simple procedure for determining the greatest common divisor of two positive integers.

•Relative Prime

•Two integers are relatively prime if their only common positive integer factor is 1.

Relatively Prime Integers 
Definition:

Two integers a and b are relatively prime if gcd(a, b) = 1.

Examples:

•Are 15 and 28 relatively prime?

–Yes, gcd(15, 28) = 1.

•Are 55 and 28 relatively prime?

–Yes, gcd(55, 28) = 1.

•Are 35 and 28 relatively prime?

–No, gcd(35, 28) = 7.

 

Greatest Common Divisor  

•Let a and b be integers, not both zero.

•The largest integer d such that d | a and d | b is called the greatest common divisor of a and b.

•The greatest common divisor of a and b is denoted by gcd(a, b).

•

•Example 1: What is gcd(48, 72) ?

–The positive common divisors of 48 and 72 are
1, 2, 3, 4, 6, 8, 12, 16, and 24, so gcd(48, 72) = 24.

•Example 2: What is gcd(19, 72) ?

–The only positive common divisor of 19 and 72 is
1, so gcd(19, 72) = 1.