Bài giảng Mật mã ứng dụng: Nhập môn số học thuật toán

M™t mã ˘ng dˆng Nh™p môn sË hÂc thu™t toán

1 / 53

Tài liªu tham kh£o

•

J. Hoffstein, J. Pipher, J. H. Silverman, An Introduction to Mathematical Cryptography, Springer-Verlag – Undergraduate Texts in Mathematics, 2nd Ed., 2014.

•

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press. 2009.

2 / 53

H. H. Khoái, Nh™p môn sË hÂc thu™t toán •

K˛ hiªu

3 / 53

1, 2, 3, . . . N = • { . . . , 2, } 1, 0, 1, 2, . . . Z = • { }

Ví dˆ

847 573. 485331 vì 485331 = 847 • | · 355 259943 vì 259943 = •

‡nh nghæa Xét a, b

Z. Ta nói

2 b là ˜Óc cıa a, hay a chia h∏t cho b

n∏u có mÎt sË nguyên c sao cho

a = bc.

| Ta vi∏t b ta vi∏t b a ∫ chø a chia h∏t cho b. N∏u a không chia h∏t cho b thì a.

4 / 53

‡nh nghæa Xét a, b

Z. Ta nói

2 b là ˜Óc cıa a, hay a chia h∏t cho b

n∏u có mÎt sË nguyên c sao cho

a = bc.

| Ta vi∏t b ta vi∏t b a ∫ chø a chia h∏t cho b. N∏u a không chia h∏t cho b thì a.

Ví dˆ

847 573. • | · 355 485331 vì 485331 = 847 259943 vì 259943 = •

4 / 53

Mªnh ∑ Xét a, b, c

2 N∏u a

3 N∏u a

5 / 53

Bài t™p Hãy ch˘ng minh mªnh ∑ tr˜Óc.

6 / 53

Ví dˆ

12 và 6 18 và không có sË nào lÓn hÏn gcd(12, 18) = 6 vì 6 • | | có tính chßt này.

gcd(748, 2014) = 44 vì • 1, 2, 4, 11, 17, 22, 34, 44, 68, 187, 374, 748 , các ˜Óc cıa 748 = { } 1, 2, 4, 8, 11, 22, 23, 44, 46, 88, 92, 184, 253, các ˜Óc cıa 2024 = { 506, 1012, 2024 . }

‡nh nghæa

◊Óc chung cıa hai sË nguyên a và b là sË nguyên d th‰a mãn: • d a và d b. | |

7 / 53

Ta k˛ hiªu gcd(a, b) là ˜Óc chung lÓn nhßt cıa a và b. •

‡nh nghæa

◊Óc chung cıa hai sË nguyên a và b là sË nguyên d th‰a mãn: • d a và d b. | |

Ta k˛ hiªu gcd(a, b) là ˜Óc chung lÓn nhßt cıa a và b. •

Ví dˆ

12 và 6 18 và không có sË nào lÓn hÏn • | |

7 / 53

gcd(12, 18) = 6 vì 6 có tính chßt này. gcd(748, 2014) = 44 vì • 1, 2, 4, 11, 17, 22, 34, 44, 68, 187, 374, 748 , { } 1, 2, 4, 8, 11, 22, 23, 44, 46, 88, 92, 184, 253, các ˜Óc cıa 748 = các ˜Óc cıa 2024 = { . 506, 1012, 2024 }

MÎt sË tính chßt cıa hàm gcd

8 / 53

a, b) a | | a vÓi mÂi k gcd(a, b) = gcd(b, a) gcd(a, b) = gcd( gcd(a, 0) = gcd(a, ka) = Z. | | 2

‡nh nghæa (Chia lßy d˜) Xét a, b là các sË nguyên d˜Ïng. Ta nói a chia cho b có th˜Ïng là q và ph¶n d˜ là r n∏u

vÓi 0 r < b. a = b q + r · 

Bài t™p Hãy ch˘ng minh r¨ng các sË q và r  trên xác ‡nh duy nhßt bi a và b.

9 / 53

Thu™t toán tính gcd(a, b)

Chia a cho b ta ˜Òc • vÓi 0 r < b. a = b q + r ·  Áp dˆng Øng th˘c •

10 / 53

gcd(a, b) = gcd(b, r).

Ví dˆ: Tính gcd(2024, 748)

11 / 53

gcd = 44 · 2024 = 748 748 = 528 528 = 220 220 = 88 88 = 44 2 + 528 1 + 220 2 + 88 · 2 + 44 2 + 0 ·

b. Thu™t toán sau ây tính

‡nh l˛ (Thu™t toán Euclid) Xét a, b là hai sË nguyên d˜Ïng vÓi a gcd(a, b) sau mÎt sË h˙u h§n b˜Óc.

1 ∞t r0 = a và r1 = b. 2 ∞t i = 1. 3 Chia ri

1 cho ri, ta ˜Òc

1 = ri

4 N∏u ri+1 = 0, v™y thì

vÓi 0 ri qi + ri+1 ri+1 < ri. · 

ri = gcd(a, b)

5 Ng˜Òc l§i, ri+1 > 0, v™y thì ∞t i = i + 1 và quay l§i B˜Óc 3.

12 / 53

và thu™t toán k∏t thúc.

‡nh l˛ Phép chia (B˜Óc 3) cıa Thu™t toán Euclid th¸c hiªn nhi∑u nhßt

13 / 53

l¶n. log2(b) + 2

Thu™t toán Euclid (d§ng ª quy)

EUCLID(a, b) if b == 0 return a else

14 / 53

return EUCLID(b, a mod b)

Thu™t toán Euclid m rÎng

• Thu™t toán Euclid có th∫ m rÎng ∫ tìm thêm mÎt sË thông tin.

• Cˆ th∫, chúng ta m rÎng thu™t toán ∫ tính thêm hª sË x, y th‰a mãn

d = gcd(a, b) = ax + b y.

15 / 53

• Các hª sË x, y có th∫ âm ho∞c b¨ng 0. Các hª sË này s≥ có ích sau này khi tích ph¶n t˚ ngh‡ch £o trong sË hÂc modun.

Thu™t toán Euclid m rÎng

• Input : C∞p sË nguyên d˜Ïng (a, b) Output: BÎ ba (d, x, y) th‰a mãn •

d = gcd(a, b) = ax + b y.

EXTENDED-EUCLID(a, b) if b == 0 return (a, 1, 0) else

16 / 53

a/b y 0) b c (d 0, x 0, y 0) = EXTENDED-EUCLID(b, a mod b) (d, x, y) = (d 0, y 0, x 0 return (d, x, y)

Tính úng ≠n cıa thu™t toán

Thu™t toán tìm (d, x, y) th‰a mãn • d = gcd(a, b) = ax + b y

N∏u b = 0, v™y thì • 0. d = a = a 1 + b · · = 0, thu™t toán EXTENDED-EUCLID s≥ tính (d 0, x 0, y 0) • 6 N∏u b th‰a mãn

d 0 = d = gcd(b, a mod b)

= bx 0 + (a mod b) y 0

17 / 53

Và v™y thì • b a/b d = b0 x 0 + (a b c a/b = a y 0 + b(x 0 ) y 0 y 0) b c

Ví dˆ

b c

a/b 1 3 1 2 2 a 99 78 21 15 6 3 b 78 21 15 6 3 0 d 3 3 3 3 3 3 x 11 3 2 1 0 1 y 14 11 3 2 1 0

• , và giá tr‡ tr£ v∑ d, x, y. a/b b c

18 / 53

• 11, 4) • 14. MÈi dòng cıa b£ng mô t£ mÎt m˘c ª quy: các giá tr‡ ¶u vào a và b, giá tr‡ tính d, x, y tr£ v∑ tr thành bÎ ba d 0, x 0, y 0 cıa m˘c ti∏p theo. LÌi gÂi thı tˆc EXTENDED-EUCLID(99,78) tr£ v∑ (3, th‰a mãn gcd(99, 78) = 3 = 99 11) + 78 ( · ·

Bài t™p Hãy tính giá tr‡

19 / 53

(d, x, y) = EXTENDED-EUCLID(899, 493).

‡nh nghæa Xét sË nguyên m modun m n∏u a

1. Ta nói hai sË nguyên a và b là Áng d˜ theo b chia h∏t cho m, và vi∏t a b (mod m) ⌘

SË m ˜Òc gÂi là modun. Áng hÁ có th∫ ˜Òc vi∏t theo nh˜ modun dùng modun m = 12:

20 / 53

và 2 1 6 + 9 = 15 3 (mod 12) 3 = 11 (mod 12) ⌘ ⌘

Ví dˆ

21 / 53

17 7 chia h∏t cho 5. • ⌘ 19 7 (mod 5) vì 10 = 17 6 (mod 11) vì 19 6 = 13 không chia h∏t cho 11 • 6⌘

2 Xét sË nguyên a. V™y thì tÁn t§i sË nguyên b th‰a mãn

a b 1 (mod m) n∏u và chø n∏u gcd(a, m) = 1. · ⌘ N∏u tÁn t§i sË b nh˜ v™y thì ta nói b là ngh‡ch £o cıa a theo modun m.

Mªnh ∑ Xét sË nguyên m 1 N∏u a1

22 / 53

a2 (mod m) và b1 b2 (mod m), v™y thì ⌘ ⌘ và ⌘ a1 ± a1 b1 b1 a2 a2 b2 ± b2 (mod m), (mod m). · ⌘ ·

Mªnh ∑ Xét sË nguyên m 1 N∏u a1

2 Xét sË nguyên a. V™y thì tÁn t§i sË nguyên b th‰a mãn

a2 (mod m) và b1 b2 (mod m), v™y thì ⌘ ⌘ và ⌘ a1 ± a1 b1 b1 a2 a2 b2 ± b2 (mod m), (mod m). · ⌘ ·

a b 1 (mod m) n∏u và chø n∏u gcd(a, m) = 1. · ⌘

22 / 53

N∏u tÁn t§i sË b nh˜ v™y thì ta nói b là ngh‡ch £o cıa a theo modun m.

1 theo modun 15.

T˜Ïng t¸ gcd(4, 15) = 1. Hãy tìm 4 •

Bài t™p

23 / 53

• Lßy m = 5 và a = 2. Rõ ràng gcd(2, 5) = 1, v™y thì tÁn t§i ngh‡ch £o cıa a theo modun 5. Hãy tìm a

Bài t™p

1. 1 theo modun 15.

•

23 / 53

Lßy m = 5 và a = 2. Rõ ràng gcd(2, 5) = 1, v™y thì tÁn t§i ngh‡ch £o cıa a theo modun 5. Hãy tìm a T˜Ïng t¸ gcd(4, 15) = 1. Hãy tìm 4 •

‡nh nghæa Ta vi∏t

0, 1, 2, . . . , m 1 Z/mZ = { } và gÂi Z/mZ là vành sË nguyên modun m.

Nh™n xét Khi chúng ta th¸c hiªn phép cÎng ho∞c nhân trong Z/mZ ta luôn chia k∏t qu£ cho m và lßy ph¶n d˜.

24 / 53

0 1 2 3 4

B£ng: CÎng và nhân theo modun 5

25 / 53

+ 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 0 0 0 0 0 1 2 3 4 0 2 4 1 3 0 3 1 4 2 0 4 3 2 1 · 0 1 2 3 4

‡nh nghæa Ta bi∏t r¨ng a có ngh‡ch £o modun m n∏u và chø n∏u gcd(a, m) = 1. Các sË kh£ ngh‡ch gÂi là Ïn v‡. Ta k˛ hiªu t™p mÂi Ïn v‡ bi

a { 2 } a (Z/mZ)⇤ = = Z/mZ : gcd(a, m) = 1 Z/mZ : a có ngh‡ch £o theo modun m { 2 }

26 / 53

T™p (Z/mZ)⇤ ˜Òc gÂi là nhóm Ïn v‡ theo modun m.

Ví dˆ Nhóm Ïn v‡ theo modun 24 là

1, 5, 7, 11, 13, 17, 19, 23 . (Z/24Z)⇤ = { } B£ng nhân cıa nhóm này xác ‡nh nh˜ sau:

1 5 7 11 13 17 19 23

5 1 11 7 7 11 1 5

27 / 53

11 13 17 19 23 1 17 13 23 19 7 5 19 23 13 17 5 7 23 19 17 13 11 1 11 1 13 17 19 23 7 17 13 23 19 5 5 7 19 23 13 17 1 23 19 17 13 11 7 11 1 5 5 1 11 7 · 1 5 7 11 13 17 19 23

Ví dˆ Nhóm Ïn v‡ theo modun 7 là

1, 2, 3, 4, 5, 6 (Z/7Z)⇤ = }

{ vì các t¯ 1 ∏n 6 ∑u nguyên tË cùng nhau vÓi 7. B£ng nhân cıa nhóm này ˜Òc xác ‡nh nh˜ d˜Ói ây.

28 / 53

1 2 3 4 5 6 1 2 3 4 5 6 2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 5 3 1 6 4 2 6 5 4 3 2 1 · 1 2 3 4 5 6

‡nh nghæa Phi hàm Euler là hàm (m) ‡nh nghæa bi lu™t

0 . a < m : gcd(a, m) = 1 (m) = #(Z/mZ)⇤ = # {  }

29 / 53

Ví dˆ và (24) = 8 (7) = 6.

Tính lÙy th¯a nhanh

Ví dˆ Gi£ s˚ ta muËn tính

3218 (mod 1000).

¶u tiên, ta vi∏t 218  d§ng cÏ sË 2:

218 = 2 + 23 + 24 + 26 + 27.

+24

+26

+27

V™y thì 3218 tr thành

3218 323 324 326 327 . = 32+23 = 32 · · · · ∫ ˛ r¨ng, dπ tính các mÙ

30 / 53

3 , 32 , 322 , 323 , 324 , . . .

Ví dˆ (ti∏p) Ta l™p b£ng

i 0 1 2 3 4 5 6 7

32i 3 9 81 561 721 841 281 961 (mod 1000)

rÁi tính

31 / 53

3218 · · 323 · 561 327 961 (mod 1000) ⌘ · · · 324 326 = 32 · 9 721 281 · 489 (mod 1000). ⌘

Thu™t toán tính nhanh a b

(mod n)

1, . . . , b0

MODULAR-EXPONENTIATION(a, b, n)

i h c = 0 d = 1 Bi∫u diπn b = bk, bk for i = k downto 0

d) (mod n) · c = 2c d = (d if bi == 1

32 / 53

c = c + 1 d = (d a) (mod n) · return d

Ví dˆ

0 0 2 0 8 0 2 3 0 70 4 1 35 7 0 4 6 0 8 9 i 5 bi 1 1 17 1 c 7 49 157 526 160 241 298 166 d 1 0 140 280 560 67 1

K∏t qu£ tính a b (mod n) vÓi •

33 / 53

a = 7, b = 560 = , và n = 561 1000110000 i h Giá tr‡ ˜Òc chø ra sau mÈi b˜Óc l∞p. • K∏t qu£ cuËi cùng b¨ng 1 •

SË nguyên lÓn hÏn 1 không ph£i sË nguyên tË ˜Òc gÂi là • hÒp sË.

‡nh nghæa

34 / 53

• SË nguyên tË là sË nguyên lÓn hÏn 1, không chia h∏t cho sË nguyên d˜Ïng nào ngoài 1 và chính nó.

‡nh nghæa

• SË nguyên tË là sË nguyên lÓn hÏn 1, không chia h∏t cho sË nguyên d˜Ïng nào ngoài 1 và chính nó.

34 / 53

• SË nguyên lÓn hÏn 1 không ph£i sË nguyên tË ˜Òc gÂi là hÒp sË.

100 sË nguyên tË ¶u tiên

35 / 53

2 31 73 127 179 233 283 353 419 467 3 37 79 131 181 239 293 359 421 479 5 41 83 137 191 241 307 367 431 487 7 43 89 139 193 251 311 373 433 491 11 47 97 149 197 257 313 379 439 499 13 53 101 151 199 263 317 383 443 503 17 59 103 157 211 269 331 389 449 509 19 61 107 163 223 271 337 397 457 521 23 67 109 167 227 277 347 401 461 523 29 71 113 173 229 281 349 409 463 541

Mªnh ∑ Xét sË nguyên tË p, và gi£ s˚ r¨ng tích ab cıa hai sË a và b chia h∏t cho p. V™y thì a ho∞c b ph£i chia h∏t cho p. TÍng quát hÏn n∏u

36 / 53

p a1a2 an, | · · · v™y thì ít nhßt mÎt trong các sË ai ph£i chia h∏t cho p.

Bài t™p Hãy ch˘ng minh mªnh ∑ tr˜Óc.

37 / 53

‡nh l˛ MÂi sË nguyên a

2 ∑u phân tích ˜Òc thành tích các sË nguyên tË

a = pe1 per r . pe2 2 pe3 3 · · · ·

38 / 53

· HÏn n˙a phân tích này là duy nhßt n∏u các th¯a sË ˜Òc vi∏t vÓi th˘ t¸ không gi£m.

Bài t™p Hãy ch˘ng minh ‡nh l˛ tr˜Óc.

39 / 53

‡nh nghæa

•

40 / 53

‡nh l˛ cÏ b£n cıa sË hÂc chø ra r¨ng trong phân tích th¯a sË nguyên tË cıa sË nguyên d˜Ïng a, mÈi sË nguyên tË p xußt hiªn vÓi mÎt sË mÙ nào ó. Ta k˛ hiªu sË mÙ này là ordp(a) và gÂi nó là cßp (ho∞c sË mÙ) cıa p trong a. ∫ cho tiªn, ta kí hiªu ordp(1) = 0 vÓi mÂi sË nguyên tË p. •

Ví dˆ Phân tích cıa 1728 là

33. 1728 = 26 · V™y thì

ord2(1726) = 6, ord3(1726) = 3,

41 / 53

và 5. ordp(1728) = 0 vÓi mÂi sË nguyên tË p

Mªnh ∑ Xét sË nguyên tË p. Khi ó mÂi ph¶n t˚ a khác 0 cıa Z/pZ ∑u có ngh‡ch £o, có nghæa r¨ng, tÁn t§i b ∫

1 n∏u p

ab 1 (mod p).

⌘ 1 mod p, ho∞c Ïn gi£n là a Ta k˛ hiªu giá tr‡ b này bi a ã xác ‡nh.

Mªnh ∑ này chø ra r¨ng

42 / 53

1, 2, 3, 4, . . . , p 1 . (Z/pZ)⇤ = { }

1 cıa ph¶n t˚ a

Bài t™p Hãy chø ra thu™t toán tính ph¶n t˚ ngh‡ch £o a trong nhóm (Z/pZ)⇤.

43 / 53

Tr˜Ìng h˙u h§n Fp

•

• N∏u p nguyên tË, v™y thì t™p Z/pZ vÓi phép toán cÎng, tr¯, nhân và lu™t chia là mÎt tr˜Ìng. Tr˜Ìng Z/pZ chø có h˙u h§n ph¶n t˚. ây là tr˜Ìng h˙u h§n và ta k˛ hiªu Fp. Ta vi∏t (Fp)⇤ cho nhóm (Z/pZ)⇤. Trong Fp ng˜Ìi ta th˜Ìng k˛ hiªu •

44 / 53

a = b thay cho a b (mod p). ⌘

Ví dˆ

B£ng: Các lÙy th¯a theo theo modun 7

1 12 2 22 3 32 4 42 5 52 6 62 11 21 31 41 51 61 1 13 4 23 2 33 2 43 4 53 1 63 1 14 1 24 6 34 1 44 6 54 6 64 1 15 2 25 4 35 4 45 2 55 1 65 1 16 4 26 5 36 2 46 3 56 6 66 1 1 1 1 1 1 ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘ ⌘

Câu h‰i T§i sao cÎt bên tay ph£i toàn nh™n giá tr‡ 1?

45 / 53

‡nh l˛ (‡nh l˛ Fermat nh‰) Xét sË nguyên tË p và xét sË nguyên a. Khi ó

46 / 53

a, ap a. 1 (mod p) n∏u p 0 (mod p) n∏u p ⌘ ® - |

Ví dˆ SË p = 15485863 là sË nguyên tË, v™y thì

215485862 1 (mod 15485863). ⌘ V™y thì, không c¶n tính toán ta cÙng bi∏t r¨ng

47 / 53

sË 215485862 1 là bÎi sË cıa 15485863.

Nh™n xét ‡nh l˛ Fermat nh‰ và thu™t toán tính nhanh lÙy th¯a cho ta mÎt ph˜Ïng pháp hÒp l˛ ∫ tính ngh‡ch £o theo modun p. Cˆ th∫

ap (mod p). a ⌘

48 / 53

ThÌi gian tính toán cıa ph˜Ïng pháp này t˜Ïng t¸ nh˜ dùng thu™t toán Euclid m rÎng.

‡nh nghæa Cßp cıa ph¶n t˚ a theo modun p là sË mÙ k > 0 nh‰ nhßt th‰a mãn

ak 1 (mod p). ⌘

1 (mod p). V™y thì n chia h∏t cho cßp cıa a theo modun p. ∞c

Mªnh ∑ Xét sË nguyên tË p và xét sË nguyên a không chia h∏t cho p. Gi£ s˚ an ⌘ biªt, p

49 / 53

1 chia h∏t cho cßp cıa a.

Bài t™p Hãy ch˘ng minh mªnh ∑ tr˜Óc.

50 / 53

F⇤p th‰a mãn 2

‡nh l˛ (‡nh l˛ c´n nguyên thıy) Xét sË nguyên tË p. Khi ó có tÁn t§i mÎt ph¶n t˚ g mÂi ph¶n t˚ cıa F⇤p ∑u là mÎt lÙy th¯a nào ó cıa g. T˘c là

1, g, g 2, g 3, , g p . F⇤p = { } · · ·

51 / 53

1. Các ph¶n t˚ có tính chßt này ˜Òc gÂi là c´n nguyên thıy cıa Fp ho∞c ph¶n t˚ sinh cıa F⇤p. Chúng là các ph¶n t˚ cıa F⇤p có cßp p

Ví dˆ Tr˜Ìng F11 có 2 là mÎt c´n nguyên thıy, bi vì trong F11,

20 25 21 = 1 = 10 26 = 2 22 = 9 27 = 4 23 = 7 28 = 8 24 = 3 29 = 5 = 6.

nh˜ng 2 không ph£i c´n nguyên thıy cıa F17, bi vì trong F17

52 / 53

= 16 20 25 21 = 1 = 15 26 22 = 2 = 13 27 = 4 23 = 9 28 = 8 24 = 1

Bài t™p

53 / 53

• Hãy tìm mÎt c´n nguyên thıy cıa tr˜Ìng F17. Hãy liªt kê tßt c£ các c´n nguyên thıy cıa F17. •

54 / 53

M™t mã ˘ng dˆng Logarit rÌi r§c

1 / 54

Tài liªu tham kh£o

•

J. Hoffstein, J. Pipher, J. H. Silverman, An Introduction to Mathematical Cryptography, Springer-Verlag – Undergraduate Texts in Mathematics, 2nd Ed., 2014.

•

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press. 2009.

2 / 54

• H. H. Khoái, P. H. i∫n, SË hÂc thu™t toán: cÏ s l˛ thuy∏t và tính toán th¸c hành, NXB §i hÂc QuËc gia Hà NÎi, 2003.

Nh≠c l§i

•

• Xét sË nguyên tË (lÓn) p và tr˜Ìng h˙u h§n Fp. TÁn t§i c´n nguyên thıy g, t˘c là mÂi ph¶n t˚ khác 0 cıa Fp ∑u là mÎt lÙy th˘c nào ó cıa g.

Cˆ th∫ • g p = 1.

3 / 54

Và • 1, g, g 2, g 3, , g p F⇤p. · · · 2

‡nh nghæa Xét g là mÎt c´n nguyên thıy cıa Fp và h là mÎt ph¶n t˚ khác 0 cıa Fp. Bài toán Logarit rÌi r§c (DLP) là bài toán tìm mÎt sË mÙ x th‰a mãn

4 / 54

g x h (mod p). ⌘ SË x ˜Òc gÂi là logarit rÌi r§c cÏ s g cıa h và k˛ hiªu logg (h).

Bài t™p Hãy tính các logarit rÌi r§c sau.

1 log2(13) cho sË nguyên tË 23, cˆ th∫ p = 23, g = 2 và b§n ph£i

2 log10(22) cho sË nguyên tË p = 47. 3 log627(608) cho sË nguyên tË p = 941.

5 / 54

gi£i ph˜Ïng trình Áng d˜ 2x 13 (mod 23). ⌘

Làm th∏ nào ∫ tính log2(38679)? • MÎt ph˜Ïng pháp là tính • 20, 21, 22, 23, (mod 56509) · · · cho ∏n khi ˜Òc lÙy th¯a b¨ng 38679.

B§n có th∫ ki∫m tra r¨ng • 211235 38679 (mod 56509). ⌘

Ví dˆ

6 / 54

• Xét sË nguyên tË p = 56509, và ta có th∫ ki∫m tra g = 2 là mÎt c´n nguyên thıy modun p.

MÎt ph˜Ïng pháp là tính • 20, 21, 22, 23, (mod 56509) · · · cho ∏n khi ˜Òc lÙy th¯a b¨ng 38679.

B§n có th∫ ki∫m tra r¨ng • 211235 38679 (mod 56509). ⌘

Ví dˆ

•

6 / 54

Xét sË nguyên tË p = 56509, và ta có th∫ ki∫m tra g = 2 là mÎt c´n nguyên thıy modun p. Làm th∏ nào ∫ tính log2(38679)? •

B§n có th∫ ki∫m tra r¨ng • 211235 38679 (mod 56509). ⌘

Ví dˆ

•

6 / 54

• Xét sË nguyên tË p = 56509, và ta có th∫ ki∫m tra g = 2 là mÎt c´n nguyên thıy modun p. Làm th∏ nào ∫ tính log2(38679)? MÎt ph˜Ïng pháp là tính • 20, 21, 22, 23, (mod 56509) · · · cho ∏n khi ˜Òc lÙy th¯a b¨ng 38679.

Ví dˆ

•

6 / 54

B§n có th∫ ki∫m tra r¨ng • 211235 38679 (mod 56509). ⌘

Nh™n xét N∏u bài toán Logarit rÌi r§c có nghiªm, v™y nó có vË sË nghiªm vì

g x+k(p g k(p

1) = g x = h

7 / 54

· 1k (‡nh l˛ Fermat) · h (mod p). ⌘

Bài t™p Ch˘ng minh r¨ng logg là mÎt hàm

8 / 54

Z/(p 1)Z. logg : F⇤p !

Bài t™p Ch˘ng minh r¨ng

9 / 54

logg (ab) = logg (a) + logg (b).

F⇤p và h 2 2

Nh™n xét Bài toán logarit rÌi r§c không c¶n ph£i gi£ s˚ cÏ s g là mÎt ph¶n t˚ sinh cıa Fp. Nói chung, xét g F⇤p, bài toán logarit rÌi r§c là xác ‡nh x sao cho g x

10 / 54

h (mod p), gi£ s˚ r¨ng x tÁn t§i. ⌘

Tính ng®u nhiên cıa lÙy th¯a 627i (mod 941)

11 / 54

Bài toán logarit rÌi r§c trong nhóm

‡nh nghæa Xét nhóm G vÓi phép toán ?. Bài toán Logarit rÌi r§c cho G là xác ‡nh sË nguyên x th‰a mãn

x l¶n

g ? g ? ? g = h · · ·

12 / 54

| {z } vÓi hai ph¶n t˚ h và g trong G cho tr˜Óc.

Bài toán

• Alice và Bob muËn trao Íi mÎt khóa k chung dùng ∫ mã hóa thông tin.

• Nh˜ng hÂ chø có mÎt kênh trao Íi không an toàn: Thông tin truy∑n có th∫ b‡ nghe trÎm.

13 / 54

• Liªu có cách ∫ Alice và Bob trao Íi khóa mà dù b‡ Eve có nghe trÎm?

Giao th˘c Diffie-Hellman

•

• Alice và Bob thËng nhßt mÎt sË nguyên tË (lÓn) p và mÎt sË nguyên g (mod p). TËt nhßt hÂ nên chÂn g sao cho cßp cıa g trong F⇤p là mÎt sË nguyên tË lÓn.

14 / 54

• Alice và Bob ∫ hai giá tr‡ p và g công khai (trên Website cıa cıa hÂ).

Ví dˆ

•

15 / 54

• Alice và Bob thËng nhßt s˚ dˆng sË p = 941 và c´n nguyên thıy g = 627. Alice chÂn khóa bí m™t a = 347. Bob chÂn khóa bí m™t b = 781. Hãy tính giá tr‡ khóa chia s¥ cıa Alice và Bob. •

‡nh nghæa Xét p là mÎt sË nguyên tË và g là mÎt sË nguyên. Bài toán Diffie-Hellman (DHP) là bài toán tính giá tr‡ cıa

g ab (mod p)

16 / 54

t¯ các giá tr‡ g a (mod p) và g b (mod p).

Nh™n xét

Ng˜Òc l§i, gi£ s˚ r¨ng Eve có thu™t toán hiªu qu£ gi£i DHP. Liªu cô ta có th∫ gi£i bài toán DLP? ây v®n là câu h‰i m.

DLP chÂi DHP

Bài t™p Hãy ch˘ng minh r¨ng DHP không khó hÏn DLP. Có nghæa r¨ng, n∏u ta có thu™t toán hiªu qu£ gi£i DLP, thì ta cÙng có thu™t toán hiªu qu£ gi£i DHP.

17 / 54

DLP chÂi DHP

Bài t™p Hãy ch˘ng minh r¨ng DHP không khó hÏn DLP. Có nghæa r¨ng, n∏u ta có thu™t toán hiªu qu£ gi£i DLP, thì ta cÙng có thu™t toán hiªu qu£ gi£i DHP.

Nh™n xét Ng˜Òc l§i, gi£ s˚ r¨ng Eve có thu™t toán hiªu qu£ gi£i DHP. Liªu cô ta có th∫ gi£i bài toán DLP? ây v®n là câu h‰i m.

17 / 54

Alice g˚i Bob giá tr‡ A = 974. • Bob chÂn sË bí m™t b = 871. • Bob nên g˚i cho Alice giá tr‡ gì, và khóa bí m™t hÂ chia s¥ là gì? • B§n có th∫ oán ˜Òc sË bí m™t a cıa Alice? •

Bài t™p

18 / 54

• Alice và Bob dùng sË nguyên tË p = 1373 và cÏ s g = 2 ∫ trao Íi khóa.

Bob chÂn sË bí m™t b = 871. • Bob nên g˚i cho Alice giá tr‡ gì, và khóa bí m™t hÂ chia s¥ là gì? • B§n có th∫ oán ˜Òc sË bí m™t a cıa Alice? •

Bài t™p

•

18 / 54

Alice và Bob dùng sË nguyên tË p = 1373 và cÏ s g = 2 ∫ trao Íi khóa. Alice g˚i Bob giá tr‡ A = 974. •

Bob nên g˚i cho Alice giá tr‡ gì, và khóa bí m™t hÂ chia s¥ là gì? • B§n có th∫ oán ˜Òc sË bí m™t a cıa Alice? •

Bài t™p

•

18 / 54

• Alice và Bob dùng sË nguyên tË p = 1373 và cÏ s g = 2 ∫ trao Íi khóa. Alice g˚i Bob giá tr‡ A = 974. Bob chÂn sË bí m™t b = 871. •

B§n có th∫ oán ˜Òc sË bí m™t a cıa Alice? •

Bài t™p

•

18 / 54

• Alice và Bob dùng sË nguyên tË p = 1373 và cÏ s g = 2 ∫ trao Íi khóa. Alice g˚i Bob giá tr‡ A = 974. Bob chÂn sË bí m™t b = 871. Bob nên g˚i cho Alice giá tr‡ gì, và khóa bí m™t hÂ chia s¥ là gì? •

Bài t™p

•

18 / 54

• Alice và Bob dùng sË nguyên tË p = 1373 và cÏ s g = 2 ∫ trao Íi khóa. Alice g˚i Bob giá tr‡ A = 974. Bob chÂn sË bí m™t b = 871. Bob nên g˚i cho Alice giá tr‡ gì, và khóa bí m™t hÂ chia s¥ là gì? • B§n có th∫ oán ˜Òc sË bí m™t a cıa Alice? •

1 th‰a mãn

MÂi ph¶n t˚ a F⇤p ∑u có ph¶n t˚ ngh‡ch £o a • 2 a = 1. a · Phép nhân có tính chßt k∏t hÒp: a c. (b c) = (a b) • · · · · Phép nhân có tính chßt giao hoán: a a. b = b • · ·

MÎt sË tính chßt cıa F⇤p

19 / 54

Có ph¶n t˚ 1 a = a. F⇤p th‰a mãn 1 • 2 ·

Phép nhân có tính chßt k∏t hÒp: a c. (b c) = (a b) • · · · · Phép nhân có tính chßt giao hoán: a a. b = b • · ·

MÎt sË tính chßt cıa F⇤p

1 th‰a mãn

19 / 54

Có ph¶n t˚ 1 • · 2 MÂi ph¶n t˚ a a = a. F⇤p th‰a mãn 1 F⇤p ∑u có ph¶n t˚ ngh‡ch £o a • 2 a = 1. a ·

Phép nhân có tính chßt giao hoán: a a. b = b • · ·

MÎt sË tính chßt cıa F⇤p

1 th‰a mãn

19 / 54

Có ph¶n t˚ 1 • · 2 MÂi ph¶n t˚ a a = a. F⇤p th‰a mãn 1 F⇤p ∑u có ph¶n t˚ ngh‡ch £o a • 2 a = 1. a · Phép nhân có tính chßt k∏t hÒp: a c. (b c) = (a b) • · · · ·

MÎt sË tính chßt cıa F⇤p

1 th‰a mãn

19 / 54

Có ph¶n t˚ 1 • · 2 MÂi ph¶n t˚ a a = a. F⇤p th‰a mãn 1 F⇤p ∑u có ph¶n t˚ ngh‡ch £o a • 2 a = 1. a · Phép nhân có tính chßt k∏t hÒp: a c. b) • · · (b Phép nhân có tính chßt giao hoán: a c) = (a · · a. b = b • · ·

MÂi ph¶n t˚ a a th‰a mãn F⇤p ∑u có ph¶n t˚ ngh‡ch £o • 2 a + ( a) = 0. Phép cÎng có tính chßt k∏t hÒp: a + (b + c) = (a + b) + c. • Phép cÎng có tính chßt giao hoán: a + b = b + a. •

Tính chßt cıa F⇤p liên quan ∏n phép cÎng

20 / 54

Có ph¶n t˚ 0 F⇤p th‰a mãn 0 + a = a. • 2

Phép cÎng có tính chßt k∏t hÒp: a + (b + c) = (a + b) + c. • Phép cÎng có tính chßt giao hoán: a + b = b + a. •

Tính chßt cıa F⇤p liên quan ∏n phép cÎng

20 / 54

Có ph¶n t˚ 0 • a th‰a mãn F⇤p th‰a mãn 0 + a = a. F⇤p ∑u có ph¶n t˚ ngh‡ch £o • 2 2 MÂi ph¶n t˚ a a) = 0. a + (

Phép cÎng có tính chßt giao hoán: a + b = b + a. •

Tính chßt cıa F⇤p liên quan ∏n phép cÎng

20 / 54

Có ph¶n t˚ 0 • a th‰a mãn F⇤p th‰a mãn 0 + a = a. F⇤p ∑u có ph¶n t˚ ngh‡ch £o • 2 2 MÂi ph¶n t˚ a a + ( a) = 0. Phép cÎng có tính chßt k∏t hÒp: a + (b + c) = (a + b) + c. •

Tính chßt cıa F⇤p liên quan ∏n phép cÎng

Có ph¶n t˚ 0 • a th‰a mãn F⇤p th‰a mãn 0 + a = a. F⇤p ∑u có ph¶n t˚ ngh‡ch £o • 2

20 / 54

• 2 MÂi ph¶n t˚ a a + ( a) = 0. Phép cÎng có tính chßt k∏t hÒp: a + (b + c) = (a + b) + c. Phép cÎng có tính chßt giao hoán: a + b = b + a. •

1 ? a = 1.

Có ngh‡ch £o: VÓi mÈi ph¶n t˚ a G sao cho G tÁn t§i a 2 2

a ? a = a

G. K∏t hÒp: a ? (b ? c) = (a ? b) ? c, vÓi mÂi a, b, c 2

‡nh nghæa MÎt nhóm bao gÁm mÎt t™p G và mÎt phép toán hai ngôi ? trên G th‰a mãn ba tính chßt:

Có Ïn v‡: TÁn t§i mÎt ph¶n t˚ e G sao cho

21 / 54

G. 2 e ? a = a ? e = a vÓi mÂi a 2

G. K∏t hÒp: a ? (b ? c) = (a ? b) ? c, vÓi mÂi a, b, c 2

‡nh nghæa MÎt nhóm bao gÁm mÎt t™p G và mÎt phép toán hai ngôi ? trên G th‰a mãn ba tính chßt:

Có Ïn v‡: TÁn t§i mÎt ph¶n t˚ e G sao cho

1 ? a = 1.

21 / 54

G. 2 e ? a = a ? e = a vÓi mÂi a 2 Có ngh‡ch £o: VÓi mÈi ph¶n t˚ a G sao cho G tÁn t§i a 2 2 1 a ? a = a

‡nh nghæa MÎt nhóm bao gÁm mÎt t™p G và mÎt phép toán hai ngôi ? trên G th‰a mãn ba tính chßt:

Có Ïn v‡: TÁn t§i mÎt ph¶n t˚ e G sao cho

1 ? a = 1.

G. 2 e ? a = a ? e = a vÓi mÂi a 2 Có ngh‡ch £o: VÓi mÈi ph¶n t˚ a G sao cho G tÁn t§i a 2 2 1 a ? a = a

21 / 54

G. K∏t hÒp: a ? (b ? c) = (a ? b) ? c, vÓi mÂi a, b, c 2

G, 2

‡nh nghæa Nhóm G vÓi phép toán ? có tính chßt Giao hoán: a ? b = b ? a vÓi mÂi a, b ˜Òc gÂi là nhóm giao hoán ho∞c nhóm Abel.

22 / 54

Cßp cıa nhóm G là sË ph¶n t˚ cıa G; nó th˜Ìng ˜Òc k˛ hiªu • bi G ho∞c #G. | |

‡nh nghæa

23 / 54

N∏u nhóm G có h˙u h§n ph¶n t˚, ta gÂi G là nhóm h˙u h§n. •

‡nh nghæa

N∏u nhóm G có h˙u h§n ph¶n t˚, ta gÂi G là nhóm h˙u h§n. •

23 / 54

• Cßp cıa nhóm G là sË ph¶n t˚ cıa G; nó th˜Ìng ˜Òc k˛ hiªu bi ho∞c #G. G | |

G = Z/N Z và ? = phép cÎng. Ph¶n t˚ Ïn v‡ là gì? Cßp cıa • nhóm này là gì?

G = Z và ? = phép cÎng. Ph¶n t˚ Ïn v‡ cıa nhóm này là gì? • ph¶n t˚ ngh‡ch £o cıa ph¶n t˚ a là gì?

G = Z và ? = phép nhân có ph£i là nhóm không? T§i sao? • G = R⇤ và ? = phép nhân có ph£i là nhóm không? T§i sao? •

Ví dˆ

24 / 54

• G = F ⇤p và ? = phép nhân. Ph¶n t˚ Ïn v‡ là e = 1. Cßp cıa nhóm này là gì?

G = Z và ? = phép cÎng. Ph¶n t˚ Ïn v‡ cıa nhóm này là gì? • ph¶n t˚ ngh‡ch £o cıa ph¶n t˚ a là gì?

G = Z và ? = phép nhân có ph£i là nhóm không? T§i sao? • G = R⇤ và ? = phép nhân có ph£i là nhóm không? T§i sao? •

Ví dˆ

•

24 / 54

• G = F ⇤p và ? = phép nhân. Ph¶n t˚ Ïn v‡ là e = 1. Cßp cıa nhóm này là gì? G = Z/N Z và ? = phép cÎng. Ph¶n t˚ Ïn v‡ là gì? Cßp cıa nhóm này là gì?

G = Z và ? = phép nhân có ph£i là nhóm không? T§i sao? • G = R⇤ và ? = phép nhân có ph£i là nhóm không? T§i sao? •

Ví dˆ

•

24 / 54

G = R⇤ và ? = phép nhân có ph£i là nhóm không? T§i sao? •

Ví dˆ

•

24 / 54

G = F ⇤p và ? = phép nhân. Ph¶n t˚ Ïn v‡ là e = 1. Cßp cıa nhóm này là gì? G = Z/N Z và ? = phép cÎng. Ph¶n t˚ Ïn v‡ là gì? Cßp cıa nhóm này là gì? G = Z và ? = phép cÎng. Ph¶n t˚ Ïn v‡ cıa nhóm này là gì? ph¶n t˚ ngh‡ch £o cıa ph¶n t˚ a là gì? G = Z và ? = phép nhân có ph£i là nhóm không? T§i sao? •

Ví dˆ

•

24 / 54

• G = F ⇤p và ? = phép nhân. Ph¶n t˚ Ïn v‡ là e = 1. Cßp cıa nhóm này là gì? G = Z/N Z và ? = phép cÎng. Ph¶n t˚ Ïn v‡ là gì? Cßp cıa nhóm này là gì? G = Z và ? = phép cÎng. Ph¶n t˚ Ïn v‡ cıa nhóm này là gì? ph¶n t˚ ngh‡ch £o cıa ph¶n t˚ a là gì? G = Z và ? = phép nhân có ph£i là nhóm không? T§i sao? G = R⇤ và ? = phép nhân có ph£i là nhóm không? T§i sao? •

Ph¶n t˚ Ïn v‡ cıa nhóm này là gì? Hãy tìm công th˘c tính • ph¶n t˚ ngh‡ch £o

a b . c d ✓ ◆ T§i sao ây không ph£i là nhóm giao hoán? •

Bài t™p

MÎt ví dˆ cıa nhóm không giao hoán là •

: a, b, c, d bc G = = 0 R và ad a c b d 2 6 ◆

25 / 54

⇢✓ vÓi ? = phép nhân ma tr™n.

T§i sao ây không ph£i là nhóm giao hoán? •

Bài t™p

MÎt ví dˆ cıa nhóm không giao hoán là •

: a, b, c, d bc G = = 0 R và ad a c b d 2 6 ◆

• ⇢✓ vÓi ? = phép nhân ma tr™n. Ph¶n t˚ Ïn v‡ cıa nhóm này là gì? Hãy tìm công th˘c tính ph¶n t˚ ngh‡ch £o

25 / 54

. a c b d ✓ ◆

Bài t™p

MÎt ví dˆ cıa nhóm không giao hoán là •

: a, b, c, d bc G = = 0 R và ad a c b d 2 6 ◆

• ⇢✓ vÓi ? = phép nhân ma tr™n. Ph¶n t˚ Ïn v‡ cıa nhóm này là gì? Hãy tìm công th˘c tính ph¶n t˚ ngh‡ch £o

25 / 54

. a c b d ✓ ◆ T§i sao ây không ph£i là nhóm giao hoán? •

Ví dˆ Nhóm tuy∏n tính tÍng quát

ma tr™n th¸c A kích th˜Óc n n vÓi det(A) = 0 G Ln(R) = ⇥ } 6

{ vÓi ? = phép nhân ma tr™n.

26 / 54

Thay R bi tr˜Ìng h˙u h§n F⇤p, ta ˜Òc nhóm G L(F⇤p).

‡nh nghæa Xét G là mÎt nhóm và x là mÎt sË nguyên d˜Ïng. Ta k˛ hiªu g x là

x l¶n

g x ? g = g ? g ? · · ·

27 / 54

| {z }

g x trong nhóm Z/N Z vÓi phép cÎng có nghæa r¨ng • x g = g + g + + g · · · ·

Ví dˆ

28 / 54

g x trong nhóm F⇤p theo nghæa thông th˜Ìng. •

Ví dˆ

28 / 54

• g x trong nhóm F⇤p theo nghæa thông th˜Ìng. g x trong nhóm Z/N Z vÓi phép cÎng có nghæa r¨ng • x g = g + g + + g · · · ·

2 G. Gi£ s˚ r¨ng có tÁn t§i sË nguyên = e. SË nguyên nh‰ nhßt d có tính chßt này gÂi

‡nh nghæa Xét nhóm G và mÎt ph¶n t˚ a d˜Ïng d sao cho ad là cßp cıa a. N∏u không tÁn t§i sË nguyên nh˜ v™y thì a gÂi là có cßp vô h§n.

29 / 54

HÏn n˙a, n∏u a G có cßp d và n∏u ak k. = e, v™y thì d • 2 |

Mªnh ∑

Xét nhóm h˙u h§n G. V™y thì mÂi ph¶n t˚ cıa G có cßp h˙u h§n. •

30 / 54

Bài t™p: Hãy ch˘ng minh mªnh ∑ trên.

Mªnh ∑

30 / 54

Xét nhóm h˙u h§n G. V™y thì mÂi ph¶n t˚ cıa G có cßp h˙u h§n. • HÏn n˙a, n∏u a G có cßp d và n∏u ak k. = e, v™y thì d • 2 | Bài t™p: Hãy ch˘ng minh mªnh ∑ trên.

Chính xác hÏn, xét n = #G và d là cßp cıa a, t˘c ad là lÙy th¯a • nguyên d˜Ïng nh‰ nhßt b¨ng vÓi e. Khi ó

an và d n. = e |

‡nh l˛ (Lagrange)

G. V™y thì cßp cıa G chia h∏t • 2 Xét G là nhóm h˙u h§n và xét a cho cßp cıa a.

31 / 54

Bài t™p: Hãy ch˘ng minh ‡nh l˛ trên.

‡nh l˛ (Lagrange)

G. V™y thì cßp cıa G chia h∏t •

• Xét G là nhóm h˙u h§n và xét a 2 cho cßp cıa a. Chính xác hÏn, xét n = #G và d là cßp cıa a, t˘c ad là lÙy th¯a nguyên d˜Ïng nh‰ nhßt b¨ng vÓi e. Khi ó

an và d n. = e |

31 / 54

Bài t™p: Hãy ch˘ng minh ‡nh l˛ trên.

Bài toán logarit rÌi r§c trong nhóm

‡nh nghæa (Nh≠c l§i) Xét nhóm G vÓi phép toán ?. Bài toán Logarit rÌi r§c cho G là tìm sË nguyên x th‰a mãn

g x = h

32 / 54

vÓi hai ph¶n t˚ h và g trong G cho tr˜Óc.

G là mÎt ph¶n t˚ có cßp N . V™y thì bài toán 2

Mªnh ∑ (Ch∞n t¶m th˜Ìng cho DLP) Xét nhóm G và g logarit rÌi r§c

g x = h

33 / 54

(N ) b˜Óc, mÈi b˜Óc gÁm phép nhân O có th∫ ˜Òc gi£i trong thÌi gian vÓi g.

2 Xây d¸ng hai danh sách:

n, h

2n, h

3n,

3 Tìm i, j th‰a mãn g i

jn.

4 V™y thì x = i + jn là mÎt nghiªm cıa g x

e, g, g 2, g 3, , g n, L1: · · · h, h , h . L2: g g g g · · · · · · · = h g · = h.

Mªnh ∑ (Thu™t toán Babystep-Giantstep) Xét nhóm G và g 2 ây gi£i bài toán logarit rÌi r§c g x

1 ∞t n = 1 +

34 / 54

G là mÎt ph¶n t˚ có cßp N = h trong 2. Thu™t toán sau log N ) b˜Óc. (pN O · pN , cˆ th∫ n > pN . b c

3 Tìm i, j th‰a mãn g i

jn.

4 V™y thì x = i + jn là mÎt nghiªm cıa g x

= h g · = h.

Mªnh ∑ (Thu™t toán Babystep-Giantstep) Xét nhóm G và g 2 ây gi£i bài toán logarit rÌi r§c g x

1 ∞t n = 1 + 2 Xây d¸ng hai danh sách:

G là mÎt ph¶n t˚ có cßp N = h trong 2. Thu™t toán sau log N ) b˜Óc. (pN O · pN , cˆ th∫ n > pN . b c

3n,

34 / 54

, g n, 2n, h , h . L1: L2: e, g, g 2, g 3, n, h g h, h · · · g g g · · · · · · ·

4 V™y thì x = i + jn là mÎt nghiªm cıa g x

= h.

Mªnh ∑ (Thu™t toán Babystep-Giantstep) Xét nhóm G và g 2 ây gi£i bài toán logarit rÌi r§c g x

1 ∞t n = 1 + 2 Xây d¸ng hai danh sách:

3n,

G là mÎt ph¶n t˚ có cßp N = h trong 2. Thu™t toán sau log N ) b˜Óc. (pN O · pN , cˆ th∫ n > pN . b c

34 / 54

, h . L1: L2: g g · · · · · e, g, g 2, g 3, n, h g h, h 3 Tìm i, j th‰a mãn g i · jn. · · · g · = h , g n, 2n, h g ·

Mªnh ∑ (Thu™t toán Babystep-Giantstep) Xét nhóm G và g 2 ây gi£i bài toán logarit rÌi r§c g x

1 ∞t n = 1 + 2 Xây d¸ng hai danh sách:

3n,

G là mÎt ph¶n t˚ có cßp N = h trong 2. Thu™t toán sau log N ) b˜Óc. (pN O · pN , cˆ th∫ n > pN . b c

34 / 54

, h . L1: L2: g g · · · · · · jn. · · · g · = h , g n, 2n, h g · e, g, g 2, g 3, n, h g h, h 3 Tìm i, j th‰a mãn g i 4 V™y thì x = i + jn là mÎt nghiªm cıa g x = h.

Thu™t toán Babystep-Giantstep (chi ti∏t)

G; cßp N cıa g. • 2 Input: Các ph¶n t˚ g, h Output: x = logg (h). •

pN c

n = 1 + b for i = 0 to n : Tính gi = g i

g //Dùng tìm ki∏m nh‡ phân

35 / 54

S≠p x∏p các c∞p (i, gi) theo giá tr‡ gi for j = 0 to n : Tính h j = h · if h j == gi vÓi i nào ó : return x = i + jn return "không tÁn t§i x"

Lßy g = 2 và h = 17. • Ta có n = 6. • Ta ã tính các lÙy th¯a g i nh˜ b£ng d˜Ói ây. Hãy hoàn thành • nËt b£ng và tìm log2(17):

i 0 1 2 3 4 5 6 g i 1 2 4 8 16 3 6 h g ·

= 5. bi∏t r¨ng 2

Bài t™p

36 / 54

1 = 28. Xét nhóm F⇤29 có cßp N = 29 •

Ta có n = 6. • Ta ã tính các lÙy th¯a g i nh˜ b£ng d˜Ói ây. Hãy hoàn thành • nËt b£ng và tìm log2(17):

i 0 1 2 3 4 5 6 g i 1 2 4 8 16 3 6 h g ·

= 5. bi∏t r¨ng 2

Bài t™p

36 / 54

1 = 28. • Xét nhóm F⇤29 có cßp N = 29 Lßy g = 2 và h = 17. •

Ta ã tính các lÙy th¯a g i nh˜ b£ng d˜Ói ây. Hãy hoàn thành • nËt b£ng và tìm log2(17):

i 0 1 2 3 4 5 6 g i 1 2 4 8 16 3 6 h g ·

= 5. bi∏t r¨ng 2

Bài t™p

1 = 28. •

36 / 54

• Xét nhóm F⇤29 có cßp N = 29 Lßy g = 2 và h = 17. Ta có n = 6. •

Bài t™p

1 = 28. •

•

• Xét nhóm F⇤29 có cßp N = 29 Lßy g = 2 và h = 17. Ta có n = 6. Ta ã tính các lÙy th¯a g i nh˜ b£ng d˜Ói ây. Hãy hoàn thành nËt b£ng và tìm log2(17):

4 5 6 0 1 2 3 1 2 4 8 16 3 6 h i g i g

36 / 54

· = 5. bi∏t r¨ng 2

SË này chia 3 d˜ 2. • SË này chia 5 d˜ 3. • SË này chia 7 d˜ 2. • H‰i có bao nhiêu v™t ? •

Bài toán

37 / 54

Có mÎt sË v™t ta ch˜a bi∏t sË l˜Òng bao nhiêu. •

SË này chia 5 d˜ 3. • SË này chia 7 d˜ 2. • H‰i có bao nhiêu v™t ? •

Bài toán

37 / 54

Có mÎt sË v™t ta ch˜a bi∏t sË l˜Òng bao nhiêu. • SË này chia 3 d˜ 2. •

SË này chia 7 d˜ 2. • H‰i có bao nhiêu v™t ? •

Bài toán

37 / 54

Có mÎt sË v™t ta ch˜a bi∏t sË l˜Òng bao nhiêu. • SË này chia 3 d˜ 2. • SË này chia 5 d˜ 3. •

H‰i có bao nhiêu v™t ? •

Bài toán

37 / 54

Có mÎt sË v™t ta ch˜a bi∏t sË l˜Òng bao nhiêu. • SË này chia 3 d˜ 2. • SË này chia 5 d˜ 3. • SË này chia 7 d˜ 2. •

Bài toán

37 / 54

Có mÎt sË v™t ta ch˜a bi∏t sË l˜Òng bao nhiêu. • SË này chia 3 d˜ 2. • SË này chia 5 d˜ 3. • SË này chia 7 d˜ 2. • H‰i có bao nhiêu v™t ? •

Ví dˆ Tìm sË nguyên x th‰a mãn Áng thÌi c£ hai ph˜Ïng trình

x và x 1 (mod 5) 9 (mod 11). ⌘ ⌘ Nghiªm cıa ph˜Ïng trình th˘ nhßt là t™p các sË nguyên

y x = 1 + 5 y, Z. 2 Th∏ vào ph˜Ïng trình th˘ hai, ta ˜Òc

5 y 1 + 5 y 9 (mod 11) 8 (mod 11) ⌘

⌘ , 9 (mod 11). Ta ˜Òc Nhân c£ hai v∏ vÓi 5

⌘ 9 y 8 72 6 (mod 11) ⌘ ⌘ ⌘

38 / 54

· Thay l§i vào ph˜Ïng trình ¶u ta ˜Òc x = 1 + 5 6 = 31. ·

‡nh l˛ (‡nh l˛ ph¶n d˜ Trung Hoa) Xét m1, m2, . . . , mk là các sË ôi mÎt nguyên tË cùng nhau. Xét các sË nguyên a1, a2, . . . , ak bßt k˝. Khi ó hª ph˜Ïng trình

x x , x a1 a2 ak (mod m1), (mod m2), (mod mk) ⌘ ⌘ · · · ⌘

39 / 54

có mÎt nghiªm x = c. HÏn n˙a, n∏u x = c và x = c0 là hai nghiªm cıa hª, v™y thì c (mod m1m2 . . . mk). c0 ⌘

Dùng mÎt nghiªm x = 2 cıa ph˜Ïng trình ¶u ∫ tìm nghiªm • th‰a mãn c£ hai ph˜Ïng trình ¶u tiên. Ta ˜Òc x = 17. Dùng nghiªm này ∫ tìm nghiªm th‰a mãn c£ ba ph˜Ïng trình. • Ta ˜Òc x = 164.

Ví dˆ

40 / 54

Xét hª ba ph˜Ïng trình sau ây • x x x 2 (mod 3), 3 (mod 7), 4 (mod 16). ⌘ ⌘ ⌘

Dùng nghiªm này ∫ tìm nghiªm th‰a mãn c£ ba ph˜Ïng trình. • Ta ˜Òc x = 164.

Ví dˆ

Xét hª ba ph˜Ïng trình sau ây • x x x 2 (mod 3), 3 (mod 7), 4 (mod 16). ⌘ ⌘ ⌘

40 / 54

• Dùng mÎt nghiªm x = 2 cıa ph˜Ïng trình ¶u ∫ tìm nghiªm th‰a mãn c£ hai ph˜Ïng trình ¶u tiên. Ta ˜Òc x = 17.

Ví dˆ

Xét hª ba ph˜Ïng trình sau ây • x x x 2 (mod 3), 3 (mod 7), 4 (mod 16). ⌘ ⌘ ⌘

•

40 / 54

• Dùng mÎt nghiªm x = 2 cıa ph˜Ïng trình ¶u ∫ tìm nghiªm th‰a mãn c£ hai ph˜Ïng trình ¶u tiên. Ta ˜Òc x = 17. Dùng nghiªm này ∫ tìm nghiªm th‰a mãn c£ ba ph˜Ïng trình. Ta ˜Òc x = 164.

Công th˘c nghiªm

•

Xét m1, m2, . . . , mk là các sË ôi mÎt nguyên tË cùng nhau. Xét các sË nguyên a1, a2, . . . , ak bßt k˝. Khi ó hª ph˜Ïng trình • x , x a1 ak (mod m1), (mod mk) ⌘ · · · ⌘ có nghiªm duy nhßt

i=1 X

ai bi M /mi x =

41 / 54

(mod mi). trong ó: M = m1 . . . mk và bi = (M /mi)

Øng cßu gi˙a Zpq và Zp

Zq

⇥

Ta có th∫ bi∫u diπn mÎt ph¶n t˚ cıa Zpq bi mÎt ph¶n t˚ cıa Zp và mÎt ph¶n t˚ cıa Zq, và ng˜Òc l§i.

Zpq t˜Ïng ˘ng vÓi (a, b), (c, d) Zq. Khi Zp 2 2 ⇥ HÏn n˙a, n∏u x, y ó

! x + y x y (a + c, b + d) (ac, bd) !

Ví dˆ Ta có th∫ vi∏t:

42 / 54

17 Z35 Z5 Z7 2 ! ⇥ 2 2 Z35 Z5 Z7 2 ! ⇥ 2 2 17 (2, 3) (2, 2) (4, 6) Z35 Z5 Z7 ⇥ 2 ! ⇥ 2

Câu h‰i

Bài t™p C∞p sË (3, 5)

43 / 54

Z5 Z7 t˜Ïng ˘ng vÓi sË gì trong Z35? 2 ⇥

Ÿng dˆng th¸c t∏

44 / 54

Zpq (ví dˆ: k˛ Zq và Zp 2 2 ⇥ N∏u ta c¶n th¸c hiªn nhi∑u tính toán trên giá tr‡ x ho∞c gi£i mã RSA), thì ta có th∫ chuy∫n x v∑ (a, b) th¸c hiªn các tính toán trên (a, b).

3 (mod 4). Xét a là sË ⌘ a (mod p) có nghiªm, t˘c là a có c´n b™c hai. ⌘

Mªnh ∑ Xét p là mÎt sË nguyên tË th‰a mãn p nguyên sao cho x 2 V™y thì

45 / 54

b a(p+1)/4 (mod p) ⌘ là mÎt nghiªm; nó th‰a mãn b2 a (mod p). ⌘

Ví dˆ MÎt c´n b™c hai cıa a = 2201 trong modun nguyên tË p = 4127 là

b a(p+1)/4 = 22014128/4 = 22011032 3718 (mod 4127). ⌘ ⌘

46 / 54

Ta có th∫ ki∫m tra xem a có c´n b™c hai không b¨ng cách bình ph˜Ïng b lên.

tính c´n trong modun th¯a sË nguyên tË này, • k∏t hÒp lÌi gi£i dùng ‡nh l˛ ph¶n d˜ Trung Hoa. •

C´n trong modun m không nguyên tË

47 / 54

Phân tích sË m thành các th¯a sË nguyên tË, •

k∏t hÒp lÌi gi£i dùng ‡nh l˛ ph¶n d˜ Trung Hoa. •

C´n trong modun m không nguyên tË

47 / 54

Phân tích sË m thành các th¯a sË nguyên tË, • tính c´n trong modun th¯a sË nguyên tË này, •

C´n trong modun m không nguyên tË

47 / 54

Phân tích sË m thành các th¯a sË nguyên tË, • tính c´n trong modun th¯a sË nguyên tË này, • k∏t hÒp lÌi gi£i dùng ‡nh l˛ ph¶n d˜ Trung Hoa. •

Gi£i hai ph˜Ïng trình trên ta ˜Òc y 8 và z (mod 23). • ⌘ ⌥ ⌘ ⌥ ChÂn hai nghiªm nguyên d˜Ïng ta ˜Òc • x và x 8 (mod 19) 6 (mod 23). ⌘ ⌘ CuËi cùng, ta ˜Òc x 236 (mod 437). • ⌘

Ví dˆ

∫ tìm nghiªm cıa ph˜Ïng trình • x 2 197 (mod 437).

48 / 54

⌘ 23. • · Phân tích 437 = 19 Gi£i hai ph˜Ïng trình • y 2 197 và z2 197 7 (mod 19) 13 (mod 23) ⌘ ⌘ ⌘ ⌘

ChÂn hai nghiªm nguyên d˜Ïng ta ˜Òc • x và x 8 (mod 19) 6 (mod 23). ⌘ ⌘ CuËi cùng, ta ˜Òc x 236 (mod 437). • ⌘

Ví dˆ

∫ tìm nghiªm cıa ph˜Ïng trình • x 2 197 (mod 437).

48 / 54

⌘ 23. • · Phân tích 437 = 19 Gi£i hai ph˜Ïng trình • y 2 197 và z2 197 7 (mod 19) 13 (mod 23) ⌘ ⌘ ⌘ Gi£i hai ph˜Ïng trình trên ta ˜Òc y ⌘ 8 và z (mod 23). • ⌘ ⌥ ⌘ ⌥

CuËi cùng, ta ˜Òc x 236 (mod 437). • ⌘

Ví dˆ

∫ tìm nghiªm cıa ph˜Ïng trình • x 2 197 (mod 437).

48 / 54

⌘ 23. • · Phân tích 437 = 19 Gi£i hai ph˜Ïng trình • y 2 197 và z2 197 7 (mod 19) 13 (mod 23) ⌘ ⌘ ⌘ Gi£i hai ph˜Ïng trình trên ta ˜Òc y ⌘ 8 và z (mod 23). • ⌘ ⌥ ⌘ ⌥ ChÂn hai nghiªm nguyên d˜Ïng ta ˜Òc • x và x 8 (mod 19) 6 (mod 23). ⌘ ⌘

Ví dˆ

∫ tìm nghiªm cıa ph˜Ïng trình • x 2 197 (mod 437).

48 / 54

⌘ CuËi cùng, ta ˜Òc x ⌘ 236 (mod 437). • ⌘

Trong bài toán logarit rÌi r§c ta c¶n gi£i • g x h (mod p) ⌘ vÓi x Z/(p 1)Z. 2 Phân tích th¯a sË nguyên tË cıa p 1 có th∫ giúp tìm x nhanh • hÏn?

ﬁ t˜ng

m3 m2 • · · · · ·

49 / 54

T¯ phân tích th¯a sË nguyên tË cıa m = m1 mt , ta có th∫ dùng ‡nh l˛ ph¶n d˜ Trung Hoa ∫ gi£i ph˜Ïng trình theo modun m b¨ng cách gi£i các ph˜Ïng trình theo modun mi.

Phân tích th¯a sË nguyên tË cıa p 1 có th∫ giúp tìm x nhanh • hÏn?

ﬁ t˜ng

m3 m2 • · · · · ·

49 / 54

T¯ phân tích th¯a sË nguyên tË cıa m = m1 mt , ta có th∫ dùng ‡nh l˛ ph¶n d˜ Trung Hoa ∫ gi£i ph˜Ïng trình theo modun m b¨ng cách gi£i các ph˜Ïng trình theo modun mi. Trong bài toán logarit rÌi r§c ta c¶n gi£i • g x h (mod p) ⌘ vÓi x Z/(p 1)Z. 2

ﬁ t˜ng

m3 m2 • · · · · ·

49 / 54

‡nh l˛ Xét G là mÎt nhóm và gi£ s˚ có thu™t toán ∫ gi£i bài toán logarit rÌi r§c cho mÂi ph¶n t˚ có cßp là lÙy th¯a cıa mÎt sË nguyên tË. Cˆ th∫, n∏u g có cßp qe và ta có th∫ gi£i g x

= h trong (Sqe ) b˜Óc. O G là mÎt ph¶n t˚ có cßp N , và gi£ s˚ N phân tích 2 Bây giÌ, xét g ˜Òc thành tích các th¯a sË nguyên tË

qet t . N = qe1 qe2 2 · · · · Khi ó, bài toán logarit rÌi r§c g x = h có th∫ gi£i trong

i + log N

i=1 X

. Sq O Ç å

50 / 54

dùng thu™t toán Pohlig-Hellman.

Thu™t toán Pohlig-Hellman

1 VÓi mÈi 1

ei i

i , v™y

i t. Xét  và  gi = g N /q hi = hN /q

Chú ˛ r¨ng gi có cßp là lÙy th¯a cıa mÎt sË nguyên tË qei thì ta dùng thu™t toán ã bi∏t ∫ gi£i ph˜Ïng trình.

g y i = hi.

2 Dùng ‡nh l˛ ph¶n d˜ Trung Hoa ∫ gi£i hª ph˜Ïng trình

GÂi y = yi là nghiªm.

x ⌘ x y1 y2 (mod qe1 1 ), (mod qe2 2 ), ⌘

t ).

51 / 54

· · · x yt (mod qet ⌘

vÓi g = 3 và h = 26 = g x . • Ta có • g 30/5 16x = h30/5 (36 ) = 266 = 1 ) ) g 30/3 25x = h30/3 (310 ) = 2610 = 5 ) ) g 30/2 30x = h30/2 (315 ) = 2615 = 30 ) ) Các ph˜Ïng trình trên ∑u theo modun 31.

Ví dˆ

52 / 54

Xét bài toán tính logarit rÌi r§c trong nhóm F⇤31 có cßp • p 3 2 1 = 30 = 5 · ·

Ta có • g 30/5 16x = h30/5 (36 ) = 266 = 1 ) ) g 30/3 25x = h30/3 (310 ) = 2610 = 5 ) ) g 30/2 30x = h30/2 (315 ) = 2615 = 30 ) ) Các ph˜Ïng trình trên ∑u theo modun 31.

Ví dˆ

Xét bài toán tính logarit rÌi r§c trong nhóm F⇤31 có cßp • p 3 2 1 = 30 = 5 · ·

52 / 54

vÓi g = 3 và h = 26 = g x . •

Ví dˆ

Xét bài toán tính logarit rÌi r§c trong nhóm F⇤31 có cßp • p 3 2 1 = 30 = 5 · ·

52 / 54

• vÓi g = 3 và h = 26 = g x . Ta có • 16x = 1 ) ) ) ) ) g 30/5 g 30/3 g 30/2 25x 30x = h30/5 = h30/3 = h30/2 (36 ) (310 (315 ) = 266 = 2610 = 2615 = 5 = 30 ) ) Các ph˜Ïng trình trên ∑u theo modun 31.

Ví dˆ (ti∏p) Gi£i mÈi ph˜Ïng trình ta ˜Òc hª

x ⌘ x ⌘ x 0 (mod 5) 2 (mod 3) 1 (mod 2) ⌘ Gi£i hª này ta ˜Òc x 5 (mod 30). ⌘ ây chính là nghiªm cıa bài toán logarit. Th™t v™y

53 / 54

35 26 (mod 31). ⌘

54 / 54

M™t mã ˘ng dˆng Bài toán phân tích th¯a sË nguyên tË

1 / 48

Tài liªu tham kh£o

•

J. Hoffstein, J. Pipher, J. H. Silverman, An Introduction to Mathematical Cryptography, Springer-Verlag – Undergraduate Texts in Mathematics, 2nd Ed., 2014.

•

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press. 2009.

2 / 48

• H. H. Khoái, P. H. i∫n, SË hÂc thu™t toán: cÏ s l˛ thuy∏t và tính toán th¸c hành, NXB §i hÂc QuËc gia Hà NÎi, 2003.

Liªu công th˘c trên còn úng khi m là hÒp sË ? • Cˆ th∫, công th˘c trên có úng khi m = pq ? •

‡nh l˛ Fermat khi modun là hÒp sË

3 / 48

N∏u m là sË nguyên tË, thì • am vÓi mÂi a 1 (mod m) 0 (mod m). ⌘ 6⌘

Cˆ th∫, công th˘c trên có úng khi m = pq ? •

‡nh l˛ Fermat khi modun là hÒp sË

3 / 48

N∏u m là sË nguyên tË, thì • am vÓi mÂi a 1 (mod m) 0 (mod m). ⌘ 6⌘ Liªu công th˘c trên còn úng khi m là hÒp sË ? •

‡nh l˛ Fermat khi modun là hÒp sË

N∏u m là sË nguyên tË, thì • am vÓi mÂi a 1 (mod m) 0 (mod m). ⌘ 6⌘

3 / 48

• Liªu công th˘c trên còn úng khi m là hÒp sË ? Cˆ th∫, công th˘c trên có úng khi m = pq ? •

VÓi modun 15, t§i sao sË mÙ l§i là 4 ? •

Ví dˆ

a 1 2 3 4 5 a4 6 7 8 9 10 11 12 13 14 1 6 1 1 (mod 15) 1 1 6 1 10 6 1 1 6 10

4 / 48

• ‡nh l˛ Fermat có th∫ m rÎng khi sË a và modun m nguyên tË cùng nhau ?

Ví dˆ

a 1 2 3 4 5 a4 6 7 8 9 10 11 12 13 14 1 1 6 1 (mod 15) 1 1 6 1 10 6 1 1 6 10

• ‡nh l˛ Fermat có th∫ m rÎng khi sË a và modun m nguyên tË cùng nhau ?

4 / 48

VÓi modun 15, t§i sao sË mÙ l§i là 4 ? •

‡nh l˛ (Công th˘c Euler cho pq) Xét p và q là hai sË nguyên tË phân biªt và xét

1)(q

1)/g

1, q g = gcd(p 1). Khi ó

1)(q

1)/2

a(p 1 (mod pq) vÓi mÂi a th‰a mãn gcd(a, pq) = 1. ⌘ ∞c biªt, n∏u p, q là các sË nguyên tË l¥, v™y thì

5 / 48

a(p 1 (mod pq) vÓi mÂi a th‰a mãn gcd(a, pq) = 1. ⌘

Diffie-Hellman và RSA

• Giao th˘c Diffie-Hellman d¸a trên tính khó gi£i cıa ph˜Ïng trình a x b (mod p). ⌘ Hª m™t mã RSA d¸a trên tính khó gi£i cıa ph˜Ïng trình • x e c (mod N ). ⌘

6 / 48

Nói cách khác, nó d¸a trên tính khó cıa bài toán tính c´n b™c e theo modun N .

Mªnh ∑ Xét sË nguyên tË p; xét sË nguyên e

1 th‰a mãn

gcd(e, p 1) = 1 và xét d là ngh‡ch £o cıa e theo modun p 1, t˘c là

de 1 (mod p 1). ⌘ Khi ó ph˜Ïng trình x e c (mod p)

7 / 48

cd có nghiªm duy nhßt x ⌘ (mod p). ⌘

Ví dˆ Hãy gi£i ph˜Ïng trình

8 / 48

x 1583 4714 (mod 7919). ⌘

1 th‰a

Mªnh ∑ Xét hai sË nguyên tË phân biªt p và q; và xét sË nguyên e mãn

gcd(e, (p 1)(q 1)) = 1, và xét d là ngh‡ch £o cıa e theo modun (p 1)(q 1), t˘c là de 1 (mod (p 1)(q 1)). ⌘ Khi ó ph˜Ïng trình x e c (mod pq)

9 / 48

có nghiªm duy nhßt x cd ⌘ (mod pq). ⌘

C£i ti∏n thu™t toán

1)(q

1)/g

1, q Xét g = gcd(p 1) và gi£ s˚ ta ã gi£i ph˜Ïng trình de 1 (mod (p 1)(q 1)/g). ⌘ Công th˘c Euler nói r¨ng

a(p 1 (mod pq). ⌘ Ta vi∏t 1) de = 1 + k (p 1)(q g

1)(q

1)/g

V™y thì

1)(q

1)/g

(cd ) = cde

= c1+k(p c(p = c = c (mod pq)

10 / 48

Ví dˆ Hãy gi£i ph˜Ïng trình sau

11 / 48

x 17389 43927 (mod 64349). ⌘

Ví dˆ (Th˚ thách) Alice Ë Eve gi£i ph˜Ïng trình

x 9843 134872 (mod 30069476293) ⌘

Nh™n xét Modun 30069476293 không nguyên tË bi vì

12 / 48

230069476293 18152503626 1 (mod 30069476293). ⌘ 6⌘

Bài toán. Gi£i ph˜Ïng trình x e c (mod N ) vÓi bi∏n là x. • ⌘ Dπ. Bob bi∏t giá tr‡ p và q nên có th∫ dπ dàng gi£i ph˜Ïng • trình ∫ tìm x.

Khó. Eve không bi∏t giá tr‡ p và q nên không th∫ gi£i ph˜Ïng • trình ∫ tìm x.

S¸ khác biªt. Ph˜Ïng trình x e c (mod N ) có th∫ gi£i mÎt • ⌘ cách dπ dàng vÓi ng˜Ìi có thông tin thêm, nh˜ng khó vÓi ng˜Ìi không có.

Tính an toàn cıa RSA

13 / 48

• Cài ∞t. Xét hai sË nguyên tË p và q, tính N = pq, các sË nguyên e và c.

Dπ. Bob bi∏t giá tr‡ p và q nên có th∫ dπ dàng gi£i ph˜Ïng • trình ∫ tìm x.

Khó. Eve không bi∏t giá tr‡ p và q nên không th∫ gi£i ph˜Ïng • trình ∫ tìm x.

S¸ khác biªt. Ph˜Ïng trình x e c (mod N ) có th∫ gi£i mÎt • ⌘ cách dπ dàng vÓi ng˜Ìi có thông tin thêm, nh˜ng khó vÓi ng˜Ìi không có.

Tính an toàn cıa RSA

•

13 / 48

Cài ∞t. Xét hai sË nguyên tË p và q, tính N = pq, các sË nguyên e và c. Bài toán. Gi£i ph˜Ïng trình x e c (mod N ) vÓi bi∏n là x. • ⌘

Khó. Eve không bi∏t giá tr‡ p và q nên không th∫ gi£i ph˜Ïng • trình ∫ tìm x.

S¸ khác biªt. Ph˜Ïng trình x e c (mod N ) có th∫ gi£i mÎt • ⌘ cách dπ dàng vÓi ng˜Ìi có thông tin thêm, nh˜ng khó vÓi ng˜Ìi không có.

Tính an toàn cıa RSA

•

• ⌘

13 / 48

• Cài ∞t. Xét hai sË nguyên tË p và q, tính N = pq, các sË nguyên e và c. Bài toán. Gi£i ph˜Ïng trình x e c (mod N ) vÓi bi∏n là x. Dπ. Bob bi∏t giá tr‡ p và q nên có th∫ dπ dàng gi£i ph˜Ïng trình ∫ tìm x.

S¸ khác biªt. Ph˜Ïng trình x e c (mod N ) có th∫ gi£i mÎt • ⌘ cách dπ dàng vÓi ng˜Ìi có thông tin thêm, nh˜ng khó vÓi ng˜Ìi không có.

Tính an toàn cıa RSA

•

• ⌘

13 / 48

• Khó. Eve không bi∏t giá tr‡ p và q nên không th∫ gi£i ph˜Ïng trình ∫ tìm x.

Tính an toàn cıa RSA

•

• ⌘

•

c (mod N ) có th∫ gi£i mÎt • ⌘

13 / 48

Khó. Eve không bi∏t giá tr‡ p và q nên không th∫ gi£i ph˜Ïng trình ∫ tìm x. S¸ khác biªt. Ph˜Ïng trình x e cách dπ dàng vÓi ng˜Ìi có thông tin thêm, nh˜ng khó vÓi ng˜Ìi không có.

Hª mã RSA

Bob Alice

Sinh khóa

ChÂn hai sË nguyên tË p và q. ChÂn sË mÙ e th‰a mãn

gcd(e, (p 1)(q 1)) = 1. Công khai N = pq và e. Mã hóa

Bob ∫ tính c me ChÂn thông iªp m. Dùng khóa công khai (N , e) cıa (mod N ). ⌘ G˚i b£n mã c cho Bob. Gi£i mã

14 / 48

ed Tính d th‰a mãn 1 (mod (p 1)(q 1)). ⌘ Tính m = cd (mod N ).

Hãy mã hóa và gi£i mã thông iªp •

m = 1070777.

Ví dˆ

• T§o khóa: Bob chÂn hai sË nguyên tË bí m™t p = 1223 và q = 1987. Bob tính modun công khai

N = p q = 1223 1987 = 2430101. ·

15 / 48

· Bob chÂn sË mÙ không khai e = 948047.

Ví dˆ

• T§o khóa: Bob chÂn hai sË nguyên tË bí m™t p = 1223 và q = 1987. Bob tính modun công khai

N = p q = 1223 1987 = 2430101. ·

· Bob chÂn sË mÙ không khai e = 948047. Hãy mã hóa và gi£i mã thông iªp •

15 / 48

m = 1070777.

N∏u ch‡ ta bi∏t tÍng p + q, v™y thì t¯ Øng th˘c •

(p 1)(q 1) = N (p + q) + 1

1). ch‡ ta có th∫ tính ˜Òc (p 1)(q Th¸c ra, n∏u Eve bi∏t p + q và pq, v™y thì ch‡ ta có th∫ tính • ˜Òc p, q dπ dàng. Ch‡ ta chø c¶n tìm nghiªm cıa a th˘c

X 2 (p + q)X + pq.

a th˘c trên này có th∫ phân tích thành (X p)(X q), nên nó có nghiªm p và q.

Chú ˛

16 / 48

1)(q 1), ch‡ ta có th∫ gi£i ˜Òc ph˜Ïng • N∏u Eve bi∏t tích (p trình x e c (mod N ). ⌘

Th¸c ra, n∏u Eve bi∏t p + q và pq, v™y thì ch‡ ta có th∫ tính • ˜Òc p, q dπ dàng. Ch‡ ta chø c¶n tìm nghiªm cıa a th˘c

X 2 (p + q)X + pq.

a th˘c trên này có th∫ phân tích thành (X p)(X q), nên nó có nghiªm p và q.

Chú ˛

1)(q 1), ch‡ ta có th∫ gi£i ˜Òc ph˜Ïng • c (mod N ). ⌘ N∏u Eve bi∏t tích (p trình x e N∏u ch‡ ta bi∏t tÍng p + q, v™y thì t¯ Øng th˘c •

(p 1)(q 1) = N (p + q) + 1

16 / 48

ch‡ ta có th∫ tính ˜Òc (p 1). 1)(q

Chú ˛

1)(q 1), ch‡ ta có th∫ gi£i ˜Òc ph˜Ïng • c (mod N ). ⌘ N∏u Eve bi∏t tích (p trình x e N∏u ch‡ ta bi∏t tÍng p + q, v™y thì t¯ Øng th˘c •

(p 1)(q 1) = N (p + q) + 1

1).

• ch‡ ta có th∫ tính ˜Òc (p 1)(q Th¸c ra, n∏u Eve bi∏t p + q và pq, v™y thì ch‡ ta có th∫ tính ˜Òc p, q dπ dàng. Ch‡ ta chø c¶n tìm nghiªm cıa a th˘c

X 2 (p + q)X + pq.

16 / 48

p)(X q), nên nó a th˘c trên này có th∫ phân tích thành (X có nghiªm p và q.

Ví dˆ Gi£ s˚ Eve bi∏t r¨ng

và

17 / 48

N = pq = 66240912547 1) = 66240396760. 1)(q (p Hãy phân tích th¯a sË nguyên tË cho N .

Th¸c ra Eve không nhßt thi∏t ph£i phân tích th¯a sË cıa N , ch‡ • ta chø c¶n gi£i ph˜Ïng trình

x e c (mod N ). ⌘ Cho tÓi nay, ng˜Ìi ta v®n ch˜a bi∏t ph˜Ïng pháp nào gi£i • ph˜Ïng trình này khi không bi∏t giá tr‡ (p 1)(q 1).

Chú ˛

18 / 48

1)(q 1) không dπ hÏn phân tích th¯a sË • Ta bi∏t r¨ng tìm (p nguyên tË cıa N = pq. T§i sao?

Cho tÓi nay, ng˜Ìi ta v®n ch˜a bi∏t ph˜Ïng pháp nào gi£i • ph˜Ïng trình này khi không bi∏t giá tr‡ (p 1)(q 1).

Chú ˛

1)(q 1) không dπ hÏn phân tích th¯a sË •

• Ta bi∏t r¨ng tìm (p nguyên tË cıa N = pq. T§i sao? Th¸c ra Eve không nhßt thi∏t ph£i phân tích th¯a sË cıa N , ch‡ ta chø c¶n gi£i ph˜Ïng trình

18 / 48

x e c (mod N ). ⌘

Chú ˛

1)(q 1) không dπ hÏn phân tích th¯a sË •

• Ta bi∏t r¨ng tìm (p nguyên tË cıa N = pq. T§i sao? Th¸c ra Eve không nhßt thi∏t ph£i phân tích th¯a sË cıa N , ch‡ ta chø c¶n gi£i ph˜Ïng trình

x e c (mod N ). ⌘

18 / 48

• Cho tÓi nay, ng˜Ìi ta v®n ch˜a bi∏t ph˜Ïng pháp nào gi£i ph˜Ïng trình này khi không bi∏t giá tr‡ (p 1)(q 1).

V™y thì ta c¶n mÎt thı tˆc ∫ ki∫m tra mÎt sË có là nguyên tË. •

Sinh sË nguyên tË lÓn

• Trong b˜Óc sinh khóa RSA, Bob c¶n chÂn hai sË nguyên tË lÓn p và q. Làm th∏ nào có th∫ chÂn ng®u nhiên sË nguyên tË lÓn?

19 / 48

• MÎt cách Ïn gi£n là chÂn ng®u nhiên ∏n khi ˜Òc sË nguyên tË.

Sinh sË nguyên tË lÓn

• Trong b˜Óc sinh khóa RSA, Bob c¶n chÂn hai sË nguyên tË lÓn p và q. Làm th∏ nào có th∫ chÂn ng®u nhiên sË nguyên tË lÓn?

• MÎt cách Ïn gi£n là chÂn ng®u nhiên ∏n khi ˜Òc sË nguyên tË.

19 / 48

V™y thì ta c¶n mÎt thı tˆc ∫ ki∫m tra mÎt sË có là nguyên tË. •

825154968537631912768298749170739297854398716362661816275503116079 481244776851676369506181060016953565332332544104243302099970453768 573552526611491950457625797020175677070075982187142166723199505455 790940666545512029823115363737022514932296310461843759943426637450 457978700698013163674793031149391910570974516004314717775131667097 126098742572843325657395082030947465507253903496576780657530224681 101778363387269042871961460357674470219471788386403599087114004172 622229372209083170147380517906145636406605403890844426358143534126 759193985336262167688110337743953182116252070586929061201355598602 898620963724847193471057235471237921703384265217076231273197853548 551705842298080177124144337311712909603561659196347298251868740384 298808360296925212361003693208144299852907112109370230400750357870 997794622389754516766792389806834086164756749904260739674386541960 302825628178473942663151037197890442447506340719073733827930075184 694843829985334125752222656014432200550207371044791552615829608023 729568421318530916220310811657584027558305745037362938267941655342 687150141185981390338210844918719377398248258106753462919520441851 026786481875648951265795109384767346853898863411878053416947898154 479434332215017695703979981056520395957368803

20 / 48

Ví dˆ

SË sau ây có là nguyên tË không? •

n = 31987937737479355332620068643713101490952335301

Không vì •

21 / 48

2n 1281265953551359064133601216247151836053160074 (mod n).

‡nh l˛ (‡nh l˛ Fermat nh‰, Version 2) Xét sË nguyên tË p. Khi ó

22 / 48

ap vÓi mÂi sË nguyên a. a (mod p) ⌘

Thu™t toán TestFermat(n, a) :

1 if (an

23 / 48

a mod n) return “HÒp sË”; 6⌘ else return “Nguyên tË”.

SË này có ph£i là sË nguyên tË? • Nh˙ng sË này ˜Òc gÂi là sË Carmichael. • M∞c dù các sË Carmichael rßt hi∏m, Alford, Granville, và • Pomerance ã ch˘ng minh vào n´m 1994 r¨ng có vô h§n sË nh˜ v™y.

SË Carmichael

• N∏u sË n qua ˜Òc TestFermat vÓi nhi∑u sË a = a1, a2, a3, . . . , có v¥ r¨ng n là sË nguyên tË.

24 / 48

B§n th˚ dùng TestFermat cho sË 561 xem. •

Nh˙ng sË này ˜Òc gÂi là sË Carmichael. • M∞c dù các sË Carmichael rßt hi∏m, Alford, Granville, và • Pomerance ã ch˘ng minh vào n´m 1994 r¨ng có vô h§n sË nh˜ v™y.

SË Carmichael

• N∏u sË n qua ˜Òc TestFermat vÓi nhi∑u sË a = a1, a2, a3, . . . , có v¥ r¨ng n là sË nguyên tË.

24 / 48

B§n th˚ dùng TestFermat cho sË 561 xem. • SË này có ph£i là sË nguyên tË? •

M∞c dù các sË Carmichael rßt hi∏m, Alford, Granville, và • Pomerance ã ch˘ng minh vào n´m 1994 r¨ng có vô h§n sË nh˜ v™y.

SË Carmichael

• N∏u sË n qua ˜Òc TestFermat vÓi nhi∑u sË a = a1, a2, a3, . . . , có v¥ r¨ng n là sË nguyên tË.

24 / 48

B§n th˚ dùng TestFermat cho sË 561 xem. • SË này có ph£i là sË nguyên tË? • Nh˙ng sË này ˜Òc gÂi là sË Carmichael. •

SË Carmichael

• N∏u sË n qua ˜Òc TestFermat vÓi nhi∑u sË a = a1, a2, a3, . . . , có v¥ r¨ng n là sË nguyên tË.

B§n th˚ dùng TestFermat cho sË 561 xem. • SË này có ph£i là sË nguyên tË? • Nh˙ng sË này ˜Òc gÂi là sË Carmichael. •

•

24 / 48

M∞c dù các sË Carmichael rßt hi∏m, Alford, Granville, và Pomerance ã ch˘ng minh vào n´m 1994 r¨ng có vô h§n sË nh˜ v™y.

Bài t™p Hãy vi∏t ch˜Ïng trình liªt kê các sË Carmichael

25 / 48

106. 

‡nh l˛ Xét p là sË nguyên tË l¥ và vi∏t

p vÓi q l¥. 1 = 2kq

1 aq Áng d˜ vÓi 1 theo modun p. 2 MÎt trong các sË aq, a2q, a4q, . . . , a2k

1q Áng d˜ vÓi

Xét a là sË bßt k˝ không là ˜Óc cıa p. V™y thì mÎt trong hai i∑u kiªn sau ph£i úng

26 / 48

1 theo modun p.

‡nh nghæa 1 = 2kq vÓi q l¥. MÎt sË nguyên a Xét sË nguyên l¥ n và vi∏t n th‰a mãn gcd(a, n) = 1 ˜Òc gÂi là b¨ng ch˘ng Miller-Rabin cho (tính hÒp sË) cıa n n∏u c£ hai i∑u kiªn sau ây ∑u úng:

1 aq 6⌘ 2 a2i q

1 (mod n). 1. 1 (mod n) vÓi mÂi i = 0, 1, 2, . . . , k 6⌘

27 / 48

The mªnh ∑ tr˜Óc n∏u tÁn t§i mÎt b¨ng ch˘ng Miller-Rabin a cho sË n, v™y n ch≠c ch≠n là hÒp sË.

1 = 2kq vÓi q l¥. (mod n).

1 (mod n)) return "Nguyên tË" 1 : , k · · · 1 (mod n)) return "Nguyên tË".

(mod n);

Thu™t toán Miller-Rabin (n, a) // n là sË c¶n ki∫m tra, a là sË ∫ xác th¸c tính hÒp sË cıa n 1 if (n chÆn ho∞c 1 < gcd(a, n) < n) return "HÒp sË". 2 Vi∏t n 3 Gán a := aq 4 if (a ⌘ 5 for i = 0, 1, 2, if (a 6 ⌘ Gán a := a2 8 return "HÒp sË".

28 / 48

Ví dˆ Ta mô t£ thu™t toán Miller-Rabin vÓi a = 2 và sË n = 561. Ta phân tích

n 35 1 = 560 = 24 · và tính

29 / 48

⌘ 235 35 166 ⌘ ⌘ 67 ⌘ 263 2632 1662 672 ⌘ 1 (mod 561). (mod 561). (mod 561). (mod 561). 22 · 24 · 28 · ⌘ ⌘ V™y a là mÎt b¨ng ch˘ng Miller-Rabin cho s¸ kiªn n là hÒp sË.

Ví dˆ Ta mô t£ thu™t toán Miller-Rabin cho n = 172947529. Ta phân tích

n 21618441. 1 = 172947528 = 23

· 1 (mod 172947529). V™y 17 không ph£i là ⌘ Ta tính 1721618441 b¨ng ch˘ng Miller-Rabin cho n. Ta th˚ ti∏p vÓi a = 3, nh˜ng

321618441 1 (mod 172947529). ⌘

V™y 3 cÙng không ph£i là b¨ng ch˘ng Miller-Rabin cho n. Th˚ vÓi a = 23, ta thßy

21618441

30 / 48

40063806 ⌘ 2321618441 21618441 2257065 ⌘ 1 (mod 172947529). (mod 172947529). (mod 172947529). 232 · 234 · ⌘ V™y a = 23 là mÎt b¨ng ch˘ng Miller-Rabin cho s¸ kiªn n là hÒp sË.

1 là b¨ng

Mªnh ∑ Xét n là mÎt hÒp sË. Khi ó ít nhßt 75% sË a gi˙a 1 và n ch˘ng Miller-Rabin cho n.

100

60.

N∏u ta ch§y thu™t toán Miller-Rabin vÓi 100 giá tr‡ a ng®u nhiên, và n∏u c£ 100 l¶n ch§y thu™t toán ∑u k∏t lu™n n là sË nguyên tË, v™y xác sußt n là hÒp sË chø b¨ng

31 / 48

(0.25) 10 ⇡ Liªu b§n ã ch≠c ch≠n sË n này là sË nguyên tË?

‡nh nghæa Hàm phân phËi cıa các sË nguyên tË ⇡(n) là sË l˜Òng sË nguyên tË nh‰ hÏn ho∞c b¨ng n.

Ví dˆ ⇡(10) = 4 vì có úng bËn sË nguyên tË nh‰ hÏn 10 là 2, 3, 5, 7.

32 / 48

‡nh l˛

lim n ⇡(n) n/ ln n = 1.

33 / 48

Nói cách khác, giá tr‡ ⇡(n) xßp xø b¨ng vÓi n/ ln n khi n lÓn.

Ví dˆ VÓi n = 109 ta có

và ⇡(n) = 50847534 n/ ln n = 48254942.

34 / 48

Sai sË  ây là 6%.

SË nguyên tË ng®u nhiên

V™y n∏u ta lßy ng®u nhiên mÎt sË nguyên d˜Ïng k bit, xác sußt ∫ sË này là sË nguyên tË b¨ng 1/ ln 2k. V™y v∑ trung bình, ta c¶n ln 2k l¶n th˚ ∫ lßy ˜Òc mÎt sË nguyên tË k bit.

Ví dˆ N∏u k = 3072 thì, trung bình lßy ng®u nhiên

35 / 48

ln 23072 2130 ⇡ sË, ta s≥ có ˜Òc mÎt sË nguyên tË 3072 bit.

Thu™t toán sinh sË nguyên tË

T¯ phân tích  trên, v∑ trung bình thu™t toán ng®u nhiên d˜Ói ây s≥ d¯ng sau ln 2k b˜Óc l∞p.

Thu™t toán sinh sË nguyên tË lÓn

1. ChÂn ng®u nhiên mÎt sË nh‡ phân p Î dài k bit.

2. ∞t c£ hai bit cao nhßt và bit thßp nhßt cıa p lên 1.

3. Ki∫m tra xem p có là sË nguyên tË.

4. N∏u có thì tr£ ra sË nguyên tË p. Còn n∏u không thì quay l§i

36 / 48

B˜Óc 1.

Sinh sË ng®u nhiên trên *NIX

•

Hª i∑u hành ki∫u *NIX sinh các dãy bit ng®u nhiên t¯ các nguÁn ng®u nhiên cıa hª thËng (các thao tác chuÎt, các thao tác bàn phím, các ch˜Ïng trình ch§y. . . ). Các dãy bit này ˜Òc l˜u tr˙ trong tªp tin /dev/urandom.

•

37 / 48

Trong tr˜Ìng hÒp các dãy bit sinh ra ch˜a ı ng®u nhiên do entropy nh‰, hª thËng s≥ s˚ dˆng mÎt hàm gi£ ng®u nhiên an toàn.

Carl Friedrich Gauss (1805):

38 / 48

"The problem of distin- guishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic."

Có nghæa r¨ng, có các sË i, j, và k vÓi k = 0 th‰a mãn • 6 và L = i(p 1) L = j(q 1) + k.

Ph˜Ïng pháp p

1 cıa Pollard

1 cıa Pollard cho phép ta phân tích th¯a sË • Ph˜Ïng pháp p nguyên tË cıa

N = pq

khi

39 / 48

tìm ˜Òc sË L sao cho L và L. (p 1) (q 1) | -

Ph˜Ïng pháp p

1 cıa Pollard

1 cıa Pollard cho phép ta phân tích th¯a sË • Ph˜Ïng pháp p nguyên tË cıa

N = pq

khi

39 / 48

tìm ˜Òc sË L sao cho L và L. (p 1) (q 1) | - Có nghæa r¨ng, có các sË i, j, và k vÓi k = 0 th‰a mãn • 6 và L = i(p 1) L = j(q 1) + k.

Nói cách khác • p và q (a L 1) (a L 1). | Khi ó - • p = gcd(a L 1, N ).

Ph˜Ïng pháp p

1 cıa Pollard (2)

Theo ‡nh l˛ Fermat •

1) = (a(p = ak 1)+k

1)) (a(q

40 / 48

⌘ a L a L 1 (mod p), ak1 j ak = ai(p = a j(q (mod q), 1i ⌘ j 1)) ⌘ và vì k = 0, nên g¶n nh˜ ch≠c ch≠n ak ⌘ 1 (mod q). 6⌘ 6

Khi ó • p = gcd(a L 1, N ).

Ph˜Ïng pháp p

1 cıa Pollard (2)

Theo ‡nh l˛ Fermat •

1) = (a(p = ak 1)+k

1)) (a(q

40 / 48

⌘ a L a L 1 (mod p), ak1 j ak = ai(p = a j(q (mod q), 1i ⌘ j 1)) ⌘ và vì k = 0, nên g¶n nh˜ ch≠c ch≠n ak ⌘ 1 (mod q). 6⌘ 6 Nói cách khác • p và q (a L 1) (a L 1). | -

Ph˜Ïng pháp p

1 cıa Pollard (2)

Theo ‡nh l˛ Fermat •

1) = (a(p = ak 1)+k

1)) (a(q

40 / 48

⌘ a L a L 1 (mod p), ak1 j ak = ai(p = a j(q (mod q), 1i ⌘ j 1)) ⌘ và vì k = 0, nên g¶n nh˜ ch≠c ch≠n ak ⌘ 1 (mod q). 6⌘ 6 Nói cách khác • p và q (a L 1) (a L 1). | Khi ó • p = gcd(a L - 1, N ).

ﬁ t˜ng cıa Pollard

N∏u p 1 là tích cıa nhi∑u sË nguyên tË nh‰, v™y thì nó s≥ là ˜Óc cıa n! vÓi mÎt sË n không quá lÓn.

Bài toán Tìm L th‰a mãn

41 / 48

L và L (p 1) (q 1) | khi chø bi∏t N . -

Bài toán Tìm L th‰a mãn

L và L (p 1) (q 1) | khi chø bi∏t N . -

1 là tích cıa nhi∑u sË nguyên tË nh‰, v™y thì nó s≥ là ˜Óc

ﬁ t˜ng cıa Pollard N∏u p cıa n! vÓi mÎt sË n không quá lÓn.

41 / 48

ﬁ t˜ng thu™t toán Pollard

ChÂn mÎt giá tr‡ n và mÎt giá tr‡ a và tính •

d = gcd(an! 1, N ).

•

42 / 48

• N∏u d = 1 v™y ta th˚ vÓi giá tr‡ ti∏p theo cıa n. N∏u d = N v™y ta ph£i th˚ vÓi giá tr‡ a khác. N∏u 1 < d < N v™y thì d là mÎt th¯a sË nguyên tË cıa N . •

n+1

Dùng Øng th˘c • a(n+1)! (an! ) (mod N ). ⌘

Làm th∏ nào ∫ tính gcd(an!

1, N )?

43 / 48

Ta chø c¶n tính an! (mod N ). •

Làm th∏ nào ∫ tính gcd(an!

1, N )?

n+1

43 / 48

(mod N ). • Ta chø c¶n tính an! Dùng Øng th˘c • a(n+1)! (an! ) (mod N ). ⌘

Thu™t toán p

1 cıa Pollard

Input: SË N c¶n phân tích th¯a sË nguyên tË Output: MÎt th¯a sË nguyên tË cıa N

// Ho∞c có th∫ chÂn giá tr‡ phù hÒp khác

// B là c™n xác ‡nh tr˜Óc

1. a = 2; 2. for j = 2, 3, 4, . . . , B : 3.

(mod N );

4.

1, N );

5.

44 / 48

a = a j d = gcd(a if (1 < d < N ) return d;

29! 1 13867883 (mod 13927189), gcd(29! 1, 13927189) = 1, ⌘ 210! 1 5129508 (mod 13927189), gcd(210! 1, 13927189) = 1, ⌘ 211! 1 4405233 (mod 13927189), gcd(211! 1, 13927189) = 1, ⌘ 212! 1 6680550 (mod 13927189), gcd(212! 1, 13927189) = 1, ⌘ 213! 1 6161077 (mod 13927189), gcd(213! 1, 13927189) = 1, ⌘ 214! 1 879290 (mod 13927189), gcd(214! 1, 13927189) = 3823 ⌘