大学安全工程之密码学2第二章 密码学的数学基础.pdfVIP

• • • 1 • A(0),B(1),…,Z(25) • 2 • b ma, a b 2 6,3 18,−5 25,3 8? • −a b ∧b c ⇒a c a b b a a b − ∧ ⇒ −a b ∧a c ⇒a bx ±cy proof ? 3 • p+p, -p,+1,-1 2,3,5,7,11,13,17,…,101,… • P • n 4,9,187,900,… 4 • Theorem:(Fundamental Theorem of Arithmetic) e1 e2 ek ei ∀n∈N n= p1 p2 …pk ( or Π p ) p ∈P i where ep is the exponent of the prime factor p • Note: the result of factorization is unique • Example: 84=22×3×7 5 • Theorem: There are infinitely many primes • Proof: (by contradiction) Assume P , build a number N is max N P P ...P +1 1 2 max There N is a new prime. 6 • Definition: the greatest common divisor (GCD) is the number c c gcd(a,b) max{d d a ∧d b} • Properties: •d n1, d n2 ,..., d nk ⇒d gcd(n1,..., nk ) gcd( , ) gcd( , mod ) • a b b a b : mod 0 proof