The Euclidean Algorithm


The Euclidean Algorithm

and prime field arithmetic
 

The GCD

• gcd(n, m), is the greatest common
divisors of n , m:

–gcd(n, m) = MAX { d; d divides n & m}

• Fact:

– If c = gcd(n, m),
– and b divides both n and m,
– then b also divides the g.c.d. c.
 

Computing the g.c.d.

• The g.c.d. of two numbers can be
computed using the Euclidean algorithm

• Based on the fact that, given a linear
combination:

–a = mb + c

• then gcd(a, b) = gcd(b, c)
 

Integer long division

• Given a and b, there are values q and
r, called the quotient and remainder of
the division of a by b such that:

– r ≥ 0;
– r < |b|;
– a = b q + r
 

Euclides’ Algorithm for g.c.d.

• Given n and m, find g.c.d. of n, m.

GCD(n, m)
IF m = 0 RETURN n
r ← REMAINDER(n, m);
RETURN GCD(m, r);
 

Examples
 

• GCD(12, 9)
FALSE ← IF(9 = 0)
r ← 3 = REMAINDER(12,9)
RETURN GCD(9, 3)

• GCD(9, 3)
FALSE ← IF(3 = 0)
r ← 0 = REMAINDER(9,3)
RETURN GCD(3, 0)

• GCD(3,0)
TRUE ← IF(0 = 0)
RETURN 3

 
• GCD(-5, 4)
FALSE ← IF(4 = 0)
r ← 3 = REMAINDER(-5, 4)
RETURN GCD(4, 3)

• GCD(4, 3)
FALSE ← IF(3 = 0)
r ← 1 = REMAINDER(4,3)
RETURN GCD(3, 1)

• GCD(3, 1)
FALSE ← IF(3 = 0)
r ← 0 = REMAINDER(3,1)
1 ← RETURN GCD(1, 0)

 


The GCD as a linear function

• The Euclides algorithm has the
following property:

– Each new recursive invocation has
parameters n’, m’ which are a linear
transformation of the parameters n, m of
the current function call.

• n’ = m
• m’ = REMAINDER(n,m) =
 

Backtracking

• Since in each step the next set of parameters
are a linear combination of the previous set ,
each set of parameters is a linear combination of
the initial parameters (by induction).

– Initial set of parameters: n, m
– Final set of parameters: c, 0, where c = GCD(n, m)

• So c = a n + b m, and a and b can be
computed by recording the intermediate
transformation taken by the algorithm.
 

Extended g.c.d. algorithm

• Define values a, b, c, d such that, in
the i-th step of the GCD computation:



• EXT-GCD(n, m, a, b, c, d)
IF m = 0 RETURN n, a, b
r ← REMAINDER(n, m) = n - q m
RETURN
EXT-GCD(m, n-qm, c, d, a-qc, b-qd)
 

Example

• GCD(12, 9,1,0,0,1)
FALSE ← IF(9 = 0)
r ← 3 = REMAINDER(12,9) = 12 - 1 * 9 (q = 1)
RETURN GCD(9, 3, 0, 1, 1, -1)

• GCD(9, 3, 0, 1, 1, -1)
FALSE ← IF(3 = 0)
r ← 0 = REMAINDER(9, 3) = 9 - 3 * 3 (q = 3)
RETURN GCD(3, 0, 1, -1, -3, 4)

• GCD(3,0)
TRUE ← IF(0 = 0)
RETURN 3, 1, -1
 
Testing:
Initial: 12 = 1*12 + 0*9
9 = 0 *12 + 1*9
Final: 3 = 1*12 - 1*9
0 = -3*12 + 4*9

 


Modular arithmetic

Finite number sets
 

Rings

• A commutative ring is a set S with two
arithmetic operations :
– Addition: +
– Multiplication: ·
• and two special elements:
– Additive identity: 0
Multiplicative identity : 1, Id, e
 

Ring properties

• Associativity of addition and multiplication:

– a + (b+c) = (a+b) + c; a · (b · c) = (a · b) · c

• Commutativity of addition and multiplication:

– a + b = b + a; a · b = b · a;

• Identity elements:

– a + 0 = a = 0 + a; a · Id = a = Id · a;

• Additive inverse:

– For each a, there is a’ such that a + a’ = 0

• Distributivity:

– a · (b + c) = a · b + a · c
 

Examples of rings

• The set of integer Z, rational Q , real R, and complex
C numbers.

• Non-commutative rings are rings where only addition
is commutative.

– Example: The set of n×n matrices is a non-commutative ring.

• If multiplication is both commutative and has an
inverse, i.e:

– For each a ≠ 0, there is a* such that a · a* = 1
then we say that the ring is a field.

• The rings of rational Q, real R, and complex C
numbers
are fields, but not the ring of integers Z.
 

Finite rings

• If m is an integer, then for all other
integers n, the function
– REMAINDER(n, m)

has values in the set {0, 1, ..., m-1}

• We wish to define a ring structure in
the above set, which we will call Zm.

• We need to define addition and
multiplication operations within Zm.
 

Remainder addition

• if r = REMAINDER(a, m), and s =
REMAINDER(b, m) then:

– r = a - pm, and s = b - qm for some p, q.

– Consider t = REMAINDER(r ± s, m)

• t = REMAINDER(a - pm ± (b - qm), m)
• t = REMAINDER(a ± b - pm ± (-qm), m)
• t = REMAINDER(a ± b, m)

• Define r ± s in Zm as
– REMAINDER(r ± s, m).
 

Remainder addition properties

• The addition/ subtraction of remainders
value (previous slide) must have the same
properties of addition /subtraction of
integers, because to add/subtract two
remainders we can first substitute the
remainders
by integers, add/subtract them
and then take the remainder.

• Multiplication of REMAINDERS is defined
analogously.
 

Example: Z5


 


Non- zero elements and
multiplication

• The multiplicative table of Z5 shows
that it is a field, because every nonzero
element has an inverse:

– 2 * 3 = 4 * 4 = 1 * 1 mod 5

• This is not true of all remainder rings:
 
Multiplication in Z4

 


Remainder fields

• When is the set Zm a field?

• For an element n to be inversible mod
m, there must exist p such that:

– n · p = 1 mod m; this is equivalent to
– n p - km = 1, for some k, which is the
same as:
– gcd(n, m) = 1
 

The fields Zm

• If Zm is to be a field, then every nonzero
remainder r must have

– gcd(r, m) = 1

• In particular, gcd(r, m) = 1 for

– r = 2, 3, ..., m - 1.

• This means that m must be a prime
number.
 

Dividing in Zm

• Whether or not m is a prime and Zm a
field, in order to compute division a/b
in Zm.

– a/b := a · (inverse of b) = a · b-1
– b-1 = c such that b * c + k m = 1
– c is the coefficient that is computed using
extended g.c.d algorithm:
– ext-gcd(b, m) = 1, c, k
 

Cryptography and modular
arithmetic

• In cryptography, two types of
remainder rings are very important

– The field Zp , when p is a prime.

– The ring Zn , when n = p q is a product of
two primes

• We will see these examples when
discussing the RSA algorithm.
 
Prev Next