网络安全技术电信群楼3-509
网络安全技术 电信群楼3-509 1
Number TheoryWe work on integers only2
2 Number Theory We work on integers only
DivisorsTwo integers: a and b (b is non-zero) b divides a if there exists some integer m such that a =m·b Notation: blaeg. 1,2,3,4,6,8,12,24 divide 24 bisadivisorofaRelations1.If b/1 b=±12.= b =±aIf bla and a|b3.If blo= anyb+o4.If blg and b|h then b I (mg + nh) for any integers m and n3
3 Divisors Two integers: a and b (b is non-zero) ❑ b divides a if there exists some integer m such that a = m·b ❑ Notation: b|a ❑ eg. 1,2,3,4,6,8,12,24 divide 24 ❑ b is a divisor of a Relations 1. If b|1 b = 1 2. If b|a and a|b b = a 3. If b|0 any b 0 4. If b|g and b|h then b | (mg + nh) for any integers m and n
Congruenceais congruenttob modulon if nIa-bNotation:a=b(modn)Examples1. 23 = 8 (mod 5)because 5 123-82. -11 = 5 (mod 8)because 8 /-11-53. 81 = 0 (mod 27)because 27 |81-0Properties1. a=a(modn)2. a= b (mod n) implies b = a (mod n)3.a = b (mod n) and b = c (mod n) imply a = c (mod n)4
4 Congruence a is congruent to b modulo n if n | a-b. Notation: a b (mod n) Properties 1. a a (mod n) 2. a b (mod n) implies b a (mod n) 3. a b (mod n) and b c (mod n) imply a c (mod n) Examples 1. 23 8 (mod 5) because 5 | 23-8 2. -11 5 (mod 8) because 8 | -11-5 3. 81 0 (mod 27) because 27 | 81-0
Modular Arithmeticmodularreduction:amod n=rristheremainderwhenaisdividedbyanaturalnumbernrisalsocalledtheresidueofamodnit can be represented as: a = gn + r where o<r < n, g = La/nJwhereLxJis thelargest integerlessthanorequal toxq is called the quotient18mod 7 = ?29345723547mod2=?Relationbetweenmodularreductionandcongruence-12=-5=2=9(mod 7)-12 mod 7 = 2 (what's the quotient?)For any integers a, b and positive integer m, a =b (mod n)iff amodn=bmod n.5
5 Modular Arithmetic ◼ modular reduction: a mod n = r r is the remainder when a is divided by a natural number n ◼ r is also called the residue of a mod n ▪ it can be represented as: a = qn + r where 0 r < n, q = a/n where x is the largest integer less than or equal to x ▪ q is called the quotient ◼ 18 mod 7 = ? ◼ 29345723547 mod 2 = ? ◼ Relation between modular reduction and congruence ▪ -12 ≡ -5 ≡ 2 ≡ 9 (mod 7) ▪ -12 mod 7 = 2 (what’s the quotient?) ▪ For any integers a, b and positive integer m, a b (mod n) iff a mod n = b mod n