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

ตัวอย่าง

$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$

proposition 1

ถ้า $a\equiv b{\pmod {m}}$ iff $m|a-b$

Proof

$p\ \Leftrightarrow \ q\equiv \ (p\ \rightarrow \ q)\ \land \ (q\rightarrow \ 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)

---

ตัวอย่าง ๆ

$a\equiv b{\pmod {m}}$

$x^{2}+{\frac {y}{m^{n}}}$

---

ตัวหารร่วมมาก (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 <= b <= m-1 ที่ b*a mod m = 1 เนื่องจากมีจำนวน m จำนวนไม่ซ้ำกันจากค่าที่เป็นไปได้ระหว่าง 0 ถึง m-1

Proof Claim1

สมมุติให้มีจำนวนเต็ม i =/= j ที่ 0 <= i ,j<= m-1 ที่ i*a mod m = j*a mod m จะได้ i*a \eqv j*a (mod m) หรือ m| i*a - j*a => m|(i-j)*a นั้นคือมีจำนวนเต็ม k ที่ mk = a (i-j) k = a(i-j) / m จาก gcd(a,m ) =1 จะได้ว่า m ต้องหาร (i -j) ลงตัว แต่ (i-j) มีค่าได้ตั้งแต่ 1 ถึง m-1 (0; i=/=j)ซึ่งน้อยกว่า m ซึ่งเป็นไปไม่ได้ []

Proof by Contradiction
(P) สมมุติ ~p => F
:หรือ ~(~P) or ~F \eqv P

(=>) สมมุติ a มี inverse การคูณ modulo m และ gcd(a,m) = 1 พิสูจน์ gcd(a,m)=/= 1 a จะไม่มี inverse

ให้ x = gcd(a,m)

หรือ a = x*k1 , m = x*k2

พิจารณา ai (mod m)

x*k1 i mod x*k2

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

funtion GCD(a,b)

if b|a then return a

else return gcd(b,a mod b)

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

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

กรณี b|a ลงตัวจัดเจน กรณี GCD(b,a mod b)

assume a > b without lose in generality

Proof

GCD(a,b) = gcd(a,b)

พิสูจน์ by induction on (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 mod b

a-r =kb เนื่องจาก y|b ,y|kb นั้นคือ

$y|a-r\rightarrow a\equiv r{\pmod {y}}$

สรุปว่า y|r

assume ที่ GCD(x,y)=gcd(x,y) สำหรับทุกๆ x < a , y <= b ) ; (hypothesis) นั้นคือ 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 ทุกๆตัว
#a P(1) จริง [base case] [basis]
#b ถ้า 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)]