ผลต่างระหว่างรุ่นของ "204512/บรรยาย 1"
Jittat (คุย | มีส่วนร่วม) |
|||
(ไม่แสดง 20 รุ่นระหว่างกลางโดยผู้ใช้ 6 คน) | |||
แถว 1: | แถว 1: | ||
{{หัวคำบรรยาย|204512}} | {{หัวคำบรรยาย|204512}} | ||
+ | '''จดบันทึกคำบรรยายโดย:''' ''(กรุณาใส่ด้วย)'' | ||
การบรรยายครั้งแรกจะเป็นการแนะนำวิชา [[204512]] และแสดงตัวอย่างการพิสูจน์ที่น่าสนใจ โดยมีเป้าหมายเพื่อที่จะพัฒนาระบบการกระจายความลับ (secret sharing) | การบรรยายครั้งแรกจะเป็นการแนะนำวิชา [[204512]] และแสดงตัวอย่างการพิสูจน์ที่น่าสนใจ โดยมีเป้าหมายเพื่อที่จะพัฒนาระบบการกระจายความลับ (secret sharing) | ||
แถว 25: | แถว 26: | ||
<math>(\Rightarrow)</math> | <math>(\Rightarrow)</math> | ||
+ | |||
<math>a \equiv b \pmod{m}</math> นั้นคือ | <math>a \equiv b \pmod{m}</math> นั้นคือ | ||
แถว 96: | แถว 98: | ||
'''Proof:''' | '''Proof:''' | ||
− | (<=) สมมุติ gcd(a,m) = 1 | + | (<=)<br> |
+ | สมมุติ gcd(a,m) = 1 | ||
:พิจารณา | :พิจารณา | ||
:: 0 mod m | :: 0 mod m | ||
แถว 107: | แถว 110: | ||
{{กล่องทฤษฎีบท|'''Claim 1:''' จำนวนเหล่านี้ไม่เท่ากันเลย}} | {{กล่องทฤษฎีบท|'''Claim 1:''' จำนวนเหล่านี้ไม่เท่ากันเลย}} | ||
− | จาก Claim 1 | + | จาก Claim 1 เราจะได้ว่ามีจำนวนเต็ม ''b'' ที่อยู่ระหว่าง <math>\ 0 \leq\ b\ \leq\ m-1 </math> ที่ <math>b\ a\ \bmod\ m = 1 </math> เนื่องจากมีจำนวน ''m'' จำนวนไม่ซ้ำกันจากค่าที่เป็นไปได้ระหว่าง 0 ถึง ''m''-1 |
− | + | สรุปคือ inverse การคูณ modulo m ของ a คือ b นั้นเอง | |
+ | {{จบบทพิสูจน์}} | ||
+ | ต่อไปเราจะพิสูจน์ Claim 1. | ||
{{เริ่มบทพิสูจน์}} | {{เริ่มบทพิสูจน์}} | ||
'''Proof of Claim1:''' สมมุติให้มีจำนวนเต็ม <math>\ i\ \neq\ j</math> ที่ <math>\ 0\ \leq\ i\ ,j\ \leq\ m-1</math> | '''Proof of Claim1:''' สมมุติให้มีจำนวนเต็ม <math>\ i\ \neq\ j</math> ที่ <math>\ 0\ \leq\ i\ ,j\ \leq\ m-1</math> | ||
− | ที่ <math> | + | :ที่ <math>ia\ \bmod\ m\ =\ ja\ \bmod\ m</math> |
− | จะได้ <math> | + | :จะได้ <math>ia \equiv\ ja \pmod{m}</math> |
− | หรือ m | + | :หรือ <math>m\mid ia\ -\ ja \Rightarrow\ m\mid (\ i\ -\ j\ )\ a</math> |
นั้นคือมีจำนวนเต็ม k ที่ | นั้นคือมีจำนวนเต็ม k ที่ | ||
− | mk = a (i-j) | + | :<math>mk\ =\ a(i-j)</math> |
− | k = a(i-j) / | + | :<math>k\ =\ \frac{a(i-j)}{ m}</math> |
จาก gcd(a,m ) =1 จะได้ว่า m ต้องหาร (i -j) ลงตัว | จาก gcd(a,m ) =1 จะได้ว่า m ต้องหาร (i -j) ลงตัว | ||
− | แต่ (i-j) มีค่าได้ตั้งแต่ 1 ถึง m-1 (0 | + | แต่ (i-j) มีค่าได้ตั้งแต่ 1 ถึง m-1 (ไม่เป็น 0 เนื่องจาก <math> i\ \neq\ j\ )</math>ซึ่งน้อยกว่า m |
ซึ่งเป็นไปไม่ได้ | ซึ่งเป็นไปไม่ได้ | ||
{{จบบทพิสูจน์}} | {{จบบทพิสูจน์}} | ||
แถว 127: | แถว 132: | ||
จะพิสูจน์ (P) สมมุติ <math>\sim P \rightarrow F</math> | จะพิสูจน์ (P) สมมุติ <math>\sim P \rightarrow F</math> | ||
:หรือ<math> \sim(\sim P) \lor \sim F \equiv P </math> | :หรือ<math> \sim(\sim P) \lor \sim F \equiv P </math> | ||
+ | (=>)<br> | ||
+ | ต้องการพิสูจน์ a มี inverse modulo m แล้ว gcd(a,m) = 1 | ||
+ | {{เริ่มบทพิสูจน์}} | ||
+ | ;Proof(Indirect)<nowiki>:</nowiki> | ||
+ | <math> gcd(\ a,\ m) \neq 1 \Rightarrow\ a</math> ไม่มี mutiplicative inverse modulo m | ||
− | + | :ให้ <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\ =\ 1</math> |
− | : | + | :<math>xk_1i\ - xk_2j\ = 1</math> |
− | :x | + | :<math>x(k_1i\ - k_2j)\ = 1</math> |
+ | :ซึ่งจะเห็นว่า ผลลบของเทอมที่คูณ x เป็นจำนวนเต็ม คูณอยู่กับ x ซึ่งมากกว่าหนึ่งจึงเป็นไปไม่ได้ที่ <math>x(k_1i\ - k_2j)</math> เท่ากับ 1 | ||
{{จบบทพิสูจน์}} | {{จบบทพิสูจน์}} | ||
− | ยูคลิด gcd alg. ในลักษณะ recursive function | + | ==ยูคลิด gcd alg. ในลักษณะ recursive function== |
− | |||
funtion GCD(a,b) | funtion GCD(a,b) | ||
:if b|a then return a | :if b|a then return a | ||
− | :else return | + | :else return GCD(b,a mod b) |
===การวิเคราะห์=== | ===การวิเคราะห์=== | ||
====การวิเคราะห์ความถูกต้อง==== | ====การวิเคราะห์ความถูกต้อง==== | ||
− | + | ;นิยาม:gcd(a,b) คือค่าหารรวมมากของ a กับ b | |
− | |||
− | |||
assume a > b without lose in generality | assume a > b without lose in generality | ||
− | ;Proof | + | {{เริ่มบทพิสูจน์}} |
− | + | ;Proof by induction on (a,b)<nowiki>:</nowiki> :GCD(a,b) = gcd(a,b) | |
− | + | ||
− | base case: ถ้า b=0 , GCD(a,b) =a = gcd(a,b) | + | ;base case<nowiki>:</nowiki>: ถ้า b=0 , GCD(a,b) =a = gcd(a,b) |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | a | + | ;inductive step<nowiki>:</nowiki>:ถ้า b > 0 และ a > b แล้ว |
− | <math> y | + | :'''claim 2''': gcd(b,a mod b ) = gcd(a,b) |
+ | :ถ้า y|a และ y|b แล้ว y|a mod b | ||
+ | :<math>a = kb + r </math> หรือ <math> r\ =\ a\ \bmod\ b</math> | ||
+ | :<math>a-r = kb </math> | ||
+ | เนื่องจาก <math> y\mid\ b </math> จะได้ว่า <math> y\mid\ kb </math> และ <math>y \mid r</math> ด้วย | ||
+ | :ดังนั้น <math> y\mid\ a-r </math> | ||
+ | :<math>\Rightarrow\; a \equiv r \pmod{y} </math> | ||
− | |||
− | + | ;hypothesis สมมุติที่ GCD(x,y)=gcd(x,y) สำหรับทุกๆ x < a , y <= b | |
− | นั้นคือ GCD(b,a mod b) = gcd(b, a mod b) | + | :นั้นคือ GCD(b,a mod b) = gcd(b, a mod b) |
− | ดังนั้น GCD(a,b) = GCD(b, a mod b) | + | :ดังนั้น GCD(a,b) = GCD(b, a mod b) |
− | := gcd(b ,a mod b) | + | ::= gcd(b ,a mod b) |
− | := gcd(a,b) ตาม claim 2 | + | ::= gcd(a,b) ตาม claim 2 |
Proof by Induction | Proof by Induction |
รุ่นแก้ไขปัจจุบันเมื่อ 01:01, 21 มีนาคม 2555
บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง
จดบันทึกคำบรรยายโดย: (กรุณาใส่ด้วย)
การบรรยายครั้งแรกจะเป็นการแนะนำวิชา 204512 และแสดงตัวอย่างการพิสูจน์ที่น่าสนใจ โดยมีเป้าหมายเพื่อที่จะพัฒนาระบบการกระจายความลับ (secret sharing)
เนื้อหา
คณิตศาสตร์มอดุโล
เราจะเริ่มจากนิยามพื้นฐานก่อน เราจะกล่าวว่าจำนวนเต็ม a หารจำนวนเต็ม b ลงตัว ถ้ามีจำนวนเต็ม k ที่ ak = b เขียนแทนด้วย a|b
- นิยาม
- จำนวนเต็มบวก p ที่ p > 1 และมีตัวประกอบสองจำนวนคือ 1 และตัวมันเองเรียกว่า จำนวนเฉพาะ
- นิยาม
- ถ้าและมีจำนวนเต็ม k ที่
ตัวอย่าง
- นิยาม
- ถ้า
เราจะเริ่มพิสูจน์ความจริงพื้นฐานเกี่ยวกับการหารลงตัวก่อน หลายครั้งเราจะพิสูจน์ความจริงในรูป โดยการพิสูจน์ และ . นอกจากนี้ ในการพิสูจน์ประโยค เรามักใช้การพิสูจน์แบบทางอ้อม (indirect proof) โดยพิสูจน์ แทน
Proposition 1: เมื่อและต่อเมื่อ
Proof:
นั้นคือ
โดยที่ j,k,f เป็นจำนวนเต็ม หาผลต่างของสมการทั้งสองจะได้
นั้นคือ
- เนื่องจาก m | a-b เราจะได้ว่ามีจำนวนเต็ม k ที่
- Propostition
- ถ้า และ แล้ว
proof:
สังเกตว่าประโยค
นั้นไม่เป็นจริงเสมอไป
นิยาม: สำหรับถ้า จะเรียก b ว่าเป็น mutiplicative inverse modulo m ของ เขียนแทนด้วย
เช่น
ถ้ามี inverse สามารถหาผลหารได้โดยเอา inverse ไปคูณ
ตัวหารร่วมมาก (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 ที่อยู่ระหว่าง ที่ เนื่องจากมีจำนวน m จำนวนไม่ซ้ำกันจากค่าที่เป็นไปได้ระหว่าง 0 ถึง m-1
สรุปคือ inverse การคูณ modulo m ของ a คือ b นั้นเอง
ต่อไปเราจะพิสูจน์ Claim 1.
Proof of Claim1: สมมุติให้มีจำนวนเต็ม ที่
- ที่
- จะได้
- หรือ
นั้นคือมีจำนวนเต็ม k ที่
จาก gcd(a,m ) =1 จะได้ว่า m ต้องหาร (i -j) ลงตัว แต่ (i-j) มีค่าได้ตั้งแต่ 1 ถึง m-1 (ไม่เป็น 0 เนื่องจาก ซึ่งน้อยกว่า m ซึ่งเป็นไปไม่ได้
แนวทางการ Proof by Contradiction จะพิสูจน์ (P) สมมุติ :หรือ
(=>)
ต้องการพิสูจน์ a มี inverse modulo m แล้ว gcd(a,m) = 1
- Proof(Indirect):
ไม่มี mutiplicative inverse modulo m
- ให้
- หรือ
- พิจารณา
- ซึ่งจะเห็นว่า ผลลบของเทอมที่คูณ x เป็นจำนวนเต็ม คูณอยู่กับ x ซึ่งมากกว่าหนึ่งจึงเป็นไปไม่ได้ที่ เท่ากับ 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
- หรือ
เนื่องจาก จะได้ว่า และ ด้วย
- ดังนั้น
- 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 เราสามารถให้ จะมี 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