Try our Free Online Math Solver!

Online Math Solver
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


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 ith step of the GCD computation: • EXTGCD(n, m, a, b, c, d) IF m = 0 RETURN n, a, b r ← REMAINDER(n, m) = n  q m RETURN EXTGCD(m, nqm, c, d, aqc, bqd) 

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


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. • Noncommutative rings are rings where only addition is commutative. – Example: The set of n×n matrices is a noncommutative 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, ..., m1} • We wish to define a ring structure in the above set, which we will call Z_{m}. • We need to define addition and multiplication operations within Z_{m}. 

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 Z_{m} 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: Z_{5}


Non zero elements and multiplication • The multiplicative table of Z_{5} 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:


Remainder fields • When is the set Z_{m} 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 Z_{m } • If Z_{m} 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 Z_{m } • Whether or not m is a prime and Z_{m} a field, in order to compute division a/b in Z_{m}. – 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: – extgcd(b, m) = 1, c, k 

Cryptography and modular arithmetic • In cryptography, two types of remainder rings are very important – The field Z_{p} , when p is a prime. – The ring Z_{n} , when n = p q is a product of two primes • We will see these examples when discussing the RSA algorithm. 
Prev  Next 