204512/บรรยาย 4

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

Balls & Bins

มีถัง $n$ ถัง

มีบอล $n$ ลูก

${\rm {Pr[first\ bin\ is\ empty]=}}\left({{\rm {1-}}{\frac {\rm {1}}{\rm {n}}}}\right)^{\rm {n}}$

Random Variable

นิยาม

สำหรับตัวแปรสุ่ม $X$

$\sum \limits _{i=-\infty }^{\infty }{i\cdot \Pr[X=i]}$

ตัวอย่าง

มีลูกเต๋า 2 ลูก โยนทีละลูก

ให้ตัวแปรสุ่ม

$Y_{1}=$แต้มบนลูกเต๋าลูกที่ 1

$Y_{2}=$แต้มบนลูกเต๋าลูกที่ 2

$Y=$แต้มรวม

$E[Y_{1}]=(1+2+...+6)\cdot {\frac {1}{6}}$

$E[Y_{1}]=3.5$

$E[Y_{2}]=3.5$

$E[Y]=2\cdot {\frac {1}{6}}\cdot {\frac {1}{6}}+3\cdot 2\cdot {\frac {1}{36}}+4\cdot 3\cdot {\frac {1}{36}}+5\cdot .....$

$E[Y]=7$

$E[Y]=E[Y_{1}+Y_{2}]=E[Y_{1}]+E[Y_{2}]$

การกระจายความลับ (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