ผลต่างระหว่างรุ่นของ "204512/บรรยาย 1"

รุ่นแก้ไขปัจจุบันเมื่อ 01:01, 21 มีนาคม 2555

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

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

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

เนื้อหา

1 คณิตศาสตร์มอดุโล
2 ตัวหารร่วมมาก (grestest common divisors)
3 ยูคลิด gcd alg. ในลักษณะ recursive function
- 3.1 การวิเคราะห์
  - 3.1.1 การวิเคราะห์ความถูกต้อง
  - 3.1.2 การวิเคราะห์เวลาการทำงาน
4 การกระจายความลับ (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}}$ แล้ว

$a+c\equiv b+d{\pmod {m}}$
$a\,c\equiv b\,d{\pmod {m}}$
$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

@@ แถว 1: / แถว 1: @@
 {{หัวคำบรรยาย|204512}}
+'''จดบันทึกคำบรรยายโดย:''' ''(กรุณาใส่ด้วย)''
 การบรรยายครั้งแรกจะเป็นการแนะนำวิชา [[204512]] และแสดงตัวอย่างการพิสูจน์ที่น่าสนใจ โดยมีเป้าหมายเพื่อที่จะพัฒนาระบบการกระจายความลับ (secret sharing)
@@ แถว 131: / แถว 132: @@
   จะพิสูจน์ (P) สมมุติ <math>\sim P \rightarrow F</math>
   :หรือ<math> \sim(\sim P) \lor \sim F \equiv P </math>
-(<=)<br>
+(=>)<br>
-ถ้า gcd(a,m) ไม่เท่ากับหนึ่ง เราสามารถพิสูจน์ได้ว่า a ไม่มี inverse การคูณ modulo m
+ต้องการพิสูจน์ a มี inverse modulo m แล้ว gcd(a,m) = 1
 {{เริ่มบทพิสูจน์}}
-;Proof by contradiction <nowiki>:</nowiki>
+;Proof(Indirect)<nowiki>:</nowiki>
 <math> gcd(\ a,\ m) \neq 1 \Rightarrow\ a</math> ไม่มี mutiplicative inverse modulo m
-สมมุติ a มี inverse การคูณ modulo m และ gcd(a,m) = 1
 :ให้ <math>x\  =\ gcd(\ a,\ m)</math>
 :หรือ <math>a\  =\  xk_1 , m = xk_2</math>
 :พิจารณา <math>ai\ \bmod\ m</math>
-:<math>xk_1i\ \bmod\  xk_2</math>
+:<math>xk_1i\ \bmod\  xk_2\ =\ 1</math>
+:<math>xk_1i\ - xk_2j\ = 1</math>
+:<math>x(k_1i\ - k_2j)\ = 1</math>
+:ซึ่งจะเห็นว่า ผลลบของเทอมที่คูณ x เป็นจำนวนเต็ม คูณอยู่กับ x ซึ่งมากกว่าหนึ่งจึงเป็นไปไม่ได้ที่ <math>x(k_1i\ - k_2j)</math> เท่ากับ 1
 {{จบบทพิสูจน์}}

ผลต่างระหว่างรุ่นของ "204512/บรรยาย 1"

รุ่นแก้ไขปัจจุบันเมื่อ 01:01, 21 มีนาคม 2555

เนื้อหา

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

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

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

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

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

การวิเคราะห์เวลาการทำงาน

การกระจายความลับ (Secret Sharing)

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ