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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 98 รุ่นระหว่างกลางโดยผู้ใช้ 15 คน)
แถว 1: แถว 1:
การบรรยายครั้งแรกจะเป็นการแนะนำวิชา และแสดงตัวอย่างการพิสูจน์ที่น่าสนใจ โดยมีเป้าหมายเพื่อที่จะพัฒนาระบบการกระจายความลับ (secret sharing)
+
{{หัวคำบรรยาย|204512}}
 +
'''จดบันทึกคำบรรยายโดย:''' ''(กรุณาใส่ด้วย)''
 +
 
 +
การบรรยายครั้งแรกจะเป็นการแนะนำวิชา [[204512]] และแสดงตัวอย่างการพิสูจน์ที่น่าสนใจ โดยมีเป้าหมายเพื่อที่จะพัฒนาระบบการกระจายความลับ (secret sharing)
  
 
==คณิตศาสตร์มอดุโล==
 
==คณิตศาสตร์มอดุโล==
Definition 1:
+
เราจะเริ่มจากนิยามพื้นฐานก่อน เราจะกล่าวว่าจำนวนเต็ม a ''หารจำนวนเต็ม b ลงตัว'' ถ้ามีจำนวนเต็ม k ที่ ak = b เขียนแทนด้วย a|b
จะกล่าวว่าจำนวนเต็ม a หารจำนวนเต็ม b ลงตัว ถ้ามีจำนวนเต็ม k ที่ ak = b เขียนแทนด้วย a|b  
+
 
 +
;นิยาม : จำนวนเต็มบวก p ที่ p > 1 และมีตัวประกอบสองจำนวนคือ 1 และตัวมันเองเรียกว่า ''จำนวนเฉพาะ''
 +
 
 +
;นิยาม : <math>a\ \bmod b = r </math>ถ้า<math> 0 \le r < b </math>และมีจำนวนเต็ม ''k'' ที่ <math>b\ k+r = a</math>
 +
 
 +
'''ตัวอย่าง'''
 +
:<math> 10\ \bmod\ 3\ =\ 1</math>
 +
 
 +
:<math>-10\ \bmod\ 3\ =\ 2\quad;\quad 3(-4)\ +\ 2\ =\ -10</math>
 +
;นิยาม :
 +
:<math>a \equiv b \pmod{m}</math> ถ้า  <math>a\ \bmod\ m\ =\ b\ \bmod\ m</math>
 +
 
 +
เราจะเริ่มพิสูจน์ความจริงพื้นฐานเกี่ยวกับการหารลงตัวก่อน  หลายครั้งเราจะพิสูจน์ความจริงในรูป <math>p\ \leftrightarrow\ q</math> โดยการพิสูจน์ <math>p\ \rightarrow\ q</math> และ <math>q \rightarrow\ p</math>.  นอกจากนี้ ในการพิสูจน์ประโยค <math>p\rightarrow q</math> เรามักใช้การพิสูจน์แบบทางอ้อม (indirect proof) โดยพิสูจน์ <math>\neg q\rightarrow\neg p</math> แทน
 +
 
 +
{{กล่องทฤษฎีบท|
 +
'''Proposition 1''': <math>a \equiv b \pmod{m}</math> เมื่อและต่อเมื่อ <math>m | a-b</math>}}
 +
{{เริ่มบทพิสูจน์}}
 +
'''Proof:'''
 +
 
 +
<math>(\Rightarrow)</math>
 +
 
 +
<math>a \equiv b \pmod{m}</math> นั้นคือ
 +
 
 +
<math>j\ m + f = a </math>
 +
 
 +
<math>k\ m + f = b </math>
 +
 
 +
โดยที่ ''j,k,f'' เป็นจำนวนเต็ม หาผลต่างของสมการทั้งสองจะได้
 +
 
 +
<math>(\ j\ -\ k\ )\ m = a\ -\ b </math>
 +
 
 +
นั้นคือ
 +
<math>m \mid a - b </math>
 +
 
 +
<math>(\Leftarrow)</math>
 +
 
 +
:เนื่องจาก  m | a-b เราจะได้ว่ามีจำนวนเต็ม k ที่
 +
<math>m\,k  = a - b</math>
  
นิยาม : จำนวนเต็มบวก p ที่ p > 1 และมีตัวประกอบสองจำนวนคือ 1 และตัวมันเองเรียกว่า จำนวนเฉพาะ
+
<math>b\ = a - m\,k</math>
นิยาม : 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)
+
<math>b\ \bmod\ m\  =\ a\ \bmod\ m\ -\ m\,k\ \bmod\ m</math>  
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 \
 
  > m|(a+c)-(b+d)  => a+c \eqv b+d (mod m)
 
          c \eqv d (mod m)=> m|c-d /
 
  
ac \eqv ad (mod m) => c \eqv d (mod m)
+
<math>b\ \bmod\ m\ =\ a\ \bmod\ m</math>
นิยาม: สำหรับถ้า 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
+
;Propostition : ถ้า <math>a\ \equiv\ b \pmod{m}</math> และ <math>c\ \equiv\ d \pmod{m} </math> แล้ว
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)
+
# <math>a+c \equiv b+d \pmod{m}</math>
2/3 = 7
+
# <math>a\,c \equiv b\,d \pmod{m}</math>
\inv 3 (mod 7) \eqv 5 (mod 7)
+
# <math>a-c \equiv b-d \pmod{m}</math>
x \eqv 2*5 \eqv 10 \eqv 3 (mod 7)
+
}}
 +
{{เริ่มบทพิสูจน์}}
 +
'''proof:'''
 +
:<math>a \equiv b \pmod{m} \rightarrow m|a-b </math>
 +
:<math>c \equiv d \pmod{m} \rightarrow m|c-d </math>
 +
:<math>m|(a+c)-(b+d)   \rightarrow a+c \equiv b+d \pmod{m}</math>
 +
{{จบบทพิสูจน์}}
  
ถ้ามี inverse สามารถหาผลหารได้โดยเอา inverse ไปคูณ
+
สังเกตว่าประโยค
4/3  = 4* \inv 3 (mod m)
+
<center><math>a\,c \equiv a\,d \pmod{m} \rightarrow c \equiv d \pmod{m}</math></center>
 +
นั้นไม่เป็นจริงเสมอไป
  
 +
นิยาม: สำหรับถ้า <math>a\,b \equiv 1 \pmod{m}</math> จะเรียก  b ว่าเป็น mutiplicative inverse modulo m  ของ <math>a</math> เขียนแทนด้วย  <math>a^{-1}</math>
  
 +
เช่น
 +
:<math>3*3 \equiv 1 \pmod{4} </math>
 +
:<math>3 = 3^{-1} \pmod{4} </math>
  
:<math>a \equiv b \pmod{m}</math>
+
<math>\pmod 4</math>
ตัวอย่าง ๆ
+
:<math>2 / 3 \equiv x</math>
<math>x^2 + \frac{y}{m^n}</math>
+
:<math>x \cdot 3 \equiv 2 \pmod 4</math>
 +
:<math>x \cdot 3 \cdot 3^{-1} \equiv 2 \cdot 3^{-1} \pmod 4</math>
 +
:<math>x \equiv 2 \cdot 3 \equiv 6 \equiv 2 \pmod 4</math>
 +
 
 +
<math>\pmod 7</math>
 +
:<math>2 / 3 \equiv x</math>
 +
:<math>3^{-1} \equiv 5 \pmod 7</math>
 +
:<math>x \equiv 2 \cdot 5 \equiv 10 \equiv 3 \pmod 7</math>
 +
 
 +
ถ้ามี inverse สามารถหาผลหารได้โดยเอา inverse ไปคูณ
 +
 
 +
<math>4/3  = 4 \cdot 3^{-1} \pmod m</math>
  
 
==ตัวหารร่วมมาก (grestest common divisors)==
 
==ตัวหารร่วมมาก (grestest common divisors)==
 +
ตัวหารร่วมมาก (gcd) ของ  a และ b คือจำนวนเต็มที่มากที่สุดที่หาร a และ b ลงตัวแทนด้วย gcd(a,b)
 +
{{กล่องทฤษฎีบท|
 +
'''Thm''':  ให้จำนวนเต็ม a ,m    a จะมี inverse การคูณ modulo m เมื่อและต่อเมื่อ gcd(a,m) เท่ากับ 1 }}
 +
{{เริ่มบทพิสูจน์}}
 +
'''Proof:'''
 +
 +
(<=)<br>
 +
สมมุติ 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'' ที่อยู่ระหว่าง <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>
 +
:ที่  <math>ia\ \bmod\ m\ =\  ja\ \bmod\ m</math>
 +
:จะได้ <math>ia \equiv\  ja \pmod{m}</math>
 +
:หรือ <math>m\mid ia\ -\ ja  \Rightarrow\ m\mid (\ i\ -\ j\ )\ a</math>
 +
นั้นคือมีจำนวนเต็ม k ที่
 +
:<math>mk\ =\ a(i-j)</math>
 +
:<math>k\ =\ \frac{a(i-j)}{ m}</math>
 +
จาก gcd(a,m ) =1 จะได้ว่า m ต้องหาร (i -j) ลงตัว
 +
แต่ (i-j) มีค่าได้ตั้งแต่ 1 ถึง m-1 (ไม่เป็น 0 เนื่องจาก <math> i\ \neq\ j\ )</math>ซึ่งน้อยกว่า m
 +
ซึ่งเป็นไปไม่ได้
 +
{{จบบทพิสูจน์}}
 +
 +
แนวทางการ
 +
Proof by Contradiction
 +
จะพิสูจน์ (P) สมมุติ <math>\sim P \rightarrow F</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>
 +
:<math>x(k_1i\ - k_2j)\ = 1</math>
 +
:ซึ่งจะเห็นว่า ผลลบของเทอมที่คูณ x เป็นจำนวนเต็ม คูณอยู่กับ x ซึ่งมากกว่าหนึ่งจึงเป็นไปไม่ได้ที่ <math>x(k_1i\ - k_2j)</math> เท่ากับ 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)<nowiki>:</nowiki> :GCD(a,b) = gcd(a,b)
 +
 +
;base case<nowiki>:</nowiki>: ถ้า b=0 , GCD(a,b) =a = gcd(a,b)
 +
 +
;inductive step<nowiki>:</nowiki>:ถ้า b > 0 และ a > b แล้ว
 +
 +
:'''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(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)==
 
==การกระจายความลับ (Secret Sharing)==
 +
ถ้า polynomial f มี degree d เราสามารถให้ <math> (x_0,y_0),\ (x_1,y_1),\  ...\  ,\ (x_d,y_d)</math> จะมี polynomial degree d เพียงตัวเดียวที่ผ่าน ทุกจุดดังกล่าว และ polynomial ดังกล่าวหาได้
 +
 +
ต้องการ key M ให้กลุ่มคน n คน ให้ทุกๆกลุ่มคน < k คน ไม่ทราบข้อมูลเกี่ยวกับ key เลย
 +
:กลุ่มคน k คนหา key ได้
 +
 +
หา prime p > key และ p - 1 > n เลือก<math> a_{k-1},a_{k-2},...,a_1</math> จากเซต { 1, 2, ... , p-1}
 +
 +
ให้ ak-1 ไม่เท่ากับ 0
 +
 +
ให้ <math>f(x) = a_{k-1}\,x^{k-1} + a_{k-2}\,x^{k-2} +...+a_2\,x^2+a_1\,x + M</math>
 +
เราจะเลือกจุด <math>\ x_1,\ x_2,\ ...,\ x_n</math> ที่ไม่ซ้ำกัรและไม่เท่ากับ 0 ให้ <math>(\ x_i,\ f(x_i))</math> กับคนที่ i

รุ่นแก้ไขปัจจุบันเมื่อ 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 ที่

Littlebox.png

Propostition 
ถ้า และ แล้ว

proof:

Littlebox.png

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

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

นิยาม: สำหรับถ้า จะเรียก 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 นั้นเอง

Littlebox.png

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


Proof of Claim1: สมมุติให้มีจำนวนเต็ม ที่

ที่
จะได้
หรือ

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

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

Littlebox.png

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

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


Proof(Indirect):

ไม่มี mutiplicative inverse modulo m

ให้
หรือ
พิจารณา
ซึ่งจะเห็นว่า ผลลบของเทอมที่คูณ x เป็นจำนวนเต็ม คูณอยู่กับ x ซึ่งมากกว่าหนึ่งจึงเป็นไปไม่ได้ที่ เท่ากับ 1
Littlebox.png

ยูคลิด 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