204512/บรรยาย 1
การบรรยายครั้งแรกจะเป็นการแนะนำวิชา และแสดงตัวอย่างการพิสูจน์ที่น่าสนใจ โดยมีเป้าหมายเพื่อที่จะพัฒนาระบบการกระจายความลับ (secret sharing)
คณิตศาสตร์มอดุโล
Definition 1: จะกล่าวว่าจำนวนเต็ม a หารจำนวนเต็ม b ลงตัว ถ้ามีจำนวนเต็ม k ที่ ak = b เขียนแทนด้วย a|b
นิยาม : จำนวนเต็มบวก p ที่ p > 1 และมีตัวประกอบสองจำนวนคือ 1 และตัวมันเองเรียกว่า จำนวนเฉพาะ
นิยาม : a mod b = r เมื่อ 0 <= r < b ถ้ามีจำนวนเต็ม k ที่ bk+r = a
ตัวอย่าง
- 10mod3 =1
- -10 mod 3 =2 ; 3(-4)+2 = -10
นิยาม : a \eqv b (mod m) ถ้า a mod m = b mod m
proposition 1: ถ้า a \eqv b (mod m)
iff m|a-b
Proof: p<=>q \eqv (p=>q)and(q=>p)
(~p=>~q)
(=>)
(<=)
เนื่องจาก m|a-b เราจะได้ว่ามีจำนวนเต็ม k ที่
mk = a-b
b = a -mk
b mod m = a mod m - mk mod m
b mod m = a mod m
Propostition : ถ้า a \eqv b (mod m ) และ c \eqv d(mod m) แล้ว
1. a+c \eqv b+d (mod m)
2. ac \eqv bd (mod m)
3. a-c \eqv b-d (mod m)
proof :
- a \eqv b (mod m)=> m|a-b
- c \eqv d (mod m)=> m|c-d
- m|(a+c)-(b+d) => a+c \eqv b+d (mod m)
ac \eqv ad (mod m) => c \eqv d (mod m)
นิยาม: สำหรับถ้า ab \eqv 1 (mod m) จะเรียก b ว่าเป็น mutiplicative inverse modulo m ของ a^-1
เช่น
- 3*3 \eqv 1 (mod 4)
- 3 = 3^-1 (mod 4)
(mod4)
- 2/3 = 7
- x*3 \eqv 2 (mod 4)
- x*3*\inv 3 \eqv 2*\inv 3 (mod 4)
- x \eqv 2*3 = 6 =2 (mod 4)
(mod 7)
- 2/3 = 7
- \inv 3 (mod 7) \eqv 5 (mod 7)
- x \eqv 2*5 \eqv 10 \eqv 3 (mod 7)
ถ้ามี inverse สามารถหาผลหารได้โดยเอา inverse ไปคูณ
4/3 = 4* \inv 3 (mod m)
ตัวอย่าง ๆ
