Wednesday, September 11, 2013

Notes - Basic Notions

The following are notes from Introduction to Cryptography with Coding Theory.
  • Divisibility
    • let a and b be integers with a ≠ 0. a divides b if there is an integer k such that b = ak, or that b is a multiple of a. This is denoted by a|b
    • 3|15, -15|60
    • Proposition
      • for every a ≠ 0, a|0 and a|a. Also, 1|b for every b
      • if a|b and b|c, then a|c
      • if a|b and a|c then a|(sb + tc) for all integers s and t
  • Prime Numbers
    • A number p > 1 that is divisible by only 1 and itself is a prime number, any number that is not prime is called composite
    • Prime Number Theorem
      • Let π(x) ~ x/(ln x) where π(x) is the number of primes less than x in the sense that π(x)/x/(ln x) ->1 as x->
      • Example
        • 100 digit primes
        • π(10100) - π(1099) ~ 10100/(ln 10100) - 1099/(ln 1099) ~ 3.9 x 1097
    • Theorem - Every Positive Integer is a product of primes, and this factorization is unique up to a reordering of the factors
      • Lemma - If p is a prime and p divides a product of integers ab, then either p|a or p|b. More generally if a prime p divides a product ab...z then p must divide one of the factors a,b,...z
        • Therefore an integer can be written as the product of its prime factors to a given power
  • Greatest Common Divisor
    • GCD is the largest positive integer dividing both a and b
      • example gcd(6,4)=2; gcd(24,60)  = 12
    • Factor both numbers into primes, and take the smallest of the common divisors and multiply them together
    • Euclidean algorithm
      • Example gcd(482,1180)
        • 1180 = 2 * 482 +216
        • 482 = 2 * 216 + 50
        • 216 = 4 * 50 + 16
        • 50 = 3 * 16 + 2
        • 16 = 8 * 2 + 0
      • Since 2 was the last nonzero remainder, the gcd is 2
    • divide a by b in the form
      • a = q1 b + r1
      • if r = 0 then b divides a and the greatest common divisor is b if r ≠ 0 then continue with
      • b = q2 r1+ r2
      • rk-2= qk rk-1 + rk
      • rk-1= qk+1 rk 
      • gcd(a,b) = rk
    • Theorem - Let a and b be two integers with at least one of a,b nonzero, and let d = gcd(a,b). Then there exist integers x, y such that ax + by = d. In particular, if a and b are relatively prime, then there exist integers x,y with ax + by = 1.
    • Corollary - If p is a prime and p divides a product of integers ab,then either p|a or p|b. More generally if a prime p divides a product ab,...z then p must divide one of the factors a,b,...z

No comments:

Post a Comment