English | Español

Try our Free Online Math Solver!

Online Math Solver

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


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