204211-src-51-1

เนื้อหา

การนับ
- นับเบื้องต้น เส้นตรง, วงกลม, nCr, nPr
- inclusion-exclusion techniques
  - bijections
- advanced counting (placing rods)

Proof Techniques
- logics
- direct proof
- indirect proof
- proof by contradiction

$ --- absence, to be covered

review basic induction & counting.
inclusion-exclusion principles.
using bijection in counting. (without actually define what a bijection is)
- a bijection between subsets and bitstrings
- a bijection between odd-sized subsets and even-sized subsets
  - gave out idea of the bijection without proof: will be in homework
- proof of the inclusion-exclusion principle (sketch)

review of modular arithmatics
- basic identities
- if $\gcd(a,b)=1$ $\gcd(a,b)=1$ then $a^{-1}{\pmod {p}}$ $a^{-1}{\pmod {p}}$ exists.
  - the proof didn't use the fact that a pair $x,y$ such that $ax+by=\gcd(a,b)$ exists
RSA, Euler's Theorem, and Fermat's Little Theorem (without proofs)
TODO: (Homework) RSA by hand, Proof of Fermat's Little Theorem
NEXT: Proof of Euler's Theorem and correctness of RSA

Number Theory
- Review of RSA, why hacking RSA is hard, its assumption (hard to factor large numbers)
  - Need large primes to do RSA
- Primality testing
  - Testing in exponential time ($O(p)$ and $O(\sqrt{p})$ for testing $p$)
    - Proved (quick): for a composite $a$, one of its factor must be at most $\sqrt{a}$
  - Testing based on Fermat's Little Theorem
    - Implementation of the test: Repeated squaring
    - Success probability of the test and Carmicheal number
  - Proof of Fermat's Little Theorem
- Euler Theorem and RSA
  - Idea of the proof of Euler Theorem (should be completed in h.w.)
  - Euler Theorem => Correctness of RSA
Recursions
- Recursive definition and counting
- Recursive algorithms, divide and conquer