ọ ủ

ơ ở

ng 2. C  s  toán h c c a lý

ươ ế

ậ

Ch thuy t m t mã

ố ọ

ậ

ế ủ ố

ố 2.1 S  h c các s  nguyên và thu t  toán Euclide Tính chia h t c a s  nguyên

 Cho a, b≠0 là các s  nguyên. Ta nói a chia h t cho b

ế ố

ế ồ ạ ố n u t n t i 1 s  c sao cho:

 a=b.c ệ  Ký hi u b|a ộ ố ủ  a là b i s  c a b (divisor), b là  ụ  Ví d : 2| 6

ướ ố ủ c s  c a a ( mutiple)

ế ủ

ố

Tính chia h t c a các s  nguyên

ớ

ế ế ế ế ế ∈  V i a, b, c, d, e  Z, ta có:  a|c⇒  ­ N u a|b và b|c   ­ N u a|b, thì ac|bc  c∀  ­ N u c|a và c|b, thì c| da+ be  d, e∀  ­ N u a|b và b≠0, thì |a|≤|b|  ­ N u a|b và b|a, thì |a|=|b|

ủ

ị

Đ nh lý phép chia c a Euclid

q Đ i v i m i s  n, d\{0}, luôn t n t

ọ ố ồ ạ ấ ố i duy nh t các s  q,

ớ

n=qd+r    v i 0

q n là s  b  chia (divident), d là s  chia (divisor), q

ố ớ ∈ r Z sao cho:

ệ ố ị ố ố ư ố ng s  (quotient), r là s  d  (remainder), ký hi u

ươ th Rd (n) q   ví d :ụ q              R7 (16)=2 q              R7 (­16)=?

ớ

ấ

c chung l n nh t(greatest

∈ ướ ủ

Ướ common divisor­ gcd) ∈ ượ  Cho hai s  a, b  Z\{0}, c Z đ

ọ c g i là c chung c a

ế

 C đ ế

ướ ượ ấ ớ ố a và b n u c|a và c|b ọ c g i là c chung l n nh t, ký hi u gcd(a, b),

ấ ố ệ ế ớ n u nó là s  nguyên l n nh t a, b chia h t.

ộ

ấ

∈ ượ ọ ủ ộ

ỏ B i chung nh  nh t(Least  common multiple) ∈  Cho hai s  a, b  Z\{0}, c Z đ

c g i là b ichung c a

ế

 C đ ế

ố a và b n u a|c và b|c ọ ượ ộ ệ ấ ỏ

c g i là b ichung nh  nh t, ký hi u lcm(a, b),  ấ ế ố ỏ n u nó là s  nguyên nh  nh t chia h t cho a, b.

ậ

Thu t toán Euclide tìm UCLN

Ø Input: hai s  không âm a, b, a>=b Ø Output: gcd(a, b).

ự

ệ

Trong khi b>=0  th c hi n:

r a mod b  a b  b r ế

ả

Cho k t qu  (a)

ố

ở ộ

ậ

Thu t toán Euclid m  r ng

 Thu t toán Euclid m  r ng dùng đ  tìm hai s  x, y

ể ậ ố

 ax + by = gcd(a, b)

ỏ ươ ở ộ ng trình sau: th a mãn ph

ở ộ

Euclide m  r ng

Ví dụ

 Cho a=4864, b= 3458, tìm (d, x, y)

(38, 32, ­45)

ố

ố

Nguyên t

ợ  và h p s

ượ ọ ố ố nhiên 1

∈ ế ỉ

∈ ả ọ c g i là

ố ự  S  t ế ố ự  S  t ợ h p s (composite).

ượ ọ ố ế c g i là nguyên t cùng nhau n u

n u nó ch  chia h t cho chính nó và cho 1. ố ượ  đ  hiên n N không ph i là nguyên t ố ố  Hai s  a và b đ gcd(a, b)=1.

 M i s  nguyên n>1đ u có th  vi

ọ ố ề ể ế ướ ạ t d i d ng:

n=p1a1 .p2a2 …pkak

ả ả ố ợ  L u ý: s  1 không p i là ngto cũng không ph i là h p

ư s .ố

ố

ế

ố

Hàm đ m các s  nguyên t

ế

ố  Hàm đ m các s  nguyên t (prime counting function)  ố ỏ ơ ố ả ế ố nh  h n hay

∏ (n) cho k t qu  là các s  nguyên t b ng n N∈ ằ

∈ ∏(n)=|{p P| p≤n}|

ợ

ể  nhiên n  N đ u có th  phân tích thành các

ừ ố ố Phân tích h p s  thành th a s   nguyên tố ỗ ố ự  M i s  t ố ừ

ố ∈ ề ấ  duy nh t th a s  nguyên t

ủ

ụ ố  ep (n): là s  mũ c a p  Ví d : 4725=32 .53 . 7

ợ

ừ ố ố Phân tích h p s  thành th a s   nguyên tố

ủ

ụ  Ví d : tìm gcd và lcm c a ( 143, 220)  143=11.13  220= 2^2. 5. 11  Gcd(143, 220)= 2min(2,0)  .5min(1,0) . 11. 13min(1, 0)  lcm(143, 220)= 2max(2,0)  .5max(1,0) . 11. 13max(1, 0)

Euler’s Totient function

 Dùng đ  đ m các s  

∈ ể ế ố ố ớ cùng nhau v i

n.

ɸ ố thì  (p)= p­1

ế ế ɸ ụ ɸ  Ví d :  (10)=4  N u p là nguyên t  N u n=p.q thì  (n)=(p­1)(q­1)

Euler’s Totient function

ọ ố ừ ể ớ ố  V i m i s  nguyên n có th  phân tích thành th a s

nguyên t thìố

 Ví d :  (45)=  (32 .5)=(3­1)2­1 .(5­1)1­1 =24

ụ ɸ ɸ

Euler’s Totient function

 T   (p.q)=(p­1)(q­1), ta có th  tính p khi bi

ừ ɸ ể ế ɸ t  (p.q)

ứ theo công th c sau:

ượ ứ  Công th c này đ c dùng trong mã hóa công khai

RSA

ư

ồ

2.2. Đ ng d  theo modular

∈ ư ớ ∈  Cho a, b Z, n N. a đ c g i là đ ng d  v i b theo

ồ ế

ệ

 Ký hi u:  a  Ví d :  7ụ              4(cid:0)

ọ ượ ứ ế modulo n n u n|a­b( t c a­b chia h t cho n, hay a và b  ố ư chia cho n cùng s  d ) (cid:0) b(mod n) (cid:0) 12(mod 5) ­1(mod 5)

ấ ồ

ư

Tính ch t đ ng d  modular n

∈ ∈ ọ ố ấ ỏ V i m i s  n N, a, b,c  Z các tính ch t sau luôn th a

ớ mãn:

ạ ấ

1. a(cid:0) a(mod n)­ tính ch t ph n x 2. N u aế

3.

ố ứ

ả (cid:0) b(mod n) thì b(cid:0) a(mod n)­ tính đ i x ng. If a(cid:0) b(mod n) and b(cid:0) c(mod n) thì a(cid:0) c(mod n) (tính  ầ ắ b c c u) ệ ồ ệ ươ ư ươ Quan h  đ ng d  theo modular n là quan h  t ng đ ng

ồ

ư

Các phép toán đ ng d

ầ ộ

ể ự ự ệ ư ộ ươ ố ư  Có th  th c hi n các phép c ng và nhân ph n d    nh  c ng nhân các s  nguyên. ng t t

baR (

)

aRR ( )(

))

n

(cid:0) (cid:0) (cid:0)

baR ).(

n bRaRR (

n (

).

bR ( n ))

(

n

n

n

n

 Ví d : ụ

(cid:0)

R

12(

)18

)12(

))18(

2

7

(cid:0) (cid:0) (cid:0) (cid:0)

)18.12(

R 7 ))18(

6)5.4(

R 7

RR ( 7 7 RR ).12( ( 7 7

R 7

R 7

(cid:0) (cid:0) (cid:0)

ả

ị

Ngh ch đ o nhân

 N u t n t ọ

i m t s  b Zn sao cho ab (cid:0) 1(mod n) thì b

ế ồ ạ ượ đ

n

)

(cid:0) c g i là ngh ch đ o nhân c a a modulo n. 1 (cid:0) ộ ố ị b

 Đi u ki n đ  a có ngh ch đ o nhân khi và ch  khi

∈ ả a ị ề ệ ỉ

ụ

ủ (mod ả ể ố gcd(a, n)=1 ( a, n nguyên t  cùng nhau).  Ví d : 8= 22­1 (mod 25) vì:                          8.22=176=1(mod 25)

ụ

ả

ị

Ví d  ngh ch đ o nhân

 Cho m=5, a=2. gcd(2,5)=1, do đó 2 có ngh ch đ o

ả ị

nhân modulo 5.

  3=2­1 (mod 5) vì 2.3(cid:0) 1(mod 5) ậ  gcd(4, 15)=1 v y 4 có ngh ch đ o nhân modulo 15   4.4(cid:0) 1(mod 15) nên 4=4­1 (mod 15)

ả ị

ả

ị Cách tìm ngh ch đ o nhân

 C1: gi

ả ậ

au

(cid:0) (cid:0) i thu t Euclid m  r ng 1

u

p

a

ở ộ pu 1(cid:0) (cid:0)

 C2: dùng gi

ả ậ

2

1

(cid:0) (cid:0)

mod ố i thu t tính s  mũ nhanh a p

(cid:0)

a

p mod

ả

ị

Cách tìm ngh ch đ o nhân(tt)

 Đ  tìm ngh ch đ o nhân modulo n , áp d ng Euclid

ụ ả ị

ể ở ộ m  r ng:

na

yn

xa

1),

(cid:0) (cid:0) (cid:0)

gcd( n

)

1 (mod

xa ả

(cid:0)

ị

   x là ngh ch đ o nhân a modulo n  N u gcd(a, n)=k>1 thì a không có ngh ch đ o nhân

ế ả ị

modulo n.

Ví dụ

ớ

ư

ồ L p đ ng d

 Phép tính đ ng d  mod m tách t p s  nguyên ra m l p,

ư ậ ớ

ỗ ớ ồ ố ố ư ớ ồ ậ

m i l p là t p các s  nguyên đ ng d  v i nhau theo mod  m.

ạ /m ệ  Ký hi u:    ỗ ố ớ  M i s  l p

/mℤ ℤ ℤ ℤ có đúng 1 s  n m trong đo n [0, m­1],  ỗ ố ố ằ ệ ạ

ạ ớ cho nên m i s  nguyên a đ i di n cho 1 l p. ệ ớ ớ  Các phép tính trong l p thông qua đ i di n l p.

ố ư

ị

2.3 Đ nh lý s  d  trung hoa

x

(cid:0) (cid:0)

x

a 1 (mod a

n )1 n

(mod

2

)2

(cid:0) (cid:0) (cid:0)

(cid:0)

(cid:0)

... x

a

(mod

)

k

n k

ệ ố

ồ

ươ

ừ

ồ

ộ

ng trình đ ng d  v i n1,…, nk t ng đôi m t

ệ ố

ấ

ư ớ ệ

Là h  th ng g m k ph ố là nguyên t

cùng nhau. H  th ng có 1 nghi m duy nh t x  Zn∈

(cid:0) (cid:0) (cid:0)

ố ư

Tìm s  d  trung hoa

ặ ớ

 Đ t mi =n/ni v i i=1,2,…,k   yi  =m­1i (mod ni ) yi là ngh ch đ o nhân c a mi

ủ ả ị

modulo ni.

 Khi đó nghi m x đ

k

ệ ượ ư c tính nh  sau:

x

n

(mod

)

yma i

i

i

(cid:0) (cid:0)

i

1

(cid:0)

Ví dụ

 Cho h  3 pt đ ng d  sau:

ư ệ ồ

(cid:0) (cid:0)

(cid:0)

(cid:0) (cid:0)

x x x

5 3 11

(mod (mod (mod

)7 )11 )13

(cid:0) (cid:0) (cid:0)

 Hãy tìm nghi m x???

ệ

Ví d (tt)ụ

  n1=7, n2=11. n3=13 (t  n=n1*n2*n3=1001   m1=n/n1=1001/7=143      m2=1001/11=91      m3=1001/13=77

ấ ả ề ố t c  đ u nguyên t cùng nhau).

Ví d (tt)ụ

 Tính y:   y1(cid:0) 143­1 (mod 7)=5

q Tính x:   x=a1*m1*y1+ a2*m2*y2+ a3*m3*y3   = 5*143*5+3*91*4+11*77*12   = 14831

y2(cid:0) 91­1 (mod 11)=4 y3(cid:0) 77­1 (mod 13)=12

ươ

ồ

ư

ệ 2.4 H  hai ph

ng trình đ ng d

ệ  Xét h  hai ph

x

(cid:0) (cid:0)

(cid:0)

x

(mod

)2

(cid:0) (cid:0)

ớ

(a2­a1)t(mod n2) ụ ượ ứ ậ i thu t này đ ề c  ng d ng nhi u trong m t mã

ươ ng trình:  a n 1 (mod )1 a n 2  V i gcd(n1,n2)=1  Tính t=n2­1 (mod n1)  Khi đó u(cid:0) ậ ả  Gi RSA

x=a 1+un1

ừ 2.5. Lũy th a modulo

 Tính ab (mod n)??? ả  Gi  Ví d :ụ

ậ ơ ả ầ ấ i thu t đ n gi n nh t là nhân a(mod n) b l n.

ừ

Lũy th a modulo

The square­and­multiply algorithm

 S  d ng tri n khai s  mũ b thành các phép bình

ể

ử ụ ươ ố ng và phép nhân. ph

Ví dụ

 Tính 722 (mod 11)

ụ

ả

◦ B1: b=(22)10  (10110)2  ◦ B2: áp d ng gi

ậ i thu t trên

ề

ộ Hàm m t chi u

 Chúng ta nói hàm: f: XY là hàm m t chi u n u

ệ ể

ọ ả ớ ộ ∈ ọ ể ế f(x)  ề ư ả ớ có th  tính toán hi u qu  v i m i x X, nh ng f­1(y)  không th  tính toán hi u qu  v i m i y RY.∈ ệ

 “tính toán hi u qu ”

ả ở ớ ộ ứ đây chúng ta nói t i đ  ph c

ệ ạ t p tính toán

ụ

 Ví d : hàm RSA             hàm bình ph ờ ạ             hàm logarith r i r c

ươ ng modular

Trapdoor function

 A one­way function f : X

→ Y is a trapdoor function if

there is a trapdoor information t and a PPT algorithm I  that can be used to efficiently compute x’= I(f(x),t) with  f(x’)= f(x).

Q&A