ผลต่างระหว่างรุ่นของ "204211-src-51-1"

รุ่นแก้ไขเมื่อ 03:37, 31 สิงหาคม 2551

การนับ
- นับเบื้องต้น เส้นตรง, วงกลม, 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
- 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
- Proof of Euler Theorem and RSA
Recursions
- Recursive definition and counting
- Recursive algorithms, divide and conquer

@@ แถว 61: / แถว 61: @@
 ** 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