"Bài giảng Cơ sở toán học cho mật mã (Mathematical Background)" cung cấp đến người học các kiến thức về lý thuyết xác suất, lý thuyết thông tin, lý thuyết độ phức tạp, lý thuyết số, đại số trừu tượng, trường hữu hạn. | Cơ sở toán học cho mật mã Mathematical Background TS. Huỳnh Trọng Thưa htthua@ Contents 1. Probability theory 2. Information theory 3. Complexity theory 4. Number theory 5. Abstract algebra 6. Finite fields 2 Division algorithm for integers If a and b are integers with b 1 then division of a by b yields integers q the quotient and r the remainder such that a qb r where 0 r Common divisor ước số chung An integer c is a common divisor of a and b if c a and c b. d is the greatest common divisor ước số chung lớn nhất of integers a and b denoted d gcd a b if i d is a common divisor of a and b and ii whenever c a and c b then c d. Equivalently gcd a b is the largest positive integer that divides both a and b with the exception that gcd 0 0 0. Example the common divisors of 12 and 18 are 1 2 3 6 and gcd 12 18 6. 4 Least common multiple bội số chung nhỏ nhất d is the least common multiple of integers a and b denoted d lcm a b if i a d and b d and ii whenever a c and b c then d c. Equivalently lcm a b is the smallest non-negative integer divisible by both a and b. If a and b are positive integers then lcm a b a b gcd a b . Example Since gcd 12 18 6 it follows that lcm 12 18 12 18 6 36. 5 Coprime nguyên tố cùng nhau Two integers a and b are said to be coprime if gcd a b 1. An integer p 2 is said to be prime nguyên tố if its only positive divisors are 1 and p. Otherwise p is called composite hợp số . If p is prime and p ab then either p a or p b or both . There are an infinite number of prime numbers. 6 Euclidean algorithm computing the greatest common divisor of two integers ước số chung lớn nhất INPUT two non-negative integers a and b with a b. OUTPUT the greatest common divisor of a and b. 1. While b 0 do the following r a mod b a b b r. 2. Return a . 7 Example of Euclidean algorithm computing gcd 4864 3458 38 4864 1 3458 1406 3458 2 1406 646 1406 2 646 114 646 5 114 76 114 1 76 38 76 2 38 0. 8 Extended Euclidean algorithm 9 Ex of extended Euclidean algorithm
