Tài liệu Kỹ thuật lập trình - Chương 2: Giới thiệu lý thuyết số

CH

NG 2

ƯƠ

GI

I THI U

Ớ

Ệ V LÝ THUY T S

Ế Ố

Ề

thu t toán m t mã khóa công khai đ c xây d ng d a trên các khái ni m c a lý H u h t các ế ầ ậ ậ ượ ự ự ủ ệ

thuy t s . Trong ch ng này s trình bày ng n g n nh ng ki n th c c b n v lý thuy t s , nó là ế ố ươ ứ ơ ả ế ố ữ ẽ ế ề ắ ọ

công c h u ích đ hi u sâu m t thu t toán m t mã nào đó. ể ể ụ ữ ậ ậ ộ

cùng nhau và các s nguyên t ố ố

2.1 Các s nguyên t ố ố

2.1.1 Các c sướ ố

c s c a đây a, b, m là Nói r ngằ , b (m t s khác 0) là ộ ố ướ ố ủ a n u ế a = mb, v i m t giá tr ớ ộ ị m nào đó, ở

các s nguyên. Nh v y, c s c a a cho b không còn l i s d . Đ kí hi u ư ậ b là ố ướ ố ủ a, n u nh chia ư ế ạ ố ư ể ệ b là

ng s d ng cách vi ướ ố ủ a th c s c a ườ ử ụ ế bŒ a. t

ệ

1. Có các quan h sau: o N u ế aŒ 1, thì a = –

o N uế bŒ a và aŒ b, thì a = –

c s c a 0. S ố b b tấ kỳ khác 0 là ướ ố ủ

o o N u ế bŒ g và bŒ h, thì bŒ (mg + nh) đ i v i b t kì s nguyên

m, n. ố ớ ấ ố

Đ ể ch ng minh kh ng đ nh cu i cùng, c n chú ý nh sau: ư ứ ầ ố ẳ

g = b * g1, đ i v i s nguyên g1 nào đó, ị n u ế bŒ g thì g có d ng ạ ố ớ ố

h = b * h1, đ i v i giá tr nguyên h1 nào đó, n u ế bŒ h thì h có d ng ạ ố ớ ị

Vì v y: ậ mg + nh = mbg1 + nbh1 = b * (mg1+ nh1)

Cu i cùng, b là c s c a ố ướ ố ủ mg + nh.

: Các s 1, 2, 3, 4, 6, 8, 12 và 24 là các c s c a 24. Ví d 2.1ụ ố ướ ố ủ

: b = 7, g = 14, h = 63, m = 3, n = 2

(cid:231) (3 * 14 + 2 * 63). Ví d 2.2ụ 7(cid:231) 14 và 7(cid:231) 63. Yêu c u ch ng minh r ng 7 ầ ứ ằ

Chúng ta có: ( 3 * 14 + 2 * 63 ) = 7(3 * 2 + 2 * 9)

(cid:231) 7(3 * 2 + 2 * 9). Nh v y, rõ ư ậ ràng r ng 7 ằ

2.1.2 Các s nguyên t ố ố

– M t s nguyên p > 1 đ , n u ch có 1 và – p là c s c a nó. ộ ố ượ ọ c g i là s nguyên t ố ố ế ỉ ướ ố ủ

M t s nguyên b t kỳ a > 1 có th phân tích thành các th a s và đ c trình bày d i d ng: ộ ố ấ ừ ố ể ượ ướ ạ

a= pp 1

a 2

a tp

a ... ,

đây: , còn các giá tr p1 < p2 < … < pt là các s nguyên t ở ố ố ị a i > 0.

: 91 = 7 * 13; 11011 = 7 * 112 * 13. Ví d 2.3ụ

, thì đ i v i m t s nguyên d N u ế P là kí hi u t p h p t ệ ậ ợ ấ ả t c các s nguyên t ố ố ố ớ ộ ố ươ ng b t kì đ ấ ượ c

vi t duy nh t d i d ng: ế ấ ướ ạ

a pp

đây t ở

(cid:213)= a , t c các ap ‡ ấ ả 0

ấ ể

Trong công th c này, bi u th c v ph i sau d u b ng, ký hi u tích theo t t c ứ ở ế ứ ả ệ ằ ấ ả kh năng c a các ủ ả

s nguyên t ố ố p. Đ i v i m i giá tr c th c a ị ụ ể ủ a thì giá tr l n nh t c a ch s ố ớ ấ ủ ỉ ố ap s b ng 0 ẽ ằ ị ớ ỗ

Ví dụ 2.4: 3600 = 24 * 32 * 52.

Các giá tr c a m t s nguyên d ng b t kỳ có th li t kê d t c các ộ ố ị ủ ươ ể ệ ấ ướ i m t d ng đ n gi n c a t ơ ả ủ ấ ả ộ ạ

ch s khác không theo công th c trên. ỉ ố ứ ở

Ví d 2.5ụ : S ố nguyên 12 có th trình bày nh { ư a2 = 2, a3 = 1}. ể

S ố nguyên 18 có th trình bày nh { ư a2 = 1, a3 = 2}. ể

Phép nhân hai s nguyên t ng đ ươ ươ ng v i phép c ng các giá tr các ch s phù h p: ị ỉ ố ớ ộ ợ

ố k = m * n ﬁ t c các p. kp = mp + np, đ i v i t ố ớ ấ ả

: k = 12 * 18 = 216, Ví d 2.6ụ

k2 = 2 + 1 = 3, k3 = 1 + 2 = 3,

216 = 23 * 33

ng b t kì d ng pk ch có th chia h t cho m t s nguyên, khi s b chia B đổ ề: M t s nguyên d ộ ố ươ ạ ấ ộ ố ố ị ể ế ỉ

có b c c a s nguyên t t h n k. Nh v y: ậ ủ ố ố p v i ch s không v ỉ ố ớ ượ ơ k, nghĩa là s ố pj v i ớ j £ ư ậ

a(cid:231) b ﬁ t c ap £ bp, đ i v i t ố ớ ấ ả p.

: a = 12 , b = 36 , 12(cid:231) 36, 12 = 22 * 3, 36 = 22 * 32 Ví d 2.7ụ

a2 = 2 = b2, a3 = 1 £ 2 = b3.

2.1.3 Các s nguyên t cùng nhau ố ố

Chúng ta s s d ng ký hi u gcd( c s chung l n nh t ẽ ử ụ ệ a, b) đ ch ể ỉ ướ ố ấ (UCLN) c a s ủ ố a và b. Nói ớ

ng r ng, m t s nguyên d ộ ố ằ ươ c là UCLN c a ủ a và b, n u:ế

c là cướ s c a ố ủ a và b.

c s b t kỳ c a Ướ ố ấ ủ a và b đ u là ề ướ ố ủ c. c s c a

ng đ ươ ể ị

ng, chúng ta có gcd( a, b) = gcd(a, –b ) = gcd(–a, b) = ỏ ằ ở ộ ố ươ Có th đ nh nghĩa t ng nh sau: ươ ư gcd(a, b) = max [k, khi k(cid:231) a và k(cid:231) b]. B i vì, đòi h i r ng UCLN là m t s d

gcd(–a, –b ). Nói chung, gcd(a, b) = gcd(|a|, |b|).

: gcd(60, 24 ) = gcd(60, –24 ) = 12. Ví d 2.8ụ

B i vì t t c các s nguyên khác không đ u là c s c a s 0, chúng ta luôn luôn có: gcd( a, 0 ) = | ở ấ ả ề ố ướ ố ủ ố

a|.

D dàng xác đ nh đ c ng, n u các s này đ c trình bày d ễ ị ượ UCLN c a hai s nguyên d ủ ố ươ ế ố ượ ướ ạ i d ng

tích c a các th a s nguyên t ừ ố ủ . ố

300 = 22 * 31 * 52, Ví d 2.9ụ

18 = 21 * 32.

gcd(18, 300) = 21 · 31 · 50 = 6.

Trong tr ợ ườ

t c các p. kp = min (ap, bp), đ i v i t ố ớ ấ ả ng h p chung: k = gcd(a, b) ﬁ

Vi c xác đ nh các th a s nguyên t c a các s l n là bài toán không đ n gi n, b i vì r ng các ừ ố ệ ị ố ủ ố ớ ả ằ ơ ở

trình bày ở trên không cho m t kh năng th c ti n đ tính ả ự ễ ể ộ UCLN c a hai s . ố ủ

Các s nguyên a và b là nguyên t cùng nhau, n u chúng không có c s nguyên t chung, hay ố ố ế ướ ố ố

c s chung duy nh t c a chúng là 1. Nói m t cách khác a và b là hai s nguyên t ướ ố ấ ủ ộ ố ố ế cùng nhau n u

gcd(a, b) = 1.

: S 8 và s 15 là các s nguyên t cùng nhau, b i vì c s c a 8 là 1, 2, 4 và 8, còn Ví d 2.10 ụ ố ố ố ố ở ướ ố ủ

các c s c a 15 là 1, 3, 5 và 15. Nh v y, 1 là c s chung duy nh t c a hai s này. ướ ố ủ ư ậ ướ ố ấ ủ ố

2.1.4 S h c trong l p s d ớ ố ư ố ọ

Đ i v i b t kỳ m t s nguyên d ng a b t kỳ, khi chia a cho n, ta nh n đ ố ớ ấ ộ ố ươ n và m t s nguyên ộ ố ấ ậ ượ c

m t s nguyên ộ ố ố ư r, phù h p v i quan h sau: ệ ợ ớ

q nào đó và s d a = qn + r, 0 £ r < n, q = º a / nß .

đây ở º xß ký hi u s nguyên l n nh t, không l n h n ớ ệ ố ơ x. ấ ớ

Đ i v i m t s d ng a và m t s nguyên d ng n, luôn luôn có th tìm đ c ộ ố ươ ố ớ ộ ố ươ ể ớ ượ q và r, phù h p v i ợ

quan h tính toán trên. ệ

: a = 11; n = 7; 11 = 1 * 7 + 4; r = 4. Ví d 2.11 ụ

n là m t s nguyên d ng, thì a mod n, đ c xác đ nh nh ph n d N u ế a là m t s nguyên, còn ộ ố ộ ố ươ ượ ư ầ ị ư

a cho n. Nh v y, đ i v i m t s nguyên a b t kỳ có th vi t : c a phép chia ủ ố ớ ộ ố ư ậ ể ế ấ

a = º a / nß * n + (a mod n)

: 11 mod 7 = 4 ; –11 mod 7 = 3. Ví d 2.12 ụ

ế ề ồ ư

2.2 Lý thuy t v đ ng d

Đ nh nghĩa 2.1 ị ư

˛ Zba , (Đ ng d ) ồ Nn ˛ Cho , . Ta nói a đ ng d v i ồ ư ớ b theo modulo n, khi a và b chia cho n có cùng s d , và ố ư

đ c vi i d ng sau: t d ượ ế ướ ạ

” a b mod n

Ch ng minh : Gi s chia a và b cho n và thu đ c các th ứ ả ử ượ ươ ng nguyên và ph n d . Các ph n d ầ ư ầ ư

= = - £ £ - £ £ a b 0 n 1 0 n 1 n – 1, nghĩa là và . Trong đó và . Khi n m gi a 0 và ữ ằ + rnq 1 1 + rnq 2 r 1 r 2

” ” ba mod n ba mod n đó có th d dàng th y r ng khi và ch khi khi và ch khi ấ ằ ể ễ ỉ . Nh v y: ư ậ ỉ r = 1 r 2

a mod = bn mod n .

Chúng ta đi tìm hi u m t s tính ch t quan tr ng c a đ ng d . ư ủ ồ ộ ố ể ấ ọ

” ” + + ” mod n a mod n và thì a mod n Tính ch t 2.1ấ : N u ế a 1 b 1 b 2 a 1 b 1 b 2

= + = + + + a nt a ( Ch ng minh : T gi và , suy ra , ứ ừ ả thuy t ta có ế a 1 nt 1 b 1 b 2 a 1 ++= bb 1 2 t 1 ) nt 2

+ đi u này có nghĩa là . mod n ề a 1 ”+ a 2 b 1 b 2

” ” ” mod n a mod n và thì * a * mod n Tính ch t 2.2ấ : N u ế a 1 b 1 b 2 a 1 b 1 b 2

= + = + a nt Ch ng minh : ta có và , suy ra ứ T gi ừ ả thuy t ế a 1 nt 1 b 1 b 2

+ + + ” * a = b * ) , đi u này có nghĩa là * a * mod n ề a 1 b 2 ( tb 21 tb 12 ntnt 21 a 1 b 1 b 2

1 , dbbda

= = ” ” gcd( , nd = ,1) ba mod , an mod n N u nh , thì Tính ch t 2.3: ấ ế ư a 1 b 1

1 =nd 1),

- - gcd( ( | ( |) n Ch ng minh : T gi thuy t ta có , mà , nên suy ra , hay ứ ừ ả ế a 1 ) ndb 1 a 1 b 1

” mod n . a 1 b 1

n+2+16n+1+23n chia h t cho 7.

3: Ch ng minh r ng 37 Ví d 2.1ụ ứ ằ

+ 1

+ ” 2

+ ” 1

n ”

37 ” 2 7mod 2 7mod 23 ” 7 7mod ế 16 ” Gi , và , t iả : Rõ ràng chúng ta th y r ng ấ ằ ừ tính ch t 2.2 có: ấ

, , . 37 2 7mod 16 2 7mod 23 7 7mod

n+2+16n+1+23n

” , và t tính ch t 2.3 suy ra đi u ph i ch ng minh. T tính ch t 2.1 có: 37 ấ ừ ừ ứ ề ấ ả 2.7 n 7mod

n ố

2.3 Các s nguyên modulo

{

nZ ) là t p h p các s nguyên

,1,0 ..., -n Các s nguyên modulo bao g m 2 phép ố n (ký hi u ệ ậ ợ ố ồ

nZ đ

c th c hi n gi ng nh c ng và nhân các s toán c ng và nhân. Vi c c ng và nhân trong ệ ộ ộ ượ ư ộ ự ệ ố ố

nguyên, ngo i tr m t đi m là các k t qu s đ c rút g n theo modulo n. ạ ừ ộ ả ẽ ượ ể ế ọ

16Z . T

= 13*11 13*11 143 trong ng t Ví dụ 2.14: Tính ươ ự nh v i các s nguyên ta có ố ư ớ . Đ rútể

= + 143 16mod 15 143 ·= 8 16 15 ng: g n 143 theo modulo 16, ta th c hi n phép chia bình th ọ ự ệ ườ , b i v y ở ậ

16Z .

= · 11 13 15 . Do đó trong

nZ tho mãn h u h t các quy t c quen thu c ộ

nghĩa trên phép c ng và phép nhân trong Các đ nhị ộ ế ả ầ ắ

trong s h c. Sau đây ta s li t kê mà không ch ng minh các tính ch t này: ố ọ ẽ ệ ứ ấ

˛+ ˛ , ZbaZba , Phép c ng là đóng, t c v i b t kì . ứ ớ ấ ộ

˛ Phép c ng là giao hoán, t c là v i b t kì thì: a + b = b + a. ớ ấ ứ ộ , nZba

˛ : Phép c ng là k t h p, t c v i b t kì ế ợ ứ ớ ấ ộ , , nZcba

(a + b) + c = a + (b + c).

nZa ˛

0 là ph n t đ n v c a phép c ng, có nghĩa là v i b t kì : ầ ử ơ ớ ấ ị ủ ộ

a + 0 = 0 + a = a.

nZa ˛

Ph n t ngh ch đ o c a phép c ng c a m t ph n t b t kì là m – a, nghĩa là a + (m – ầ ử ả ủ ầ ử ấ ủ ộ ộ ị

nZa ˛

a) = (m – a) + a = 0 v i b t kì . ớ ấ

˛ Phép nhân là đóng, t c v i b t kì , . ứ ớ ấ , nZba ˛* nZba

˛ abba * = * Phép nhân là giao hoán, nghĩa là v i b t kì , . ớ ấ , nZba

= ˛ ba *)*( c a cb )*(* , . Phép nhân là k t h p, nghĩa là v i ế ợ ớ , , nZcba

nZa ˛

1 là ph n t đ n v c a phép nhân, t c là v i b t kì : ầ ử ơ ớ ấ ị ủ ứ

= a = *11* a a .

˛ Phép nhân có tính ch t phân ph i đ i v i phép c ng, t c là đ i v i , ứ ấ ố ộ ố ớ ố ớ , , nZcba

+ = = + ( a b *) c + cbca * * a (* + cb ) * ba * ca và .

lý Fermat lý Euler và đ nhị

2.4 Hàm Euler, đ nhị

Đ nh nghĩa 2.2 (Hàm Euler) ị

)(nf là s các ph n t c a t p h p, mà t p này là các s nguyên ươ ng, đ t ặ ầ ử ủ ậ ậ ợ ố ố

)(nf Cho n là s nguyên d ố ]n,1 [ và nguyên t cùng nhau v i trong kho ng ả ố ớ n, thì g i là hàm Euler. ọ

Ta công nh n m t s tính ch t quan tr ng c a hàm Euler: ấ ộ ố ủ ọ

f ậ 1)1( = 1.

pf ( ) -= p 1 thì 2. N u ế p là s nguyên t ố ố

f = f ( pq ) ( p f )(*) q cùng nhau thì 3. N u nh ế ư p và q là hai s nguyên t ố ố

- f = - 4. ( p ) p ( p )1

1p ,

2p , …,

kp là s nguyên t

e pp 1 1

e 2 2

ke k

= , đây , thì n ... p 5. N u nh ư ế ở ố ố

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) f = - - - )( n n 1 1 1... (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) 1 p ł Ł ł Ł ł Ł 1 p 1 1 kp

)(nf Trên b ng 2.1 trình bày 30 giá tr đ u tiên c a ị ầ ủ ả . Giá tr ị f (1) là không xác đ nh, nh ng coi r ng ằ ư ị

nó b ng 1 ằ

)(nf B ng 2.1 ả : M t s giá tr c a hàm Euler ị ủ ộ ố

n n n f (n) f (n) f (n)

1 11 10 1 21 12

2 12 4 1 22 10

3 13 12 2 23 22

4 14 6 2 24 8

5 15 8 4 25 20

6 16 8 2 26 12

7 17 16 6 27 18

8 18 6 4 28 12

9 19 18 6 29 28

10 20 8 4 8

> 30 )(nf n ,1 gcd( na , = 1) Đ nh lý Euler: Cho , và là hàm Euler. Khi đó ta có: ị

f )( a n

” 1 mod n

1 mod 10, 5: a = 3, n = 10, f (10) = 4, 34 = 81 ” Ví d 2.1ụ

a = 2, n = 11, f (11) = 10, 210 = 1024 ” 1 mod 11.

nx f )(

Ch ng minh : Gi – là các s t nhiên khác nhau, nh h n cùng nhau x 1 ..., , ứ s ả ử ố ự ỏ ơ n và nguyên t ố

v i ớ n.

f ˛ Hãy xét t các kh năng c a tích a nguyên t cùng nhau v i i ,1 n )( t cấ ả ủ ả , v i ớ . B i vì ở ố ớ n và axi

” x mod n nguyên t cùng nhau v i cũng nguyên t cùng nhau v i . ax i ố ố ớ n, do đó có ớ n, nên tích axi

các ph n d c a phép chia Chú ý r ng ằ ầ ư ủ cho n là khác nhau. N u đi u này không đúng, có nghĩa ề ế axi

là t n t i , sao cho ồ ạ i „ 1 i 2

” mod n ax 2 i ax i 1

i 1

” - ( x 0 mod n Cho nên a nguyên t cùng nhau v i . B i vì ở ố ớ n, nên bi u th c cu i cùng t ứ ể ố ươ ng ) ax i 2

đ ng v i ươ ớ

i 1

i 2

” - x x 0 mod n

nx f )(

Đi u này là mâu thu là các c p khác nhau theo modulo n. x 1 ..., , ề ẫ n, b i các s ố ở ặ

)( n

” x mod n Hãy nhân t t c đ ng th c , thì thu đ ax i ấ ả ẳ ứ c:ượ

)( n

” ... a ... mod n x f x f x 1 x 1

)( n

Hay

)( n

” - ... ( a 0)1 mod n x f x 1

n mod )(

... n x f nguyên t cùng nhau v i ng đ ng v i x 1 B i vì s ố ở ố ớ n nên đ ng th c cu i cùng t ứ ẳ ố ươ ươ ớ

f )( a n

f a n

” - ” hay 01 mod n 1)( mod n

f (n ) + 1 ”

a a mod n. Ta có m t công th c quan tr ng sau: ứ ộ ọ

Đ nh lý Fermat , ng không chia h t cho p. Khi đó ta ị nhỏ: Cho p là s nguyên t ố ố a là s nguyên d ố ươ ế

có - a p 11 ” mod p

pf ( ) -= p 1 Ch ng minh : Ta có , áp d ng đ nh lý Euler ta có đi u ph i ch ng minh. ứ ụ ứ ề ả ị

T đ nh lý Fermat chúng ta có các h qu quan tr ng sau: ừ ị ệ ả ọ

” Za ˛ 1. Cho , p là s nguyên t , thì ta có: a p a mod p ố ố

18 +218 +318 +418 +518 +618 ”

˛ + + ” Zba , 2. Cho , p là s nguyên t ( a b ) a b mod p ố ố

–1 mod 7 Ví d 2.ụ 16: Ch ng mình r ng 1 ứ ằ

Gi cùng nhau v i 7. Nên theo đ nh lý Fermat chúng ta có iả : Các s 1, 2, 3, 4, 5, 6 là s nguyên t ố ố ố ớ ị

các ph ng trình sau: ươ

; ; ; ; ; 16 ” 1 7mod 26 ” 1 7mod 36 ” 1 7mod 46 ” 1 7mod 56 ” 1 7mod 66 ” 1 7mod

c ba hai v t ng ph ng trình và c ng l i ta đ c: L y bấ ậ ế ừ ươ ộ ạ ượ

-= ” 6 7mod 1 7mod 118 +218 +318 +418 +518 +618

ở ộ ậ ậ

2.5 Thu t toán Euclide và thu t toán Euclide m r ng

2.5.1 Thu t toán Euclide ậ

„ ˛ bZba , , 0 Zq ˛ Nr ˛ Đ nh lý Euclide : Cho , t n t và ị ồ ạ i duy nh t c p giá tr ( ấ ặ ị q, r) v i ớ th aỏ

mãn:

= + a bq r £0 r < b , .

đây ở r g i là s d . ố ư ọ

ộ ố ố ư ư

= a Có m t s ký hi u cho s d nh sau: ệ r = mod b . , )(aRr b

M t s tính ch t đ n gi n c a v s d : ả ủ ề ố ư ấ ơ ộ ố

= - 1. , b i vìở aR )( b aR )( b

= + + - (cid:236) (cid:252) a r b ) r a -= ( )( (cid:219) (cid:237) (cid:253) qb < q < £ £ 0 r b 0 b r (cid:238) (cid:254)

+ = ˛ " ib ) ), Zi 2. , b i vìở ( aR b ( aR b

+ = + + a ib ( ) rbiq .

N u nh b, ký hi u là ba . ư r = 0 thì ta nói a chia h t cho ế ế ệ

˛ , Ziba , Đ nh lý 2.1 : ị : Đ i v i b t kỳ các s ố ố ớ ấ

= + gcd( ba , ) gcd( a bib , ) .

1 , = bdq

(cid:222) = + = + a a ib iq ) Ch ng minh: N u nh . Lúc này da và db , thì ứ ế ư dq 2 qd ( 1

( + a ib ) d . Có nghĩa là:

+ £ gcd( ba , ) gcd( a bib , ) . (*)

1 , = dqbdq

(cid:222) + = = - ( + a ib ) d a ib a iq ) T ng t s r ng gi và . Lúc này db (cid:222) da . ươ ự ả ử ằ qd ( 1

Có nghĩa là:

+ ‡ gcd( ba , ) gcd( a bib , ) . (**)

T (*) và (**) chúng ta có đ ng th c gcd(a,b)=gcd(a+ib,b). ẳ ứ ừ

„ ˛ bZba , , 0 Đ nh lý 2.2 , ta có: ị : Đ i v i b t kỳ ố ớ ấ

= gcd( ba , ) gcd( ( )) aRb , b

Ch ng ứ minh.

= + a bq , B i vì ở )(aR b

= = - gcd( ba , ) gcd( a bqb , ) gcd( baR ( ), ) .

T đ nh lý 2.2 ta có thu t toán Euclide. Đây là thu t toán giúp tìm UCLN c a hai s nguyên d ừ ị ủ ậ ậ ố ươ ng

a0 và a1 v i ớ a0 > a1.

Thu t toán đ c miêu t b ng dãy các phép chia nh sau: ậ ượ ả ằ ư

0 < a2 < a1

= + a a qa 11 ,2

0 < a3 < a2

= + a a 1 qa 22 ,3

…

0 < ak < |ak-1|

= + a a q a , - - -

+ a 0 =- 1 qa k

, nh n đ c gcd( a0, a1) = gcd(a1, a2) = … = gcd(ak, 0) = ak. D a vào đ nh lý 2.1 ị ự ậ ượ

: Tìm gcd(814, 187). Ví d 2.ụ 17 (Thu t toán Euclide) ậ

Gi i:ả Khai tri n dãy phép tính theo thu t toán Euclide: ể ậ

814 = 4 * 187 + 66

187 = 2 * 66 + 55

66 = 1 * 55 + 11

55 = 5 * 11 + 0

V y gcd(814, 187) = 11. ậ

Thu t toán có th vi ể ế ậ t nh sau: ư

ng Vào: Hai s nguyên d ố ươ a và b v i ớ a > b

Ra: UCLN c a ủ a và b

(1) While b # 0 do a mod b, a ‹ r ‹ b, b ‹ r

(2) Return (a).

2.5.2 Thu t toán

Euclide m r ng ậ ở ộ

(Ph n t ngh ch đ o) ị ầ ử ả ị

nZb ˛

” ” a * b b * a 1 mod n Cho . Ph n t ngh ch đ o c a sao cho ầ ử ả ủ a là ph n t ầ ử ị . Kí hi uệ Đ nh nghĩa 2.3 nZa ˛

ph n t ngh ch đ o c a ầ ử ả ủ a là a-1. ị

Đ nh lý 2.2 a > 0 nguyên t cùng nhau v i i ph n t ị : Cho s nguyên ố ố ớ n, thì luôn t n t ồ ạ ầ ử ả ngh ch đ o ị

c a ủ a theo modulo n.

,2,1 ..., -n Ch ng minh c a t p h p v i ứ ậ . Nhân t ng ph n t ừ ớ a theo modulo n, ợ

- mod 2(), a n ( a ầ ử ủ ậ }) mod n ), ..., (( n )1 a mod n n ợ { : Hãy xét t p h p ợ { c t p h p nh n đ ậ ượ ậ , t p này s bao g m các s 1, 2,…, ồ ẽ ậ ố

ia mod =n 1 – 1, có nghĩa đ i v i m t s giá tr ố ớ ộ ố ị i nào đó s th a mãn đi u ki n ẽ ỏ ệ ề ế . Đi u này d n đ n ề ẫ

m t mâu thu n n u nh t n t i hai giá tr ư ồ ế ẫ ộ ạ ị h và k th a mãn đi u ki n trên, nghĩa là ề ệ ỏ

= ” ha mod n ka mod n h k mod n . Đi u này d n đ n , vì gcd(a, n) = 1, suy ra h = k. V y ta tìm đ ế ề ẫ ậ ượ c

i là ph n t ngh ch đ o c a ầ ử ả ủ a và i là duy nh t.ấ ị

H qu 2.1 : N u nh i ph n t ệ ả ư p là s nguyên t ố ế ố , thì b t kỳ s ấ ố a, 0 < a < p, luôn t n t ồ ạ ầ ử ả ngh ch đ o ị

theo modulo p.

ngh ch đ o thông qua thu t toán Euclide Chúng ta s tìm hi u v cách tìm ph n t ể ầ ử ẽ ề ả ậ ị m r ng. ở ộ

T dãy chia c a thu t toán Euclide ừ ủ ậ

= + a 0 < a2 < a1 qa 11 ,2 a 0

= + 0 < a3 < a2 qa 22 a ,3 a 1

…

= + a a q a , - - - 0 < ak < ak-1

Ta d dễ àng rút ra dãy sau:

= = - - - = - a a q a a a q ( a q a ) - - - - - - - - - mà nên suy ra , t ng t a a q a ươ ự - - -

2-ka

nh th , chúng ta rút ra , đ n cu i cùng chúng ta có đ ư ế ế ố ượ c bi u th c d ng sau: ứ ạ ể

(2.1)

= ak + yaxa 0

gcd( 1) , , chúng ta có x là ph n t ngh ch đ o c a N u nh ư ế ầ ử ả ủ a0 theo modulo a1. ị =aa 1 0

Ví d 2.ụ 18 (Thu t toán Euclide m r ng): ở ộ ậ

1. Tìm x và y trong bi u th c (2.1) v i ớ a0 = 814 và a1 = 187. ứ ể

Gi c dãy: iả : Theo ví d 2.17 ta thu đ ụ ượ

814 = 4 * 187 + 66

187 = 2 * 66 + 55

66 = 1 * 55 + 11

55 = 5 * 11 + 0

Suy ra: 11 = 66 – 1 * 55 = 66 – 1 * (187 – 2 * 66) = 3 * 66 – 1 * 187 = 3 * (814 – 4 * 187) –187 = 3 *

2. Tìm ph n t

ngh ch đ o c a 17 theo modulo 74.

ầ ử

ả ủ

ị

c 3 * 74 – 13 * 17 = 1. Nên ph n t

iả : Theo ví d trên ta có đ ụ

ượ

ầ ử

nghich đ o c a 17 là – ả ủ

13, nh ng ch l y s d

ng, nên ph n t

ngh ch đ o c a 17 là 74 – 13 = 61.

ỉ ấ ố ươ

ầ ử

ả ủ

ị

814 – 13 * 187. V y ậ x = 3 và y = –13.

i ph ng ả ươ ng trình đ ng d trong nhóm th ư ồ ươ

2.6 Gi

ng pháp gi i ph ng trình đ ng d , nh ng chúng tôi mu n trình bày v i Có nhi u ph ề ươ ả ươ ọ ớ b n đ c ạ ư ư ồ ố

m t ph ộ ươ ng pháp khá hay d a vào đ nh lý sau: ự ị

” ax b mod n Đ nh lý 2.3 : Cho n > 1, gcd(a, n) = 1. Khi đó ph ị ươ ng trình đ ng d ư ồ có nghi m duy ệ

1)( n mod

nh t, và nghi m đó là: ệ ấ - = ba x n

1)( n

f a n

n - 1)(

- ” ” Ch ng minh : Theo đ nh lý Euler, ta có , suy ra 1)( mod n . baa b mod n ứ ị ệ . V y nghi m ậ

= x ba mod n .

i ph ng trình 7x ” 3 mod 10. Ví d 2.ụ 19: Gi ả ươ

)10(f

Chúng ta tính nh sau: ư

= 4; x ” 3 * 74-1 mod 10 ” 1029 mod 10 ” 9.

Th nh ng cách này s khó th c hi n n u b c c a ậ ủ a đ l n. B i v y chúng ta xem cách sau. ở ậ ủ ớ ư ự ế ẽ ế ệ

Chúng ta đã bi t đ nh lý v ngh ch đ o, n u nh gcd( a, n) = 1, thì luôn t n t i ph n t ế ị ề ph n t ầ ử ư ế ả ị ồ ạ ầ ử

- ” ” ax b mod n ngh ch đ o ng trình , suy ra x ba mod n . ả a-1. Nên t ị ph ừ ươ

7 ”x 3 mod 10 i ph ng trình . Ví d 2.ụ 20: Gi ả ươ

- = ng trình x = 3 * 3 mod 10 = 9. 7 1 mod 10 3 Chúng ta th y ấ . Nên nghi m c a ph ệ ủ ươ

” ax b mod n Đ nh lý 2.4 : Cho n >1, đ ph ng trình có nghi m thì đi u ki n c n và đ là gcd( a, ị ể ươ ệ ầ ủ ệ ề

n)|b.

” ax b mod n Ch ng minh : Ph ng trình có th vi i d ng ph ứ ươ t d ể ế ướ ạ ươ ng trình tuy n tính sau ế

ax + kn = b, (2.2),

k là s nguyên. ố

Ta ch ng minh đi u ki n c n. Gi a, n) là ứ ề ệ ầ ả ử s hoàn thành đi u ki n (2.2). B i vì s gcd( ệ ề ố ờ ướ ủ c c a

c c a v ph i. v trái, nên nó cũng ph i là ế ả ướ ủ ế ả

Ch ng minh đi u ki n đ . ng d ng thu t toán Euclide đ i v i hai s ố ớ ố a và n, có th tính ụ ứ ể ậ

ề + m ệ ủ Ứ = l gcd( na ), n a (2.3)

b/gcd(a, n) là s nguyên, nên nhân hai v (2.3) cho b/gcd(a, n) và nh n đ B i vì ở ế ố ậ ượ c công th c (2.2), ứ

l = x mod n và đây là m t nghi m. ở ệ ộ b ), na gcd(

D dàng ki m tra ph ng trình đã có nghi m d ng ễ ể ươ ệ ạ

+ x mod n , i = 0, 1, 2, .., gcd(a, n) – 1. ni gcd( , na )

T c là ph ng trình đã cho có gcd( a, n) nghi m khác nhau, nghi m này nh h n ứ ươ ỏ ơ n. ệ ệ

Ví d 2.ụ 21:

1. Gi

2 ”x 5 mod 10 i ph ng trình ả ươ

Vì gcd(2, 10) = 2, vì 2 không là c c a 5 nên ph ướ ủ ươ ng trình trên vô nghi m, n u không d a vào ệ ự ế

đ nh lý cũng d dàng th y r ng 2 ị ấ ằ ễ x + 10y = 5 cũng vô nghi m, vì v trái là s ch n, còn v ph i là s ế ố ẳ ệ ế ả ố

l ẻ . Đi u này là không th . ể ề

2. Gi

6 ”x 18 mod 36 i ph ng trình . Vì gcd(6, 36)|18. Nên ph ng trình này có 6 nghi m: 3, 9, ả ươ ươ ệ

15, 21, 27 và 33.

ị

2.7 Đ nh lý ph n d Trung Hoa. ầ ư

Đ nh lý này nh m giúp chúng ta gi ằ ị i h ph ả ệ ươ ng trình đ ng d th c, đ nh lý phát bi u nh sau: ị ư ứ ư ể ồ

Gi s cho các s ng nguyên t c1, c2, ả ử ố n1, n2, …, nk là các s nguyên d ố ươ ố cùng nhau t ng đôi m t và ừ ộ

ố ệ ươ ng trình đ ng d : ư ồ

…, ck là các s nguyên khi đó h ph x ” c 1 mod n 1

2 mod n

x ” c

…

” x c mod n

Có nghi m duy nh t ấ theo modulo n và nghi m đó là: ệ ệ

(2.4)

= 1

- x ( mod ) mod n NNc i i n i (cid:229)= i

= n đây và . N = i ở ...21 nn M n i

Ch ng minh : ứ

N u ta ch ng minh h trên t ng đ ng v i m t ph ng trình sau: ứ ế ệ ươ ươ ộ ớ ươ

” x mod n x 0

= 1

- mod ) đây thì coi nh chúng ta đã ch ng minh đ c đ nh lý trên. ở ứ ư ượ ị x 0 ( NNc i i n i (cid:229)= i

- ” , t Ta có Ni chia h t cho ns, khi s „ mod (mod ) ế i. Đi u này d n đ n ế ề ẫ đóừ x 0 NN ( i cn ) i i n i

(mod ) . Đi u này có nghĩa h trên t ng đ ệ ề ươ ươ ng v i h sau: ớ ệ x ” 0 c i n i

x ” x 0 mod n 1

x ” x 0 mod n 2

...

” x mod x 0

” x mod n Đi u này t ng đ ng v i m t ph ng trình sau . Mà ta đã bi t ph ng trình này ề ươ ươ ớ ộ ươ ế ươ x 0

0x mod n.

có nghi m duy nh t là ệ ấ

i h ph ả ệ ươ ng trình đ ng d sau: ồ ư

Ví d 2.ụ 22: Gi 5”x 7mod

3”x mod 11

”x 10 mod 13

Gi iả : Ta có n = 7 * 11 * 13 = 1001; N1 = n/5 = 143; N2= n/11 = 91; N3 = n/13 = 77

Ta đi tính ph n t ngh ch đ o c a ầ ử ả ủ Ni theo modulo ni ị

143-1 mod 7 = 5; 91-1 mod 11 = 4 và 77-1 mod 13 = 12.

Áp d ng công th c (2.4) ta có đ c nghi m c a h ph ng trình là: ụ ứ ượ ủ ệ ươ ệ

x = (5.143.5 + 3.91.4 + 10.77.12) mod 1001 = 894.

ậ

2.8 B c và căn nguyên th y ủ

Đ nh nghĩa 2.4 ị (B c) ậ

ng trình đ ng d Cho gcd(a, n) = 1. B c ậ a mod n là s nguyên d ố ươ ng nh nh t ỏ ấ g th a mãn ph ỏ ươ ồ ư

th c: ứ

n(a).

, a 1” mod n

Kí hi u b c là Ord ậ ệ

Ví d 2.ụ 23: Tìm b c c a 2 mod 5 ậ ủ

5(2) = 4.

Gi iả : 21 mod 5 = 2; 22 mod 5 = 4; 23 mod 5 = 3; 24 mod 5 = 1; v y Ord ậ

Đ nh nghĩa 2.5 ị (Căn nguyên th y)ủ

N u nh b c c a ư ậ ủ a modulo n b ng giá tr c a hàm Euler c a ị ủ ế ằ ủ ủ n. ọ

5(2) =

ủ n. Thì a g i là căn nguyên th y c a =)5(f 4. Ví d 2.ụ 24: S 2 là căn nguyên th y c a 5. Vì Ord ủ ủ ố

ư ậ ặ

2.9 Th ng d b c hai

Th ng d b c hai đóng vai trò r t quan tr ng trong lý thuy t s . Ví d , thu t toán phân tích s ế ố ư ậ ụ ấ ậ ặ ọ ố

nguyên ra th a s . Ngoài ra th ng d b c hai cũng ng d ng l n trong m t mã cũng nh trong các giao ứ ừ ố ư ậ ư ụ ậ ặ ớ

th c mã hóa. ứ

Đ nh nghĩa 2.6 (Th ng d b c hai) ị ư ậ ặ

nZ g i là th ng d b c hai theo modulo ư ậ

2 ”

1>n . S t nhóm n, n u trong Cho n là s nguyên và ố ố ừ ặ ọ ế

nZ t n t

nhóm i s , tr i g i là không th ng d c l x a mod n ồ ạ ố x, th a mãn đi u ki n ề ệ ỏ ườ ng h p ng ợ ượ ạ ọ ặ ư

T p h p các s th ng d b c hai theo modulo b c hai. ậ ố ặ ư ậ ậ ợ n ký hi u ệ QRn, t p h p không th ng d b c hai ư ậ ặ ậ ợ

QNRn. ký hi u là ệ

Ví d 2.ụ 25: Tính QR11 là t p t ặ ậ ấ ư ậ

}

= = Chúng ta có

{ 2 2 10,9,8,7,6,5,4,3,2,1

t th ng d b c hai theo modulo 11. }9,5,4,3,1 { mod 11 QR , trong ví d , chúng ta ụ

* 11Z .

tính QR11 b ng cách l a ch n các ph n t ầ ử ủ ự ằ ọ

}

}9,5,4,3,1 {

= i r ng . Đi u này s tìm c a nhóm { 2 2 5,4,3,2,1 mod 11 Đ c gi ộ ả có th ki m tra l ể ể ạ ằ ề ẽ =QR 11

hi u qua đ nh lý sau: ị ể

Đ nh lý 2.5 . Khi đó nh ng kh ng đ nh sau đây là đúng. ị : Cho p là s nguyên t ố ố ữ ẳ ị

{

= - x (mod p 0|) £< x ( p

}2/)1

. QRp

pZ chia ra hai t p con,

Nhóm b ng nhau. QRp và QNRp có s ph n t ậ ầ ử ằ ố

Ch ng minh : ứ

ta ch ng minh đi u kh ng đ nh th Rõ ràng ứ ề ẳ ị ứ nh t. ấ ằ r ng

Chúng { = ˝ - (mod x S p 0|) £< x ( p

} 2/)1

pQR

S = , đi u này s đúng n u nh chúng . Đ ch ng minh ứ ể ư ề ẽ ế QRp

˝ S ta ch ng minh đ c r ng . QRp ứ ượ ằ

pQR

a ˛ Ch n m t s . T n t i s a (mod p ) x ” 2 ộ ố a b t kỳấ ọ ồ ạ ố x < p, th a mãn đi u ki n ệ ề ỏ . N u nh ế ư

- £ - £ x ( p 2/)1 y -= p x ( p 2/)1 a ˛ S , thì . Gi r ng s x > (p – 1)/2. Nh th và ả ử ằ ư ế

˝ + ” ” - ” - ” S . QRp y ( p x ) p 2 px x x a (mod p ) . Ch ng t ứ , ỏ

- # = p ( 2/)1 Ta đi ch ng minh đi u kh ng đ nh th hai. Đ ch ng minh ,thì nó s t QRp ứ ứ ứ ề ể ẳ ị ẽ ươ ng

- 0 £<< y x ( p 2/)1 đ ng v i vi c ch ng minh r ng đ i v i t t c s , ươ ố ớ ấ ả ố x, th a mãn b t đ ng th c ỏ ấ ẳ ứ ứ ệ ằ ớ

+ ” - ” - thì th a mãn đi u ki n . Gi s đi u này sai: x „ 2 y (mod p ) x y ( x xy )( y ) 0 (mod p ). ề ệ ỏ ả ử ề D nẫ

x + y < p và p là s nguyên t đ n, ế p|(x + y) ho c ặ p|(x – y). B i vì ở ố ố . Nên ch có th là ỉ ể x = y. Đi u này trái ề

* Z p

- # = p ( 2/)1 -= p 1 ng c v i gi . Mà # QRp ượ ớ ả thuy t. V y ế ậ , nên đi u kh ng đ nh th hai hoàn toàn ị ứ ề ẳ

đúng.

Th ng xu t hi n bài toán, xác đ nh xem s ườ ố n có ph i là th ng d b c hai theo modulo đã cho hay ư ậ ả ặ ệ ấ ị

không. V n đ này g i là bài toán v th ng d b c hai. Bài toán này đ c gi i quy t thông qua đ nh lý ề ặ ư ậ ề ấ ọ ượ ả ế ị

pZx ˛

Đ nh lý 2.6 , x là th ng d ị (Tiêu chu n Euler) ẩ : Cho p là s nguyên t ố ố . Đ i v i b t kỳ s ố ố ớ ấ ặ ư

2/)1

( x p

b c hai khi và chi khi th a mãn đi u ki n sau: ậ ề ệ ỏ - ” . 1 mod p

pQR

pZy ˛

x ˛ Ch ng minh thì t n t sao cho . Theo đ nh lý Fermat y ” 2 x (mod p ) ứ : Đ i v i ố ớ i s ồ ạ ố ị

(

2/)1

- - ” ” chúng ta có, . x y 1 mod p

2/)1

( x p

( y p

- - ” ” - Ng , nh v y . 1 mod p 12/)1 0 mod p c l ượ ạ i, n u nh ư ế ư ậ x là nghi m c a đa th c ệ ủ ứ

pZ là m t tr

Chúng ta đã bi ng. Mà ta d dàng th y r ng m i ph n t c a tr t ế ộ ườ ấ ằ ầ ử ủ ễ ỗ ườ ủ ng là nghi m c a ệ

- . Hay nói cách khác, m i ph n t khác không c a tr y p y 0” mod p đa th c ứ ầ ử ỗ ủ ườ ng là nghi m c a đa ệ ủ

(

2/)1

(

2/)1

th c:ứ - - - + ” - ” - y (1 y )(1 y )1 0 mod p .

Mà t t c các nghi m này ph i khác nhau, b i vì đa th c có b c ấ ả ậ p – 1. Đi u này d n đ n ( ế p – 1)/2 ứ ệ ề ẫ ả ở

( y p

- ” - ph i khác nhau. Mà theo đ nh lý v s ph n t 12/)1 0 mod p nghi m c a đa th c ủ ứ ệ ề ố ầ ử ủ ậ c a t p ả ị

th ng d b c hai ta có t p , m i ph n t ng trình ư ậ ậ QRp có (p – 1)/2 ph n t ầ ử ặ ầ ử ỗ là nghi m c a ph ệ ủ ươ

( y p

pZ cũng ph i th a mãn ph ả

- ” - . Và b t kỳ ph n t nào khác c a nhóm ng trình 12/)1 0 mod p ầ ử ấ ủ ỏ ươ

( y p

pQR

pZx ˛

- x ˛ . ”+ 12/)1 0 mod p . V y ậ

Khi ch ng minh đ nh lý này chúng ta có th đi u kh ng đ nh sau: N u nh ư ể ề ứ ế ẳ ị ị mà tiêu chu nẩ

2/)1

( x p

Euler không th a mãn thì: ỏ - - ” . 1 mod p

2.10

Các ký hi u Legendre và Jacobi ệ

gendre là m t công c h u ích đ xem xét li u m t s nguyên a có là th ng d b c hai Ký hi u Le ệ ộ ố ụ ữ ể ệ ộ ư ậ ặ

theo modulo c a m t s nguyên t ộ ố ủ ố p hay không?

2.10.1 Ký hi u Legendre ệ

Đ nh nghĩa 2.7 ị

nhiên

ố l

ố ự

và ẻ , thì ký hi u Legendre ệ a là m t ộ s t N u ế p là s nguyên t ố

(cid:246) (cid:230) (cid:247) (cid:231) đ c xác đ nh nh sau: ượ ư ị (cid:247) (cid:231) a p ł Ł

o 0

n u ế a|p;

pQR

o 1

a ˛ ; n u ế

pQNR

o −1

a ˛ n u ế

: ấ ủ ệ

Các tính ch t c a ký hi u Legendre a, b ˛ và Z. Khi đó ký hi u Legendre có các tính ch t sau: Cho p là m t s nguyên t ộ ố l ố ẻ ệ ấ

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:247) (cid:231) (cid:247) (cid:231) ” (cid:247) (cid:231) 1. (cid:247) (cid:231) (cid:247) (cid:231) ł Ł ab p a b b p ł Ł ł Ł

(cid:246) (cid:230) (cid:246) (cid:230) ” (cid:247) (cid:231) (cid:247) (cid:231) ba mod p , thì 2. N u ế =(cid:247) (cid:247) (cid:231) (cid:231) a p b p ł Ł ł Ł

(cid:246) (cid:230) (cid:247) (cid:231) 1 3. (cid:231) 1 =(cid:247) p ł Ł

p 2

- ” (cid:236) (cid:246) (cid:230) 1 khi p 1 4mod (cid:247) (cid:231) - (cid:237) )1( 4. -=(cid:247) (cid:231) ” - 1 khi p 3 4mod 1 p ł Ł (cid:238)

12 8

- ” (cid:236) (cid:246) (cid:230) 1 khi p 7,1 8mod (cid:247) (cid:231) = 5. (cid:237) )1( -=(cid:247) (cid:231) ” - 1 khi p 5,3 8mod 2 p ł Ł (cid:238)

ø Ø ” œ Œ (cid:236) (cid:246) (cid:230) 1 khi p 11,1 mod 12 œ Œ (cid:247) (cid:231) = 6. (cid:237) )1( -=(cid:247) (cid:231) ” - 1 khi p 7,5 mod 12 3 p ł Ł (cid:238)

- ø Ø ” œ Œ (cid:236) (cid:246) (cid:230) 1 khi p 4,1 5mod œ Œ (cid:247) (cid:231) = 7. (cid:237) )1( -=(cid:247) (cid:231) ” - 1 khi p 3,2 5mod 5 p ł Ł (cid:238)

ø Ø ” œ Œ (cid:236) (cid:246) (cid:230) 1 khi p 27,25,19,9,3,1 mod 28 œ Œ (cid:247) (cid:231) = 8. (cid:237) )1( -=(cid:247) (cid:231) ” - 1 khi p 23,17,15,13,11,5 mod 28 7 p ł Ł (cid:238)

p 2

- - (cid:246) (cid:230) (cid:246) (cid:230) (cid:247) (cid:231) (cid:247) (cid:231) - )1( thì 9. N u ế p và q là các s nguyên t ố l ố ẻ =(cid:247) (cid:247) (cid:231) (cid:231) q p p q ł Ł ł Ł

t l Euler ch ng minh r ng v i m i s nguyên t ẩ ể ế ạ i nh sau: ư ọ ố ứ ằ ớ ố p và s ố a,

Tiêu chu n Euler có th vi a £ p £1 ,

(

2/)1

(cid:246) (cid:230) - (cid:247) (cid:231) ” a mod p . (cid:247) (cid:231) a p ł Ł

Ví d 2.26 ụ : Tính ký hi u Legendre ệ

(cid:246) (cid:230) (cid:247) (cid:231) ł Ł 12345 331

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) = (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) ł Ł ł Ł ł Ł 3 331 5 331 823 331

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) = (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) ł Ł ł Ł ł Ł 3 331 5 331 161 331

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) = (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) ł Ł ł Ł ł Ł ł Ł

(

( -=

) 1

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) 5 331 ( 23 331 ( - - - (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) 3 331 ) 1 7 331 ) 1 ł Ł ł Ł ł Ł ł Ł 331 3 331 7 331 23 331 5

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) -= (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) ł Ł ł Ł ł Ł ł Ł 1 3 1 5 2 7 9 23

(

1 1 3 5 )( )( ) )( -= 1111 2.10.2 Ký hi uệ Jacobi

2.8 ị Đ nh nghĩa

Ký hi u Jacobi là cho s nhiên l ệ t ng quát hóa c a ổ ủ ký hi u Legendre ệ t ố ự ẻ n. Gi sả ử

a pp 1

a 2

a kp

= n ...

là d ng phân tích tiêu chu n c a a b t kỳ, ký hi u Jacobi là: ẩ ủ n. V i s nguyên ớ ố ạ ệ ấ

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) =(cid:247) (cid:231) , trong đó t t c các ký hi u bên v ph i là ký hi u Legendre. ... ấ ả ệ ế ệ ả (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) ł Ł a n a p ł Ł ł Ł ł Ł a p 1 a kp

Các tính ch t c a ký hi u ấ ủ

Cho n là các s t nhiên l Z. Kí hi u Jacobi có các tính ch t sau: ệ Jacobi: a, b ˛ và ố ự ệ ấ ẻ

1. N u n là s nguyên t thì ký hi u Jacobi là ký hi u Legendre ế ố ố ệ ệ

{

}1,1,0

(cid:246) (cid:230) - ˛ (cid:247) (cid:231) 2. ł Ł a n

(

) 1

(cid:246) (cid:230) „ =(cid:247) (cid:231) 0 khi gcd na , 3. ł Ł a n

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) ” (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) 4. ł Ł ł Ł ł Ł ab n a n b n

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) ” (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) 5. , đi u này d n t i ẫ ớ ề là 0 ho c 1.ặ ł Ł ł Ł ł Ł ł Ł a mn a m b n a 2n

(cid:246) (cid:230) (cid:246) (cid:230) ” =(cid:247) (cid:247) (cid:231) (cid:231) ba mod n , thì 6. N u ế ł Ł ł Ł a n b n

(cid:246) (cid:230) (cid:231) 1 7. ł Ł 1 =(cid:247) n

- ” (cid:236) (cid:246) (cid:230) 1 nkhi 1 4mod - -=(cid:247) (cid:231) (cid:237) )1( 8. ” - ł Ł 1 nkhi 3 4mod 1 n (cid:238)

12 8

)

- ” (cid:236) (cid:246) (cid:230) 1 nkhi 7,1 8mod = -=(cid:247) (cid:231) 9. (cid:237) )1( ” - ł Ł 1 nkhi 5,3 8mod 2 n (cid:238)

)( 1 4

) ( ( 1)

- - (cid:246) (cid:230) - =(cid:247) (cid:231) ( 10. ł Ł m n n m

: Ví d 2.27 ụ

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) =(cid:247) =(cid:247) (cid:247) (cid:231) (cid:247) (cid:231) (cid:231) (cid:231) .1 ł Ł ł Ł ł Ł ł Ł 37035 331 294 331 2 331 147 331

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) -= =(cid:247) =(cid:247) =(cid:247) (cid:247) (cid:231) (cid:231) (cid:231) (cid:231) ł Ł ł Ł ł Ł ł Ł 147 331 37 147 147 37 331 147 2 (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) = =(cid:247) =(cid:247) =(cid:247) =(cid:247) (cid:231) (cid:231) (cid:231) (cid:247) (cid:231) (cid:231) 1 ł Ł ł Ł ł Ł ł Ł ł Ł 36 37 2 37 9 37 37 9 1 9

nên t đó 37035 là th ng d b c hai mod 331. Vì 331 là s nguyên t ố ố ừ ư ậ ặ

Có hai tính ch t đúng v i ký hi u Legendre nh ng không th m r ng cho ký hi u Jacobi. ể ở ộ ư ệ ệ ấ ớ

+ Khác v i ký hi u Legendre, ký hi u Jacobi không cho bi t li u ệ ệ ớ ư ậ ế ệ a có ph i là m t th ng d b c ả ặ ộ

(cid:246) (cid:230) (cid:246) (cid:230) (cid:231) (cid:231) 1=(cid:247) 1=(cid:247) hai theo modulo n hay không. S th c n u . Tuy nhiên thì không có nghĩa QRn thì ự ự ế a ˛ ł Ł ł Ł a n a n

là a ˛ QRn.

(

2/)1

(cid:246) (cid:230) - (cid:247) (cid:231) ” a mod p + Tính ch t th hai không th m r ng g n v i đ ng d th c Euler ể ở ộ ư ứ ớ ồ ứ ắ ấ v i sớ ố (cid:247) (cid:231) a p ł Ł

nguyên t a b t kỳ. M t cách t nhiên đ ng d th c Euler m r ng t ố p và s nguyên ố ấ ộ ự ư ứ ở ộ ồ ừ ệ ký hi u

(

2/)1

(cid:246) (cid:230) - ” (cid:247) (cid:231) a mod n Legendre sang ký hi u Jacobi là v i h p s l d ng ệ ớ ợ ố ẻ ươ ư ứ n. Tuy nhiên đ ng d th c ồ ł Ł a n

này là sai v i ít nh t m t n a c a các ấ ộ ử ủ ớ a mod n khi n là h p s . ợ ố

2.10.3 B đ Gauss ổ ề

p 2

N u nh khác 2 thì: ư p và q là 2 s nguyên t ế ố ố - - (cid:246) (cid:230) (cid:246) (cid:230) (cid:247) (cid:231) (cid:247) (cid:231) - )1( =(cid:247) (cid:247) (cid:231) (cid:231) q p p q ł Ł ł Ł

n + 1, thì p bình ph ng theo Hay nói cách khác, n u nh m t trong 2 s ế ư ộ ố p ho c ặ q có d ng 4 ạ ươ

modulo q khi và ch khi q là bình ph ng theo modulo p. N u nh c 2 s n + 3, thì p ỉ ươ ư ả ố p và q có d ng 4 ế ạ

bình ph ng theo modulo q khi và ch khi q không là bình ph ng theo modulo p. ươ ỉ ươ

Ch ng minh : ứ

1-qp

F p „ q , xét tr ng và cũng bi t đây là cũng là nhóm cyclic. Theo đ nh lý nh Fermat Cho r ng ằ ườ ế ỏ ị

-qp

thì q, nên trong nhóm t n t i ph n t q. Chúng ta xem nó là w, lúc này 11 - chia h t cho ế ồ ạ ầ ử có b c là ậ

1-qp

F 1„w và trong . Bây gi ờ xác đ nh t ng Gauss: ổ ị 1=qw

qZx

(cid:246) (cid:230) (cid:247) (cid:231) = (cid:229) y (cid:247) (cid:231) ˛ x q ł Ł

Chúng ta s ch ng minh 2 đi u kh ng đ nh sau: ẽ ứ ề ẳ ị

q 2

: Ta có đ ng th c sau Đi u kh ng đ nh 1 ẳ ề ị ứ ẳ - . -= y )1( q

Ch ng minh : ứ

+ zx

, zx

(cid:246) (cid:230) (cid:246) (cid:230) - x ) (cid:247) (cid:231) (cid:247) (cid:231) = (cid:229)= (cid:229) (cid:229) y w (cid:247) (cid:231) (cid:247) (cid:231) ˛ ˛ xz q ł Ł ł Ł w q

0„x T t ng cu i cùng . Khi , có: ( ux q { }0\qZ ừ ổ ố x l y giá tr trong t p ị ậ ấ

q 2

- - - (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) - - - - x ) 1 1 (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) )1( . =(cid:247) (cid:231) -=(cid:247) (cid:247) (cid:231) (cid:231) (cid:247) (cid:231) ( ux q x q ux q ux q ł Ł ł Ł ł Ł ł Ł

q 2

qZu

T đâyừ - - (cid:229)= )1( y 2 , wC u ˛

}

{ 0\

qZx

- (cid:246) (cid:230) - 1 (cid:247) (cid:231) = (cid:229) C . v i ớ (cid:247) (cid:231) ˛ ux q ł Ł

Rõ ràng

}

{ 0\

qZx

(cid:246) (cid:230) (cid:247) (cid:231) = (cid:229) C 1 . -=(cid:247) q (cid:231) ˛ 1 q ł Ł

{ }1\qZ

- 0„u , thì nh n các giá tr trong t p , cho nên: N u nh ư ế ậ ậ ị s -= 1 ux

qZs

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) = -= - (cid:229) C , (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) ˛ s q 1 q 1 q ł Ł ł Ł ł Ł

{ }0\qZ

(cid:246) (cid:230) (cid:247) (cid:231) 0 , còn trong s l ng ph n t là bình ph ng và s l ng ph n t không là B i vì ở ố ượ ầ ử ươ ố ượ ầ ử (cid:231) 0 =(cid:247) p ł Ł

chính ph ng là nh nhau. T đây: ươ ư ừ

= = - - (cid:229) (cid:229) ( q )1 q . ˛ ˛ w { } 0\ wC u q

c đi u kh ng đ nh 1, chúng ta ch ng minh ti p đi u kh ng đ nh ti p theo. V yậ đã ch ng minh đ ứ ượ ứ ế ề ế ề ẳ ẳ ị ị

Kh ng đ nh th 2 ị ứ : Ta có đ ng th c sau: ẳ ứ ẳ

(cid:246) (cid:230) (cid:247) (cid:231) =- y p 1 . (cid:247) (cid:231) p q ł Ł

Ch ng minh ứ : Theo đ nh th c Newton rút ra: ứ ị

- - (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) = = = = (cid:229) (cid:229) y w w y y , (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) ˛ ˛ x q zp q p q p q ł Ł ł Ł ł Ł ł Ł

V y đi u kh ng đ nh th hai đã đ c ch ng minh. ứ ề ậ ẳ ị ượ ứ

p 2

q 2

p 2

K t h p hai kh ng đ nh trên chúng ta có đ ng th c: ế ợ ứ ẳ ẳ ị - - - - (cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) - (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) -= -= y )1( q )1( =(cid:247) (cid:247) (cid:231) (cid:231) (cid:247) (cid:231) p q q p ł Ł ł Ł ł Ł

2.11 Tính căn b c hai theo modulo s nguyên

ố ậ

2.11.1 Tính căn b c hai theo modulo là s nguyên t ố ậ ố

, thì có 2 ph ng án tính nh sau: Cho p là s nguyên t ố ươ ư

ố 7,3”p 4mod Ph ng án 1 : ươ

pQR

1+ p 4

a ˛ Trong tr ng h p này s . Ta đ nh nghĩa ườ ố p + 1 chia h t cho 4. Cho ế ợ ị x nh sau: ư

, = x a mod p

(

2/)1

+ 2/)1

(

( a p

- - ” ” ” ” B i vì theo tiêu chu n Euler, , nên 12/)1 mod p x a a a a mod p ẩ ở ư ậ . Nh v y

ậ

s ố x là căn b c hai c a ủ a theo modulo p. 5”p 8mod Ph ng án 2 ươ :

Tr ng h p này thì p + 3 chia h t cho 8. B i vì s ( ườ ợ ẩ ố p – 1)/2 là s ch n, s –1 th a mãn tiêu chu n ố ố ẵ ế ở ỏ

pQR

p+ 8

a ˛ Euler và là th ng d b c hai. Cho , ta đ nh nghĩa ư ậ ặ ị x nh sau: ư

= x a (mod p )

2/)1

4/)1

(

4/)3

(

4/)1

( a p

- - - (cid:222) ” – ” ” ” T đi u ki n (cid:222) . 1 mod p 1 mod p x a a a ” a mod p ừ ề ệ

Đi u này ch ng t c đ nh nghĩa trên là căn b c hai c a ứ ề ỏ x đ ượ ị ở ủ a ho c –ặ a. N u nh s d ư ố ươ ế ậ ậ ng thì thu t

toán gi i quy t xong, n u s âm thì: ả ế ố ế

” - ” - x ( x )1 a (mod p )

p+ 1 8 a

D n đ n là s c n tìm. Nh v y bài toán d n đ n tìm . 1- pmod ế ẫ ư ậ ố ầ ế ẫ -= x (mod p )

Cho s p. Nh v y theo tiêu chu n Euler ta có ố b là s không th ng d b c hai theo modulo ư ậ ặ ố ư ậ ẩ

(

2/)1

4/)1

24/)1 )

( - b b

- - - ” ” , nh v y có th thay ( b b 1 mod p 1- pmod mod p ư ậ ể b ng ằ . B i vì ở

pQNR

4/)1

+ = + + = + + - - ˛2 . Mà ta đã bi , nên có th dùng = (12 p p )(1 p )1 8( k 8)(6 k )4 )1"2)(3'4(8 k k t ế ể

(2 -p

thay cho 1-

2 ”

Ngoài ra trong tr ườ ư ứ ng h p t ng quát ta có th tính nh sau: T tiêu chu n Euler, đ ng d th c ợ ổ ư ừ ể ẩ ồ

gi c khi và ch khi a là th ng d b c hai theo modulo p, có nghĩa: x a mod p i đ ả ượ ỉ ư ậ ặ

p 2

- ” a 1 mod p

Gi s r ng đ ng th c cu i cùng là đúng. Cũng có th gi s r ng, chúng ta bi t m t s s ả ử ằ ể ả ử ằ ứ ẳ ố ế ộ ố ố N là

p 2

không th ng d b c hai theo modulo p, có nghĩa là bi ư ậ ặ t ế N v i tính ch t: ấ ớ - - ” N 1 mod p

s21 =

- Gi , l là s l sao cho: p l s ả ử ố ẻ . Chúng ta s tìm dãy s ố ẽ bs- , 1 ..., b 0

22 l ) ba i

-i

” . ( 1 mod p

122)

lba i

0>i Có th đ t . N u nh c và , khai căn, chúng ta nh n đ c r ng ể ặ ế ượ ậ ượ ằ ( =-sb 11 ư ib đã tìm đ

so sánh v i 1 và –1 theo modulo p. Trong tr ng h p th nh t thi , trong tr ớ ườ ứ ấ ợ ế ậ t l p quan h ệ ngườ b i =- 1 b i

p 1 + 12 i

+ 1 2

- =

b i

Nb i

- ” . Cu i cùng ta có , t đây , có nghĩa mod p h p th hai thì ứ ợ ố ừ ” 12 bal 0 ( a ) a mod p b 0

1+ 2

là:

. – ” a mod p x b 0

2.11.2 Tính căn b c hai theo modulo là h p s ợ ố

* x q p Z

nZ đ ng c u v i không gian ớ

2 ”

ậ n = pq Z Chúng ta bi t r ng , p và q là s nguyên t , nhóm . ế ằ ố ố ấ ồ

B i vì đ ng c u đ m b o tính ch t l nh s h c nên x y mod n ấ ệ ố ọ ấ ả ả ở ồ ứ , th a mãn khi và ch khi bi u th c ể ỏ ỉ

p và modulo q. Đi u này có nghĩa n u tri n khai đ c trên đúng v i modulo ớ ề ế ể ậ ượ n ra th a s thì căn b c ừ ố

hai theo modulo n có th tính đ ể ượ c theo thu t toán sau: ậ

Thu t toán 2.1: ậ

pQR

y ˛ Đ u vào 2 s nguyên t . ầ ố ố p, q th a mãn đi u ki n ệ n = pq, s nguyên ề ỏ ố

Đ u ra: Căn b c hai c a ủ y theo modulo n ầ ậ

y (mod p ) xp

y (mod q ) xq

1-= q

return vp * xp + vq * xq mod n

1-= p

(mod ). pp v p

(mod ). qq vq

Thu t toán bình ph ng và nhân ậ ươ

2.12

b mod

= Thu t toán “bình ph ng và nhân” đ tính z x n ậ ươ ể ả . Đây là thu t toán tính hàm mũ hi u qu , ệ ậ

mà trong các ch ng ti p theo chúng ta s áp d ng nó đ tính giá tr hàm mũ đ i v i tr ng h p s ươ ố ớ ườ ụ ế ẽ ể ị ợ ố

mũ l n.ớ

Trong thu t toán này, ta coi r ng s mũ b đ d ng nh phân nh sau: ằ ậ ố ượ c bi u th ể ị ở ạ ư ị

ib 0

b 2 (cid:229)= i

- £ £ 0 i l 1 . Trong đó bi = 0 ho c 1, ặ

b mod

Thu t toán tính: g m các b ậ ồ ướ c nh sau: ư

1. z = 1

2. for i = l – 1 down to 0 do

2= z

3. z mod n

z *= xz mod n 4. if bi = 1 then

Ví dụ : Tính 97263533 mod 11413

3533 = 211+210+28+27+26+23+22+1 = 110111001101

z = 1

i 11 10 9 8 7 6 5 4 3 2 1 0 bi 1 1 0 1 1 1 0 0 1 1 0 1 z mod 11413 12 * 9726 = 9726 97262 * 9726 = 2659 26592 = 5634 56342 * 9726 = 9167 91672 * 9726 = 4958 49582 * 9726 = 7783 77832 = 6298 62982 = 4629 46292 * 9726 = 10185 101852 * 9726 = 105 1052 = 11025 110252 * 9726 = 5761

V y ậ 97263533 mod 11413 = 5761