204512/บรรยาย 4

ขออภัย Lecture Note ที่ท่านเรียก ยังไม่เปิดให้ใช้บริการค่ะ

Balls & Bins

• มีถัง n ถัง
• มีบอล n ลูก

:หรือ$\sim (\sim P)\lor \sim F\equiv P$

(=>) สมมุติ 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 นั้นคือ

$y|a-r\rightarrow a\equiv r{\pmod {y}}$

สรุปว่า 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)

ถ้า polynomial f มี degree d เราสามารถให้ $(x_{0},y_{0}),\ (x_{1},y_{1}),\ ...\ ,\ (x_{d},y_{d})$ จะมี polynomial degree d เพียงตัวเดียวที่ผ่าน ทุกจุดดังกล่าว และ polynomial ดังกล่าวหาได้

ต้องการ key M ให้กลุ่มคน n คน ให้ทุกๆกลุ่มคน < k คน ไม่ทราบข้อมูลเกี่ยวกับ key เลย

กลุ่มคน k คนหา key ได้

หา prime p > key และ p - 1 > n เลือก$a_{k-1},a_{k-2},...,a_{1}$ จากเซต { 1, 2, ... , p-1}

ให้ ak-1 ไม่เท่ากับ 0

ให้ $f(x)=a_{k-1}\,x^{k-1}+a_{k-2}\,x^{k-2}+...+a_{2}\,x^{2}+a_{1}\,x+M$ เราจะเลือกจุด $\ x_{1},\ x_{2},\ ...,\ x_{n}$ ที่ไม่ซ้ำกัรและไม่เท่ากับ 0 ให้ $(\ x_{i},\ f(x_{i}))$ กับคนที่ i