|
|
| แถว 56: |
แถว 56: |
| | <math>Pr[</math>ถังใบแรกว่าง<math>] = </math><math>(1 - \frac{1}{n}) ^ n</math> | | <math>Pr[</math>ถังใบแรกว่าง<math>] = </math><math>(1 - \frac{1}{n}) ^ n</math> |
| | | | |
| − | ==ตัวหารร่วมมาก (grestest common divisors)== | + | ==Random Variable== |
| − | ตัวหารร่วมมาก (gcd) ของ a และ b คือจำนวนเต็มที่มากที่สุดที่หาร a และ b ลงตัวแทนด้วย gcd(a,b)
| |
| | | | |
| − | ;Thm: ให้จำนวนเต็ม a ,m a จะมี inverse การคูณ modulo m เมื่อและต่อเมื่อ gcd(a,m) = 1 | + | ;นิยาม สำหรับตัวแปรสุ่ม X |
| − | ;Proof:
| |
| − | (<=) สมมุติ gcd(a,m) = 1
| |
| − | :พิจารณา
| |
| − | :: 0 mod m
| |
| − | :: a mod m
| |
| − | :: 2a mod m
| |
| − | :: 3a mod m
| |
| − | :: . . .
| |
| − | ::(m-1)a mod m
| |
| | | | |
| − | ;claim 1: จำนวนเหล่านี้ไม่เท่ากันเลย
| + | <math>E[X] = \sum i Pr[X=i]</math> |
| − | ----
| |
| − | จาก claim 1 จะมีจำนวนเต็ม b ที่อยู่ระหว่าง 0 <= b <= m-1 ที่ b*a mod m = 1 เนื่องจากมีจำนวน m จำนวนไม่ซ้ำกันจากค่าที่เป็นไปได้ระหว่าง 0 ถึง m-1
| |
| − |
| |
| − | ;Proof Claim1:
| |
| − | สมมุติให้มีจำนวนเต็ม i =/= j ที่ 0 <= i ,j<= m-1
| |
| − | ที่ i*a mod m = j*a mod m
| |
| − | จะได้ i*a \eqv j*a (mod m)
| |
| − | หรือ m| i*a - j*a => m|(i-j)*a
| |
| − | นั้นคือมีจำนวนเต็ม k ที่
| |
| − | mk = a (i-j)
| |
| − | k = a(i-j) / m
| |
| − | จาก gcd(a,m ) =1 จะได้ว่า m ต้องหาร (i -j) ลงตัว
| |
| − | แต่ (i-j) มีค่าได้ตั้งแต่ 1 ถึง m-1 (0; i=/=j)ซึ่งน้อยกว่า m
| |
| − | ซึ่งเป็นไปไม่ได้ []
| |
| − | | |
| − | แนวทางการ
| |
| − | Proof by Contradiction
| |
| − | จะพิสูจน์ (P) สมมุติ <math>\sim P \rightarrow F</math>
| |
| − | :หรือ<math> \sim(\sim P) \lor \sim F \equiv P </math>
| |
| − | | |
| − | | |
| − | (=>) สมมุติ a มี inverse การคูณ modulo m และ gcd(a,m) = 1
| |
| − | พิสูจน์ gcd(a,m)=/= 1 a จะไม่มี inverse
| |
| − | :ให้ x = gcd(a,m)
| |
| − | :หรือ a = x*k1 , m = x*k2
| |
| − | :พิจารณา ai (mod m)
| |
| − | :x*k1 i mod x*k2
| |
| − | | |
| − | | |
| − | | |
| − | ยูคลิด gcd alg. ในลักษณะ recursive function
| |
| − | | |
| − | funtion GCD(a,b)
| |
| − | :if b|a then return a
| |
| − | :else return gcd(b,a mod b)
| |
| − | | |
| − | ===การวิเคราะห์===
| |
| − | ====การวิเคราะห์ความถูกต้อง====
| |
| − | กรณี b|a ลงตัวจัดเจน
| |
| − | กรณี GCD(b,a mod b)
| |
| − | | |
| − | assume a > b without lose in generality
| |
| − | ;Proof: GCD(a,b) = gcd(a,b)
| |
| − | พิสูจน์ by induction on (a,b)
| |
| − | | |
| − | base case: ถ้า b=0 , GCD(a,b) =a = gcd(a,b)
| |
| − | | |
| − | inductive step:ถ้า b > 0 และ a > b แล้ว
| |
| − | | |
| − | :claim 2: GCD(b,a mod b ) = gcd(a,b)
| |
| − | | |
| − | ถ้า y|a และ y|b แล้ว y|a mod b
| |
| − | | |
| − | a = kb + r เขียน r = a mod b
| |
| − | | |
| − | a-r =kb เนื่องจาก y|b ,y|kb นั้นคือ
| |
| − | | |
| − | <math> y|a-r \rightarrow a \equiv r \pmod{y} </math>
| |
| − | | |
| − | สรุปว่า y|r
| |
| − | | |
| − | assume ที่ GCD(x,y)=gcd(x,y) สำหรับทุกๆ x < a , y <= b ) ; (hypothesis)
| |
| − | นั้นคือ GCD(b,a mod b) = gcd(b, a mod b)
| |
| − | ดังนั้น GCD(a,b) = GCD(b, a mod b)
| |
| − | := gcd(b ,a mod b)
| |
| − | := gcd(a,b) ตาม claim 2
| |
| − | | |
| − | Proof by Induction
| |
| − | :พิสูจน์ว่า P(i) จริงสำหรับจำนวนเต็มบวก i ทุกๆตัว
| |
| − | ## P(1) จริง [base case] [basis]
| |
| − | ## ถ้า P(i) แล้ว P(i+1) จริงสำหรับทุกๆ i >=1 ; P(i) จริงจาก P(j) j < i [inductive step]
| |
| − | ถ้า (a)&(b) จะสรุปได้ว่า P(i) จริงสำหรับทุกจำนวนเต็ม i
| |
| − | | |
| − | ====การวิเคราะห์เวลาการทำงาน====
| |
| − | ;การหา multiplicative inverse mudulo m
| |
| − | lemma: สำหรับจำนวนเต็ม a และ b มีจำนวนเต็ม x,y ที่ ax + by = gcd(a,b) ; x และ y หาได้จาก [[extended gcd alg.]]
| |
| − | >จะหา \inv a (mod m) เมื่อ gcd(a,m) = 1 | |
| − | :จะมี x,y ที่ ax + my = 1
| |
| − | mod m
| |
| − | : (ax + my) mod m = 1
| |
| − | : ax mod m = 1
| |
| − | เลือก mod p เมื่อ p เป็นจำนวนเฉพาะ จะได้ทุกๅ a e {1,2,3,...,p-1} , gcd(a,p) = 1 ; [GFp(Galois Field)]
| |
| | | | |
| | ==การกระจายความลับ (Secret Sharing)== | | ==การกระจายความลับ (Secret Sharing)== |
ขออภัย
Lecture Note ที่ท่านเรียก ยังไม่เปิดให้ใช้บริการค่ะ
Balls & Bins
- มีถัง n ถัง
- มีบอล n ลูก
ถังใบแรกว่าง![{\displaystyle ]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbb7071d99bdb87d7649bb3329360bf2d49bced1)
Random Variable
- นิยาม สำหรับตัวแปรสุ่ม X
![{\displaystyle E[X]=\sum iPr[X=i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e90827545cc8d32292378bf1e78a53089d0d1827)
การกระจายความลับ (Secret Sharing)
ถ้า polynomial f มี degree d เราสามารถให้ 
จะมี polynomial degree d เพียงตัวเดียวที่ผ่าน ทุกจุดดังกล่าว และ polynomial ดังกล่าวหาได้
ต้องการ key M ให้กลุ่มคน n คน ให้ทุกๆกลุ่มคน < k คน ไม่ทราบข้อมูลเกี่ยวกับ key เลย
- กลุ่มคน k คนหา key ได้
หา prime p > key และ p - 1 > n เลือก
จากเซต { 1, 2, ... , p-1}
ให้ ak-1 ไม่เท่ากับ 0
ให้ 
เราจะเลือกจุด 
ที่ไม่ซ้ำกัรและไม่เท่ากับ 0 ให้ 
กับคนที่ i
