�ݺ�ߣ

Bảo Mật Thông Tin
Trần Nhật Quang
Khoa Công Nghệ Thông Tin – ĐH Sư Phạm Kỹ Thuật TP HCM
trannhatquang4810@gmail.com

Bảo Mật Thông Tin Chương 5. Lý Thuyết Số (tt) 2
 Thuật toán Euclid
 Thuật toán Euclid mở rộng
Các Nội Dung

 (Nhắc lại: Lý thuyết số nghiên cứu các số nguyên. Vì vậy
các số ở đây đều là số nguyên.)
 Ước số chung lớn nhất (Greatest Common Divisor - gcd)
của 2 số a, b là số lớn nhất chia hết cả a và b.
 Ký hiệu: gcd(a, b) hay (a, b)
 Thuật toán Euclid rất hiệu quả để tìm gcd.
Ước Số Chung Lớn Nhất

 Thuật toán Euclid được dùng để tìm ước chung lớn nhất.
 Ta có phép chia a/b:
a = q.b + r
 Nếu số d: d|a và d|b  d|r
 Nên: gcd( a, b) = gcd( b, r)
 Thuật toán Euclid: Giả sử a ≥ b > 0
 Đặt g0 = a, g1 = b
 Lặp tìm số dư: gi+1 = gi-1 mod gi (gi +1 là số dư của gi-1 cho gi
)
Cho đến khi gk+1 = 0
 Lúc đó: (a,b) = gk
Thuật Toán Euclid

 Ví dụ 1: Tìm (8, 6)
 (8, 6) = (6, 2) = (2, 0)
 Hay: 8620
  (8, 6) = 2
 Ví dụ 2: Tìm (128, 48)
 (128, 48) = (48, 32) = (32, 16) = (16, 0)
 Hay: 1284832160
  (128, 48) = 16
Ví Dụ Thuật Toán Euclid

Bảo Mật Thông TinChương 5. Lý Thuyết Số (tt) 6

 Dùng để tìm số nghịch đảo a-1 mod n của số a.
 a-1 là nghịch đảo của a theo mod n nếu a.a-1 = 1 mod n
 Ví dụ: 3.7 = 1 mod 10  7 = 3-1 mod 10
 Nếu (a, n) = 1 thì luôn  nghịch đảo của a theo mod n (điều
kiện để dùng Euclid mở rộng).
 Sử dụng thuật toán Euclid mở rộng để
tìm các giá trị gi ,ui ,vi sao cho gi = ui.n + vi.a.
(v y gi n 1)
 Từ 1 = uk.n + vk.a suy ra vk là nghịch đảo của a
vì uk.n + vk.a mod n = vk.a mod n.
Thuật Toán Euclid Mở Rộng

 g0 = n, u0 = 1, v0 = 0 : g0 = u0 . n + v0 . a
 g1 = a, u1 = 0, v1 = 1 : g1 = u1 . n + v1 . a
• y = g0 div g1 (chia lấy nguyên)
g0 = u0 . n + v0 . a
g1 = u1 . n + v1 . a X y
---------------------------------------
(g0 – y. g1) = (u0 – y. u1) . n + (v0 – y. v1) . a
 g2 = u2 . n + v2 . a (g2 = g0 mod g1)
• y = g1 div g2
(g1 – y. g2) = (u1 – y. u2) . n + (v1 – y. v2) . a
 g3 = u3 . n + v3 . a
…………..
Đến khi gk+1 = 0 ta có gk = gcd(a,n) = 1  vk =a-1(mod n)
Thuật Toán Euclid Mở Rộng (2)

 TT tìm nghịch đảo của a theo mod n ((a,n)=1, n>a>0)
(nếu a > n  lấy a = a mod n)
• g0 = n, u0 = 1, v0 = 0
• g1 = a, u1 = 0, v1 = 1
• Lặp:
y = gi-1 div gi
gi+1 = gi-1 mod gi
ui+1 = ui-1 – y . ui
vi+1 = vi-1 – y . vi
• Đến khi gk = 1 ta có vk = a-1 mod n
Thuật Toán Euclid Mở Rộng (3)

Tìm 3-1 mod 460: a=3, n=460
i y g u(n) v(a) Đẳng thức tương đương
0 - 460 1 0 460 = 1*460 + 0*3
1 - 3 0 1 3 = 0*460 + 1*3
2 153 1 1 -153 1 = 1*460 + -153*3
Ở đây k=2. Vậy: 3-1 mod 460 = -153 = 307 mod 460
 Tìm 299-1 mod 323: a=299, n=323:
i y g u(n) v(a) Đẳng thức tương đương
0 - 323 1 0 323 = 1.323 + 0.299
1 - 299 0 1 299 = 0.323 + 1.299
2 1 24 1 -1 24 = 1.323 + -1.299
3 12 11 -12 13 11 = -12.323 + 13.299
4 2 2 25 -27 2 = 25.323 + -27.299
5 5 1 -137 148 1 = -137.323 + 148.299
Vậy: 299-1 mod 323 = 148
Ví Dụ

 Tìm 299-1mod 323: (a=299, n=323)
y g v
- 323 0
- 299 1
1 24 -1
12 11 13
2 2 -27
5 1 148
Vậy: 299-1 mod 323 = 148
Giải Thuật Rút Gọn

 Tập số dư đầy đủ theo mod n: [0..n-1]
 Tập số dư rút gọn theo mod n: chỉ gồm các số trong
[0..n-1] nguyên tố cùng nhau với n.
 Ví dụ: n = 10
 Tập số dư đầy đủ: {0,1,2,3,4,5,6,7,8,9}
 Tập số dư rút gọn: {1,3,7,9}
 Số phần tử trong tập số dư rút gọn gọi là hàm phi Euler.
Ký hiệu: φ(n)
 Ví dụ: φ(10) = 4
Hàm Phi Euler

 Một số tính chất của φ(n):
 Nếu n là số nguyên tố thì: φ(n) = n-1
 Nếu n là số nguyên tố thì: φ(nr) = nr-1(n-1)
 : φ(a.b) = φ(a).φ(b)
 Phân tích n thành thừa số nguyên tố: n = pa. qb... (p, q… là
số nguyên tố)  φ(n) = φ(pa. qb... ) = φ(pa). φ(qb)…
 Ví dụ: φ(2000) = φ(2.103) = φ(2.23.53) = φ(24.53) =
φ(24).φ(53) = 23.(2-1) . 52.(5-1) = 800
Hàm Phi Euler (2)

 Định lý nhỏ Fermat
 Giả sử p là số nguyên tố và (a,p)=1
 Khi đó: ap-1 = 1 mod p
 Định lý Euler
 Là trường hợp tổng quát của định lý Fermat
 Với mọi số nguyên dương n và (a,n)=1
 Khi đó: aφ(n) = 1 mod n
 Bây giờ ta có vài cách tính nghịch đảo a-1 mod n
1. Lần lượt tìm 1,...,n-1 số a-1 sao cho: a.a-1 = 1 mod n
2. Sử dụng thuật toán Euclid mở rộng để tìm số nghịch
đảo
3. Nếu đã biết φ(n) thì từ định lý Euler ta tìm được:
a-1 = aφ(n)-1 mod n
Định Lý Nhỏ Fermat Và Định Lý Euler

 Ta thường cần tìm các số nguyên tố rất lớn.
 Phương pháp cổ điển: sàng Erastosthene. (Cách này chỉ dùng
để tìm các số nguyên tố không lớn lắm).
 Ta có thể kiểm tra (gần đúng) số nguyên tố bằng định lý nhỏ
Fermat: an-1 = 1 mod n với (a,n)=1
 Tất cả các số nguyên tố ‘n’ đều thỏa đẳng thức trên
 Một vài hợp số (số không phải số nguyên tố) cũng thỏa
đẳng thức trên. Các hợp số đó gọi là các GIẢ NGUYÊN TỐ.
 Để đoán 1 số n nào đó là số nguyên tố hay không, ta làm test
sau:
 Chọn số lượng lớn (ví dụ: 100) các số ‘a‘ sao cho: (a,n)=1
 Kiểm tra: an-1 = 1 mod n ?
• Nếu có 1 số a nào đó không thỏa thì n không là số nguyên tố
• Nếu thỏa cho tất cả các giá trị a có thể kết luận gần đúng rằng n là
số nguyên tố (95%)
Tìm Các Số Nguyên Tố Lớn

 Tính các logarit rời rạc sau:
 2x = 3 mod 5; 4x = 2 mod 13; 5x = 3 mod 7;
 6x = 10 mod 11; 7x = 3 mod 13; 8x = 3 mod 11
 Tính ƯSCLN (gcd):
 (65,91); (102,238); (110,154); (171,285); (185,259)
 Tính hàm phi Euler φ(n) của:
 57, 61, 65, 79, 83, 85, 2012, 323
 Tính số nghịch đảo sử dụng 1 trong các cách sau:
 Thử sai; Định lý Euler; TT Euclid mở rộng
 11-1 mod 35; 13-1 mod 48;
 17-1 mod 199; 21-1 mod 197;
Bài Tập

*1+ Đặng Trường Sơn, BMTT_06_NumberTheory.ppt, ĐH Sư
Phạm Kỹ Thuật TP HCM.
[2] William Stallings, Cryptography and Network Security
Principles and Practices, Fourth Edition, Prentice Hall,
November 16, 2005.
[3] Dương Anh Đức và Trần Minh Triết, Mã hóa và ứng
dụng, Đại học Quốc gia thành phố Hồ Chí Minh, 2005.
[4] http://vi.wikipedia.org/wiki/Giải_thuật_Euclid
*5+ http://vi.wikipedia.org/wiki/Định_lý_nhỏ_Fermat
Tài Liệu Tham Khảo

�ݺ�ߣ

07 chương 5. lý thuyết số (2)

More Related Content

07 chương 5. lý thuyết số (2)