Report

COM5336 Cryptography Lecture 11 Euclidean Domains & Division Algorithm Scott CH Huang Scott CH Huang COM 5336 Cryptography Lecture 10 Groups • Binary operations on a set is a mapping • A set w/ an operation satisfying 1. 2. 3. 4. Closure Associativity Identity Inverse • The most fundamental algebraic structure • Semi-groups: 1 & 2 only. • Abelian groups: commutative groups. Scott CH Huang COM 5336 Rings • A set R with two operations: + and *. – +: commutative. – *: not necessarily commutative. • • • • (R,+) forms an abelian group. (R,*) forms a semi-group (i.e. no identity and inverse) Distributivity Ring v.s. Ring with 1 (mult. identity). Scott CH Huang COM 5336 Integral Domains • Domain = Ring w/o zero-divisors – ab=0 implies a=0 or b=0 – One-sided cancellation law • Integral Domain = Commutative domain w/ 1. – Two-sided cancellation law Scott CH Huang COM 5336 Euclidean Domains • A Euclidean Domain is an integral domain with the notion of size. • The notion of size enables us to apply the Division Algorithm and therefore Euclid’s Algorithm. • Size of a≠0, denoted by g(a) is a nonnegative integer s.t. – g(a)≤g(ab), for all b≠0. – For all a,b≠0, there exists q,r s.t. a=qb+r, w/ r=0 or g(r)<g(b) Scott CH Huang COM 5336 Division Algorithm • A theorem in mathematics which precisely expresses the outcome of the usual process of division of integers. • Its name is a misnomer. • It is not a true algorithm. – A well-defined procedure for achieving a specific task Scott CH Huang COM 5336 Division Rings • A ring with unit in which division is possible. – i.e. every nonzero element has a multiplicative inverse. • A division ring is NOT necessarily commutative. – But finite division rings must be commutative (Wedderburn's little theorem). • A field is a commutative division ring. – Therefore all finite division rings are finite fields. Scott CH Huang COM 5336 Relationship of Algebraic Structures Ring Ring w/ unit Commutative ring w/ unit Integral Domain Euclidean Domain Scott CH Huang Field COM 5336 Division Ring Division in a Euclidean Domain • a|b: ‘a’ divides ‘b’ iff there exists c s.t. b=ac – a,b,c D, a Euclidean domain. • If a|b1, a|b2,…, then a is a common divisor of b1,b2,… • If d is a common divisor of b1,b2,…, and every common divisor divides d, then d is a greatest common divisor (GCD) of b1,b2,… • In fact, the concept of GCD can be extended to certain integral domains called Principal Ideal Domains. Scott CH Huang COM 5336 GCD in Algebraic Structures algebraic structure requirement properties loose GCD can be defined. Pricipal Ideal Domain stricter GCD can be defined and exists. Euclidean Domain strictest GCD can be defined and can be found Integral Domain Scott CH Huang COM 5336 GCD may not exists in an Integral Domain Note that Both d1, d2 are common divisors of b1, b2 , so b1, b2 has no greatest common divisors. Scott CH Huang COM 5336 GCD exists in a Euclidean Domain • If , then d can be expressed as a linear combination of a,b. • If D is a Euclidean domain and , then d can be expressed as a linear combination of a,b • How to calculate the GCD? Scott CH Huang COM 5336 Euclid’s Inspiring Lemma • gcd(s,t)=gcd(s,t-rs) for all s,t,r in a Euclidean domain D. • This lemma directly results in Euclid’s algorithm. Scott CH Huang COM 5336 Euclid’s Algorithm int gcd(s,t){ while (s!=0){ u=s; s= t mod s; t=u; } return t; } Scott CH Huang COM 5336 Theorem #1 Let t be an element in a Euclidean domain D and m,n be two positive integers. Then *Hint: (tn-1)-tn-m (tm-1)= tn-m -1 Scott CH Huang COM 5336 Corollary #1 Let x be an element in a Euclidean domain D and q,n,d be positive integers. Then Scott CH Huang COM 5336 Conceptually Group +, - Ring +, -, * Integral Domain +, -, * and “cancellation” Euclidean Domain +, -, * and “division algorithm” Field +, -, *, / Scott CH Huang COM 5336 Some Examples • • • • • Euclidean domain ring w/ 1 finite field commutative ring w/ 1 Euclidean domain Scott CH Huang COM 5336 More Examples (cont’d) • The set of polynomials over an arbitrary field with polynomial addition & multiplication. • The set of polynomials with two variables x,y over an arbitrary field with polynomial addition & multiplication. Scott CH Huang COM 5336 Factorization in Euclidean Domains • We wish to establish a “Fundamental Theorem of Arithmetic” in Euclidean domains. • Fundamental Theorem of Arithmetic (aka Unique-Prime-Factorization Theorem) – Any integer greater than 1 can be written as a unique product (up to ordering of the factors) of prime numbers. • In order to do that, it’s vital to introduce the idea of a “prime number” in Euclidean domains. Scott CH Huang COM 5336 Preliminaries • Let D be an integral domain. A unit u D is any divisor of 1. – In the integer ring, the units are ±1. In the Gaussian integer ring, ±1, ±i are units. • a, b D are associates if a=ub for some unit u. – In the integer ring, +3, -3 are associates. In the Gaussian integer ring, 1+ i, 1- i are associates. • A factorization of b is an expression of the form b=a1a2· · · ar. If each of the ai’s are either a unit or an associate of b, this is a trivial factorization. Scott CH Huang COM 5336 Irreducible Elements in Integral Domains • A element p D, an integral domain, is called irreducible iff every factorization of p is trivial. • We do not consider units to be irreducible. • b D. d|b. If d is not an associate of b, then it is called a proper divisor. • Irreducible elements have no proper divisors other than units. Scott CH Huang COM 5336 Primes in Integral Domains • A nonzero, non-unit element p D, an integral domain, is called prime iff the following property holds. – If p|ab, then either p|a or p|b for a,b D. Scott CH Huang COM 5336 Primes vs Irreducible Elements • In an integral domain, every prime is irreducible. • In a Principal Ideal Domain (PID), every irreducible element is prime. • In our textbook, only Euclidean domains are discussed. The author did not distinguish between primes and irreducible elements and regarded them as synonyms. Scott CH Huang COM 5336 Relative Primality • In a PID, two elements a,b are relatively prime iff gcd(a,b)=1. (remember that GCD must exists in a PID) • In a Euclidean domain, if p does not divide a and p is prime, then p and a are relatively prime. Scott CH Huang COM 5336 Some Properties • In a Euclidean domain, if p does not divide a, then there exist s,t such that ps+at=1. • In a Euclidean domain, if a is a proper divisor of b, then g(a)<g(b). Scott CH Huang COM 5336 Unique Factorization • Theorem 3.6: In a Euclidean domain, if b is not a unit, then b can be factorized as a product of primes: – b=p1p2 · · · pn – If b can be factorized in another way as b=q1q2 · · · qn , then after appropriate renumbering, pi qi are associates for all i. • In short, Euclidean domains are Unique Factorization Domains (UFD). Scott CH Huang COM 5336 Euclidean Domains, PIDs, UFDs Integral Domain Unique Factorization Domain *Principal Ideal Domain* Euclidean Domain Field Scott CH Huang COM 5336 Example of a non-UFD • Consider the integral domain • • are irreducible. Scott CH Huang COM 5336