204512/บรรยาย 1

บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย: (กรุณาใส่ด้วย)

การบรรยายครั้งแรกจะเป็นการแนะนำวิชา 204512 และแสดงตัวอย่างการพิสูจน์ที่น่าสนใจ โดยมีเป้าหมายเพื่อที่จะพัฒนาระบบการกระจายความลับ (secret sharing)

คณิตศาสตร์มอดุโล

เราจะเริ่มจากนิยามพื้นฐานก่อน เราจะกล่าวว่าจำนวนเต็ม a หารจำนวนเต็ม b ลงตัว ถ้ามีจำนวนเต็ม k ที่ ak = b เขียนแทนด้วย a|b

นิยาม 

จำนวนเต็มบวก p ที่ p > 1 และมีตัวประกอบสองจำนวนคือ 1 และตัวมันเองเรียกว่า จำนวนเฉพาะ

นิยาม 

$a\ {\bmod {b}}=r$ถ้า$0\leq r<b$และมีจำนวนเต็ม k ที่ $b\ k+r=a$

ตัวอย่าง

$10\ {\bmod {\ }}3\ =\ 1$

$-10\ {\bmod {\ }}3\ =\ 2\quad ;\quad 3(-4)\ +\ 2\ =\ -10$

นิยาม 

$a\equiv b{\pmod {m}}$ ถ้า $a\ {\bmod {\ }}m\ =\ b\ {\bmod {\ }}m$

เราจะเริ่มพิสูจน์ความจริงพื้นฐานเกี่ยวกับการหารลงตัวก่อน หลายครั้งเราจะพิสูจน์ความจริงในรูป $p\ \leftrightarrow \ q$ โดยการพิสูจน์ $p\ \rightarrow \ q$ และ $q\rightarrow \ p$. นอกจากนี้ ในการพิสูจน์ประโยค $p\rightarrow q$ เรามักใช้การพิสูจน์แบบทางอ้อม (indirect proof) โดยพิสูจน์ $\neg q\rightarrow \neg p$ แทน

Proposition 1: $a\equiv b{\pmod {m}}$ เมื่อและต่อเมื่อ $m|a-b$

---

Proof:

$(\Rightarrow )$

$a\equiv b{\pmod {m}}$ นั้นคือ

$j\ m+f=a$

$k\ m+f=b$

โดยที่ j,k,f เป็นจำนวนเต็ม หาผลต่างของสมการทั้งสองจะได้

$(\ j\ -\ k\ )\ m=a\ -\ b$

นั้นคือ $m\mid a-b$

$(\Leftarrow )$

เนื่องจาก m | a-b เราจะได้ว่ามีจำนวนเต็ม k ที่

$m\,k=a-b$

$b\ =a-m\,k$

$b\ {\bmod {\ }}m\ =\ a\ {\bmod {\ }}m\ -\ m\,k\ {\bmod {\ }}m$

$b\ {\bmod {\ }}m\ =\ a\ {\bmod {\ }}m$

---

Propostition 

ถ้า $a\ \equiv \ b{\pmod {m}}$ และ $c\ \equiv \ d{\pmod {m}}$ แล้ว

1. $a+c\equiv b+d{\pmod {m}}$
2. $a\,c\equiv b\,d{\pmod {m}}$
3. $a-c\equiv b-d{\pmod {m}}$

---

proof:

$a\equiv b{\pmod {m}}\rightarrow m|a-b$

$c\equiv d{\pmod {m}}\rightarrow m|c-d$

$m|(a+c)-(b+d)\rightarrow a+c\equiv b+d{\pmod {m}}$

---

สังเกตว่าประโยค

$a\,c\equiv a\,d{\pmod {m}}\rightarrow c\equiv d{\pmod {m}}$

นั้นไม่เป็นจริงเสมอไป

นิยาม: สำหรับถ้า $a\,b\equiv 1{\pmod {m}}$ จะเรียก b ว่าเป็น mutiplicative inverse modulo m ของ $a$ เขียนแทนด้วย $a^{-1}$

เช่น

$3*3\equiv 1{\pmod {4}}$

$3=3^{-1}{\pmod {4}}$

${\pmod {4}}$

$2/3\equiv x$

$x\cdot 3\equiv 2{\pmod {4}}$

$x\cdot 3\cdot 3^{-1}\equiv 2\cdot 3^{-1}{\pmod {4}}$

$x\equiv 2\cdot 3\equiv 6\equiv 2{\pmod {4}}$

${\pmod {7}}$

$2/3\equiv x$

$3^{-1}\equiv 5{\pmod {7}}$

$x\equiv 2\cdot 5\equiv 10\equiv 3{\pmod {7}}$

ถ้ามี inverse สามารถหาผลหารได้โดยเอา inverse ไปคูณ

$4/3=4\cdot 3^{-1}{\pmod {m}}$

ตัวหารร่วมมาก (grestest common divisors)

ตัวหารร่วมมาก (gcd) ของ a และ b คือจำนวนเต็มที่มากที่สุดที่หาร a และ b ลงตัวแทนด้วย gcd(a,b)

Thm: ให้จำนวนเต็ม a ,m a จะมี inverse การคูณ modulo m เมื่อและต่อเมื่อ gcd(a,m) เท่ากับ 1

---

Proof:

(<=)
สมมุติ gcd(a,m) = 1

พิจารณา

0 mod m

a mod m

2a mod m

3a mod m

. . .

(m-1)a mod m

Claim 1: จำนวนเหล่านี้ไม่เท่ากันเลย

จาก Claim 1 เราจะได้ว่ามีจำนวนเต็ม b ที่อยู่ระหว่าง $\ 0\leq \ b\ \leq \ m-1$ ที่ $b\ a\ {\bmod {\ }}m=1$ เนื่องจากมีจำนวน m จำนวนไม่ซ้ำกันจากค่าที่เป็นไปได้ระหว่าง 0 ถึง m-1

สรุปคือ inverse การคูณ modulo m ของ a คือ b นั้นเอง

---

ต่อไปเราจะพิสูจน์ Claim 1.

---

Proof of Claim1: สมมุติให้มีจำนวนเต็ม $\ i\ \neq \ j$ ที่ $\ 0\ \leq \ i\ ,j\ \leq \ m-1$

ที่ $ia\ {\bmod {\ }}m\ =\ ja\ {\bmod {\ }}m$

จะได้ $ia\equiv \ ja{\pmod {m}}$

หรือ $m\mid ia\ -\ ja\Rightarrow \ m\mid (\ i\ -\ j\ )\ a$

นั้นคือมีจำนวนเต็ม k ที่

$mk\ =\ a(i-j)$

$k\ =\ {\frac {a(i-j)}{m}}$

จาก gcd(a,m ) =1 จะได้ว่า m ต้องหาร (i -j) ลงตัว แต่ (i-j) มีค่าได้ตั้งแต่ 1 ถึง m-1 (ไม่เป็น 0 เนื่องจาก $i\ \neq \ j\ )$ซึ่งน้อยกว่า m ซึ่งเป็นไปไม่ได้

---

แนวทางการ 
Proof by Contradiction
จะพิสูจน์ (P) สมมุติ $\sim P\rightarrow F$
:หรือ$\sim (\sim P)\lor \sim F\equiv P$

(=>)
ต้องการพิสูจน์ a มี inverse modulo m แล้ว gcd(a,m) = 1

---

Proof(Indirect):

$gcd(\ a,\ m)\neq 1\Rightarrow \ a$ ไม่มี mutiplicative inverse modulo m

ให้ $x\ =\ gcd(\ a,\ m)$

หรือ $a\ =\ xk_{1},m=xk_{2}$

พิจารณา $ai\ {\bmod {\ }}m$

$xk_{1}i\ {\bmod {\ }}xk_{2}\ =\ 1$

$xk_{1}i\ -xk_{2}j\ =1$

$x(k_{1}i\ -k_{2}j)\ =1$

ซึ่งจะเห็นว่า ผลลบของเทอมที่คูณ x เป็นจำนวนเต็ม คูณอยู่กับ x ซึ่งมากกว่าหนึ่งจึงเป็นไปไม่ได้ที่ $x(k_{1}i\ -k_{2}j)$ เท่ากับ 1

---

ยูคลิด gcd alg. ในลักษณะ recursive function

funtion GCD(a,b)

if b|a then return a

else return GCD(b,a mod b)

การวิเคราะห์

การวิเคราะห์ความถูกต้อง

นิยาม

gcd(a,b) คือค่าหารรวมมากของ a กับ b

assume a > b without lose in generality

---

Proof by induction on (a,b):

GCD(a,b) = gcd(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\ {\bmod {\ }}b$

$a-r=kb$

เนื่องจาก $y\mid \ b$ จะได้ว่า $y\mid \ kb$ และ $y\mid r$ ด้วย

ดังนั้น $y\mid \ a-r$

$\Rightarrow \;a\equiv r{\pmod {y}}$

hypothesis สมมุติที่ GCD(x,y)=gcd(x,y) สำหรับทุกๆ x < a , y <= b

นั้นคือ 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