1 Mục Lục GIỚI THIỆU .............................................................................................................4 Chƣơng 1. MỘT SỐ KHÁI NIỆM CƠ BẢN.........................................................5 1.1. CÁC KHÁI NIỆM CƠSỞ.......................................................................................................5 1.1.1. Một số khái niệm trong toán học ......................................................................... 5 1.1.2. Một số khái niệm trong đại số ............................................................................ 10 1.1.3. Một số khái niệm và Độ phức tạp của thuật toán ............................................ 18 1.2. .................................................................................................................. 21 1.2.1. Khái niệm mã hóa ................................................................................................ 21 1.2.2. Hệ mật mã khóa bí mật ....................................................................................... 23 1.2.3. Một số hệ mật mã cổ điển.................................................................................... 25 1.2.4. .................................................................................. 33 1.3. CHỮKÝ SỐ....................................................................................................................... 38 1.3.1. Khái niệm chữ ký số ............................................................................................ 38 1.3.2. Quá trình tạo ra chữ ký điện tử ......................................................................... 39 1.3.3. Hàm băm sử dụng trong chữ ký điện tử ........................................................... 40 1.3.4. Chữ ký RSA .......................................................................................................... 41 1.3.5. Chữ ký ElGamal................................................................................................... 42 1.3.6. Chữ ký Schnorr (chữ ký một lần) ..................................................................... 43 1.3.7. Các loại chữ ký khác ............................................................................................ 44 Chƣơng 2. CHỮ KÝ “MÙ” VÀ ỨNG DỤNG .......................................................46 2.1. CHỮKÝ “ MÙ” ................................................................................................................. 46 2.1.1. .............................................................................................................. 46 2.1.2. CHỮ KÝ “MÙ” DỰA TRÊN CHỮ KÝ RSA .................................................. 48 2.2. ỨNG DỤNG CỦA CHỮKÝ “MÙ”.......................................................................................... 49 2.2.1. Ứng dụng trong bỏ phiếu trực tuyến ................................................................. 49 2 2.2.2. Ứng dụng chữ ký mù trong tiền điện tử ........................................................... 51 Chƣơng 3: Chƣơng trình thử nghiệm ....................................................................53 3.1. Yêu cầu hệ thống ............................................................................................................ 53 3.2. Các thành phần của chương trình .................................................................................... 53 4.1. Giao diện chương trình ..................................................................................................... 55 4.1.1. Chữ ký RSA .......................................................................................................... 55 4.1.2. Ứng dụng chữ ký “mù” ....................................................................................... 56 KẾT LUẬN ...............................................................................................................57 TÀI LIỆU THAM KHẢO..........................................................................................58 3 LỜI CẢM ƠN Trước hết, em xin gửi lời cảm ơn sâu sắc tới PGS. TS. Trịnh Nhật Tiến đã hướng dẫn em phát triển khóa luận đi từ lý thuyết đến ứng dụng. Sự hướng dẫn của thầy trong suốt thời gian qua đã giúp em tiếp cận tới một hướng nghiên cứu khoa học mới: là nghiên cứu trong lĩnh vực an toàn thông tin. Qua đó, những lý thuyết về an toàn thông tin đã lôi cuốn em và sẽ trở thành hướng nghiên cứu tiếp của em sau khi tốt nghiệp. Em xin bày tỏ lòng biết ơn đến các thầy cô trong trường Đại Dân Lập Hải Phòng đã giảng dạy và cho em những kiến thức quý báu, làm nền tảng để em hoàn thành khóa luận cũng như thành công trong nghiên cứu, làm việc trong tương lai. Cuối cùng, cho em gửi lời cảm ơn sâu sắc tới gia đình, bạn bè đã động viên kịp thời để em học tập tốt và hoàn thành được khóa luận. Em xin chân thành cảm ơn! Hải Phòng, tháng 12 năm 2012 Sinh viên Trần thị chiên 4 GIỚI THIỆU Những năm gần đây, nhu cầu trao đổi thông tin từ xa của con người ngày càng lớn, các ứng dụng trao đổi thông tin qua mạng diễn ra ngày càng nhiều. Tuy nhiên, mỗi loại ứng dụng có những đòi hỏi riêng khác nhau, ví dụ như ứng dụng bầu cử từ xa cần phải che dấu được thông tin người bỏ phiếu, hoặc những văn bản đã được ký nhưng không muốn ai cũng có thể xác thực chữ ký khi chưa được sự đồng ý của người ký. Chữ ký mù đã ra đời để giải quyết vấn đề nêu trên. Ý tưởng chính của ký mù là người ký không biết mình đang ký trên nội dung gì. 5 Chƣơng 1. MỘT SỐ KHÁI NIỆM CƠ BẢN 1.1. CÁC KHÁI NIỆM CƠ SỞ 1.1.1. Một số khái niệm trong toán học 1.1.1.1. Khái niệm về số nguyên tố 1./ Khái niệm Số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó Ví dụ 2, 3, 5… Các hệ mật mã thường sử dụng các số nguyên tố ít nhất là lớn hơn 150 10 . 2./ Một số định lý về số nguyên tố Định lý về số nguyên dƣơng > 1 Mọi số nguyên dương n > 1 đều có thể biểu diễn được duy nhất dưới dạng: n= p1e1 p2e2 …. pkek . ... trong đó: k, ni (i =1,2,..,k) là các số tự nhiên, Pi là các số nguyên tố, từng đôi một khác nhau. Định lý Mersenne Cho p = 2k-1, nếu p là số nguyên tố thì k phải là số nguyên tố. Chứng minh Giả sử k không là nguyên tố. Khi đó k = a.b với 1 < a, b < k. Như vậy p = 2k-1 = 2ab-1 = (2a)b - 1= (2a-1).E (Trong đó E là một biểu thức nguyên - áp dụng công thức nhị thức Newton). Điều này mâu thuẫn giả thiết p là nguyên tố. Vậy giả sử là sai, hay k là số nguyên tố. 6 1.1.1.2. Ƣớc lớn nhất 1./ Ƣớc số Khái niệm: Cho hai số nguyên a, b Z, b 0. Nếu có một số nguyên q sao cho a=b*q, thì ta nói rằng a chia hết cho b, ký hiệu b|a. Ta nói b la ước của a, và a là bội của b. Ví dụ: Cho a=6, b=2, ta có 6=2*3, ký hiệu 2|6. Ở đấy 2 là ước của 6 và 6 là bội của 2. Tính chất: Cho a, b, c Z +a|a. + a|b, b|c a|c. +a|b, b|a a= b. 2./ Ƣớc chung lớn nhất Khái niệm: Số nguyên d được gọi là ước chung của các số nguyên a1, a2,…,an,nếu nó là ước của tất cả các số đó. Một ước chung d > 0 của các số nguyên a1,a2,…,an, trong đó mọi ước chung của a1, a2,…,an, đều là ước của d, thì d được gọi là ước chung lớn nhất (ƯCLN) của a1, a2,…,an. Ký hiệu d = gcd (a1, a2,…,an) hay d = ƯCLN (a1, a2,…,an). Ví dụ: Cho a = 12, b = 15, gcd (12,15) = 3. Tính chất: +d = gcd (a1, a2,…,an) khi và chỉ khi tồn tại các số x1, x2,…,xn sao cho: d = a1x1 + a2x2+ ….+ anxn. Đặc biệt: a1, a2,…,an nguyên số cùng nhau tồn tại các số x1, x2,…,xn sao cho: 1 = a1x1 + a2x2+ ….+ anxn. + d = gcd (a1, a2, …, an) gcd (a1/d, a2/d,…,an/d) = 1. + gcd (m.a1,m. a2,…,m.an) = m* gcd (a1, a2,…,an) (với m ). + Nếu b > 0, a= b.q + r thì gcd (a,b) = gcd (b,r). 7 3./ Thuật toán Euclide tìm ƣớc chung lớn nhất Bài toán: * Dữ liệu vào: Cho hai số nguyên không âm a,b, a b. *Kết quả gcd(a,b). Thuật toán: input(a,b); While b>0 r = a mod b; a = b; b = r; output(a); Ví dụ: a= 30, b= 18 gcd(30,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6 Bảng 1: Mô tả các bước tính gcd(30,18) a b r a = b.q + r 30 18 12 30 = 18*1 + 12 18 12 6 18 = 12*1 + 6 12 6 0 12 = 6*2 + 0 8 1.1.1.3. Hàm Euler Định nghĩa: Cho n được định nghĩa là các số nguyên trong khoảng từ [1.n] nguyên tố cùng nhau với n . hàm được gọi là hàm phi Euler. Tính chất: Nếu p là số nguyên tố thì ) = p-1. Hàm phi Euler là hàm có tính nhân: Nếu n= p1e1 p2e2 …. pkek là thừa số nguyến tố của n thì: =n 1.1.1.4. Khái niệm số nguyên tố cùng nhau Khái niệm: Hai số m và n được gọi là số nguyên tố cùng nhau nếu ước số chung lớn nhất của chúng bằng 1 , ký hiệu gcd (m,n)=1 Ví dụ: 9 và 14 là 2 số nguyên tố cùng nhau. 9 1.1.1.5. Khái niệm số đồng dƣ 1./ Khái niệm Cho a và b là các số nguyên , khi đó a được gọi là đồng dư với b theo modulo n, ký hiệu là a ≡ b mod n nếu a, b chia cho n có cùng số dư. Số nguyên n được gọi là modulo của đồng dư. Kí hiệu: a ≡ b (mod n). Ví dụ: 5 ≡ 7 mod 2 vì: 5 mod 2=1 và 7 mod 2 =1 . 2./ Tính chất của đồng dƣ a ≡ b mod n nếu và chỉ nếu a và b có cùng số dư khi chia cho n. Tính chất phản xạ: a ≡ a mod n. Tính đối xứng: Nếu a ≡ b mod n thì b ≡ a mod n. Tính bắc cầu: Nếu a ≡ b mod n và b ≡ c mod n thì a ≡ c mod n . Nếu a ≡ a1 mod n ,b ≡ b1 mod n thì a + b ≡ (a1+ b1)(mod n ) và ab ≡ (a1 b1) (mod n) 3./ Lớp tƣơng đƣơng Lớp tương đương chủa một số nguyên a là tập hợp các số nguyên đồng dư với a theo modulo n. Cho n cố định đồng dư với n trong không gian Z vào các lớp tương đương. Nếu a = qn + r, trong đó 0 ≤ r ≤ n thì a ≡ r mod n. vì vậy mỗi số nguyên a là đồng dư theo modulo n với duy nhất một số nguyên trong khoảng từ 0 đến n-1 và được gọi là thặng dư nhỏ nhất của a theo modulo n. Cũng vì vậy, a và r cùng thuộc một lớp tương. Do đó r có thể đơn giản được dùng để thể hiện lớp tương đương. 10 1.1.2. Một số khái niệm trong đại số 1.1.2.1. Khái niệm nhóm, nhóm con, nhóm Cyclic -Nhóm là bộ phận các phần tử (G, *) thõa mãn các tính chất sau: +Tính chất kết hợp: ( x * y ) * z = x * ( y * Z) +Tính chất tồn tại phần tử trung gian e ∈ G: e * x=x *e =x, ∀ x ∈ G +Tính chất tồn tại của phần tử nghịch đảo x’ ∈ G: x’ * x=x * x’ = e -Nhóm con là bộ các phần tử ( S, * ) là nhóm thõa mãm các tính chất sau: + S ∈ G là phần tử trung gian e ∈ S +x, y ∈ S => x * y ∈ S -Nhóm Cyclic: là nhóm mà mọi phần tử của nó được sinh ra từ một phần tử đặc biệt g ∈ G . Phần tử này được gọi là phần tử nguyên thủy, tức: Với ∀ x ∈ G: mà g n =x. Ví Dụ: (Z+, * ) là một nhóm cyclic có 1 phần tử sinh là 1. 1.1.2.2. Phần tử nghich đảo 1./ Định nghĩa Cho a ∈ Zn. Nghịch đảo nhân của a theo modulo n là một số nguyên x ∈ Zn sao cho a*x mod n. Nếu tồn tại, thì đó là giá trị duy nhất và a được gọi là khả nghịch. Nghịch đảo của a ký hiệu là a -1. 2./ Tính chất -Cho a, b ∈ Zn. Phép chia của a cho b theo modulo n là tích của a và b-1 theo modulo n và chỉ được xác định khi b có nghịch đảo theo modulo n. -Cho a ∈ Zn, a nghịch đảo khi và chỉ khi (a,n) =1. -Giả sử d= (a,n). Phương trình đồng dư ax có nghiệm x nếu và chỉ nếu d chia hết cho b, trong trường hợp các nghiệm d nằm trong khoảng 0 đến n-1 thì các nghiệm đồng dư theo modulo n/d. 3./ Ví dụ: Z25 = {0, 1, 2, 3,…, 24}. Trong Z25: 13 + 16 = 4, vì 13 +16 = 29 4 (mod 25). Tương tự: 13*16 = 8 trong Z25. 11 4./ Các phép toán trong không gian modulo Cho n là các số nguyên dương. Các phần tử trong Zn được thể hiện bởi các số nguyên{0, 1, 2, 3,…,n-1}. Nhận xét rằng: nếu a, b Zn thì: (a + b) mod n = Vì vậy, phép cộng modulo (và phép trừ modulo ) có thể được thực hiện mà không cần thực hiện các phép chia dài. Phép nhân modulo của a và b được thực hiện bằng phép nhân thông thường a với b như các số nguyên bình thường, sau đó lấy phần dư của kết quả sau khi chia cho n. Phép tính nghịch đảo trong Zn có thể được thực hiện nhờ sử dụng thuật toán Euclid mở rộng. 1.1.2.3. Phần tử nghịch đảo trong Zn Định nghĩa: Cho a Zn , nghịch đảo của a là số nguyên b Zn sao cho a.b 1 (mod n), -1 ta nói b là phần tử nghịch đảo của a trong Zn và ký hiệu là a . Một phần tử có phần tử nghịch đảo, gọi là khả nghịch. Tính chất: + Cho a, b Zn , a/b (mod n) = a.b-1 (mod n) được xác định khi và chỉ khi b là khả nghịch theo modulo của n. +a Zn , a là khả nghịch khi và chỉ khi gcd(a, n) = 1. Chứng minh: Nếu a.a-1 1 (mod n) thì a.a-1 1 + kn a.a-1 - kn = 1 (a,n) = 1. Nếu (a,n) = 1, ta có a.a-1 = 1 + kn a.a-1 + kn, do đó a.a-1 1 (mod n). 12 Ví dụ: Các phần tử khả nghịch trong Z9 là 1, 2, 4, 5, 7 và 8. 1-1 = 1 vì 1*1 1 (mod 9). 2-1 = 5 vì 2*5 1 (mod 9). 4-1 = 7 vì 4*7 1 (mod 9). 8-1 = 8 vì 8*8 1 (mod 9). Cho d = gcd(a,n).Khi đó phương trình đồng dư có dạng a.x b (mod n) sẽ có nghiệm x khi và chỉ khi d chia hết cho b. Tìm phần tử nghịch đảo bằng thuật toán Euclid mở rộng: Bài toán: + Dữ liệu vào: a Zn , n. + Kết quả: Phần tử nghịch đảo của a Thuật toán: Input(a,n); Begin g0 = n; g1 = a; u0 = 1; u1 = 0; v0 = 0; v1 = 1; i = 0; while gi 0 { y = gi-1 / gi ; gi+1 = gi+1 – y.gi ; ui+1 = ui+1 – y.ui ; vi+1 = vi+1 – y.vi ; i = i +1; } t = vi+1 ; if t > 0 then a-1 = t else a-1 = t + n; End; 13 Ví dụ: Tìm phần tử nghịch đảo của 3 trong Z7 Tức là ta phải giải phương trình 3.x 1 (mod 7), x sẽ là phần tử nghịch đảo của 3. i gi ui vi y 0 7 1 0 1 3 0 1 2 2 1 1 -2 3 3 0 Vì t = v2 = -2 < 0 do đó x = x= a-1 = t + n = -2 + 7 = 5. Vậy 5 là phần tử nghịch đảo của 3 trong Z7 . Chú ý: Số mũ modulo có thể được tính một cách hiệu quả bằng thuật toán bình phương và nhân liên tiếp, nó được sử dụng chủ yếu trong nhiều giao thức mã hóa. Một phiên bản của thuật toán này như sau: Giả sử biểu diễn nhị phân của k là: với ki {0,1} 14 Thuật toán bình phƣơng liên tiếp để tính số mũ modulo trong Zn: Bài toán: + Dữ liệu vào: a Zn và số nguyên dương 0 k n trong đó k có biểu diễn nhị phân là: k = + Kết quả: ak mod n. Thuật toán: Readln(a,n); Begin b:=1; if k = 0 then writeln(b); A:= a; if k0 = 1 then b:= a; for i = 1 to n begin A:= A*A mod n; if ki=0 then b:= A*b mod n; end; writeln(b); End; Ví dụ: Tính số mũ modulo Bảng 2: Mô tả các bước tính 5596 mod (1234) = 1013 I 0 1 2 3 4 5 6 7 8 9 ki 0 0 1 0 1 0 1 0 0 1 A 5 25 625 681 1011 369 421 799 947 925 B 1 1 625 625 67 67 1059 1059 1059 1013 15 1.1.2.4. Nhóm nhân Zn* 1/.Định nghĩa Nhóm nhân (phép nhân) của tập Zn ký hiệu là Zn* = {a Zn | gcd(a,n) = 1}. Đặc biệt, nếu n là một số nguyên tố thì Zn* = {a|1 a n-1}. 2/.Định nghĩa cấp của Zn* Cấp của Zn* được định nghĩa là số phần tử trong Zn* , (| Zn* |). Theo định nghĩa hàm phi – Euler ta có | Zn* | = (n). 3/.Tính chất Cho n 2 là số nguyên: + Định lý Euler: Nếu a Zn* thi 1 (mod n). +Nếu n là tích của các số nguyên tố phân biệt và nếu r s(mod (n)) thì ar as (mod n) với mọi số nguyên a. Nói cách khác, làm việc với các số theo modulo nguyên tố p thì số mũ có thể giảm theo modulo (n). Cho p là số nguyên tố: + Định lý Fermat: Nếu gcd(a,p) = 1 thì ap-1 1 (mod p). + Nếu r s (mod p-1) thì ar = as (mod p) với mọi số nguyên a.Nói cách khác, làm việc với các số theo modulo nguyên tố p thì số mũ có thể giảm theo modulo p-1. + ap a (mod p) với mọi số nguyên a. 16 1.1.2.5. Phần tử sinh 1/. Định nghĩa Cho a Zn* , nếu cấp của là (n) ,khi đó gọi là phần tử sinh hay phần tử nguyên thủy của Zn ,và nếu Zn có một phần tử sinh,thì Zn* được gọi là nhóm * * cyclic.(chú ý nếu là số nguyên tố thì (n) = n-1). 2/. Tính chất: + Nếu là phần tử sinh của Zn* thì Zn* = { (mod n) | 0 i (n)-1}. + Giả sử là một phần tử sinh của Zn* .Khi đó , b = mod n cũng là một phần tử sinh của Zn* khi và chỉ khi gcd(i, (n)) = 1 .Và sau đó nếu Zn* là nhóm cyclic thì số phần tử sinh sẽ là ( (n)). + Zn* là phần tử sinh của Zn* khi và chỉ khi ! 1 (mod n) với mỗi số chia nguyên tố của (n). + Zn* có phần tử sinh khi và chỉ khi n = 2, 4, hay 2 khi p là số nguyên tố lẻ và k 1. Còn nếu p là số nguyên tố thì chắc chắn có phần tử sinh. 1.1.2.6. Thặng dƣ 1./ Định nghĩa Cho a Zn* , a được gọi là thặng dư bậc hai theo modulo n hoặc bình phương theo modulo n, nếu tồn tại một x Zn* , sao cho x2 a (mod n), và nếu không tồn tại x như vậy thì a được gọi là bất thặng dư bậc hai theo modulo n. Tập các thặng dư bậc hai ký hiệu là . Chú ý: Vì định nghĩa 0 Zn* nên 0 Qn và 0 . 2./ Tính chất Cho n là tích của hai số nguyên tố p và q. Khi đó, a Zn* là một thặng dư bậc 2 theo modulo n khi và chỉ khi a Qn và a . Ta có: |Qn | = |Qp|.|Qq| = (p-1)(q-1)/4 và | | = 3(p-1)(q-1)/4. 3./ Ví dụ Cho n = 21. Khi Q21 = {1, 4, 16} và = {2, 5, 8, 10, 11, 13, 17, 19, 20 17 1.1.2.7. Hàm một phía và hàm một phía có cửa sập Hàm một phía: Một hàm một phía là hàm mà dễ dàng tính toán ra quan hệ một chiều nhưng rất khó để tính ngược lại. Ví dụ: Biết giả thiết x thì có thể dễ dàng tính ra f(x), nhưng nếu biết f(x) thì khó tính ra được x. Trong trường hợp này “khó” có nghĩa là để tính ra được kết quả thì phải mất nhiều thời gian để tính toán. Ví dụ: Tính y = f(x)=ax mod p là dễ tính nhưng tính ngược lại x = loga y là bài toán “khó” (bài toán logarit rời rạc). Hàm một phía có cửa sập: F(x) được gọi là hàm một phía có cửa sập nếu tính xuôi y = f(x) thì dễ tính ngược x= f-1 (y ) thì khó tuy nhiên nếu có “ cửa sập” thì vấn đề tính ngược trở nên dễ dàng. Cửa sập ở đây là một điều kiện nào đó giúp chúng ta dễ dàng tính ngược. Ví dụ: Y=f(x)=xb mod n tính xuôi thì dễ nhưng tính ngược x = ya mod n thì khó vì phải biết a với a * b =1 (mod ( )) trong đó ) =( p-1)*(q-1). Nhưng nếu biết Cửa sập p, q thì việc tính n= p*q và tính a trở nên dễ dàng. Hộp thư là một ví dụ khác về hàm một phía có cửa sâp. Bất kỳ ai cũng có thể bỏ thư vào thùng. Bỏ thư vào thùng là một hành động công cộng. Mở thùng thư không phải hành động công cộng. Nó là khó khăn, bạn sẽ cần đến mỏ hàn để phá hoặc những công cụ khác. Tuy nhiên, nếu bạn có “ cửa sập” ( trong trường hợp này là chìa khóa của hòm thư) thì công việc mở hòm thư thật dễ dàng. 18 1.1.3. Một số khái niệm và Độ phức tạp của thuật toán 1.1.3.1. Khái niệm thuật toán 1. Khái niệm bài toán Bài toán được diễn đạt bằng hai phần: - Input: Các dữ liệu vào của bài toán. - Output: Các dữ liệu ra của bài toán (kết quả). 2. Khái niệm thuật toán - “Thuật toán” được hiểu đơn giản là cách thức để giải một bài toán. Cũng có thể được hiểu bằng hai quan niệm: Trực giác hay Hình thức như sau: + Quan niệm trực giác về “Thuật toán” Một cách trực giác, thuật toán được hiểu là một dãy hữu hạn các qui tắc (chỉ thị, mệnh lệnh) mô tả một quá trình tính toán, để từ dữ liệu đã cho (Input) ta nhận được kết quả (Output) của bài toán. + Quan niệm toán học về ”Thuật toán” Một cách hình thức, người ta quan niệm thuật toán là một máy Turing. - Thuật toán được chia thành hai loại: Đơn định và không đơn định. + Thuật toán đơn định (Deterministic): Là thuật toán mà kết quả của mọi phép toán đều được xác định duy nhất. + Thuật toán không đơn định (Non - deterministic): Là thuật toán có ít nhất một phép toán mà kết quả của nó là không duy nhất. 19 1.1.3.2. Khái niệm độ phức tạp của thuật toán 1/. Chi phí của thuật toán (tính theo một bộ dữ liệu vào) Chi phí phải trả cho một quá trình tính toán gồm chi phí về thời gian và bộ nhớ. - Chi phí thời gian của một quá trình tính toán là thời gian cần thiết để thực hiện một quá trình tính toán. Với thuật toán tựa Algol: Chi phí thời gian là số các phép tính cơ bản thực hiện trong quá trình tính toán . - Chi phí bộ nhớ của một quá trình tính toán là số ô nhớ cần thiết để thực hiện một quá trình tính toán. Gọi A là một thuật toán, e là dữ liệu vào của bài toán đã được mã hoá bằng cách nào đó. Thuật toán A tính trên dữ liệu vào e phải trả một giá nhất định. Ta ký hiệu: tA (e) là giá thời gian và lA(e) là giá bộ nhớ. 2/. Độ phức tạp về bộ nhớ (trong trƣờng hợp xấu nhất) lA(n) = max{l A (e), với |e| }. (n là kích thước đầu vào của thuật toán) 3/. Độ phức tạp thời gian (trƣờng hợp xấu nhất) tA(n) = max{tA(e), với |e| } 4/. Độ phức tạp tiệm cận Độ phức tạp PT(n) được gọi là tiệm cận tới hàm f(n), ký hiệu O(f(n)) nếu các số n0 , c mà PT(n) ư c.f(n) , no. 5/. Độ phức tạp đa thức Độ phức tạp PT(n) được gọi đa thức, nếu nó tiệm cận tới đa thức p(n). 20 6/. Thuật toán đa thức - Thuật toán được gọi là đa thức nếu độ phức tạp về thời gian trong trường hợp xấu nhất của nó là đa thức. - Nói cách khác: + Thuật toán thời gian đa thức: là thuật toán có độ phức tạp là O(nt) trong đó t là hằng số. + Thuật toán thời gian hàm mũ: là thuật toán có độ phức tạp O(tf(n)) trong đó t là hằng số và f(n) là hàm đa thức của n. - Thời gian chạy của các lớp thuật toán khác nhau: Độ phức tạp Số phép tính(n=106) Thời gian(106phép tính/s) O(1) 1 1micro giây O(n) 106 1 giây O(n2) 1012 11,6 ngày O(n3) 1018 32 000 năm O(2n) 10301030 10301006 tuổi của vũ trụ - Có người cho rằng ngày nay máy tính với tốc độ rất lớn, không cần quan tâm nhiều tới thuật toán nhanh, chúng tôi xin dẫn một ví dụ đã được kiểm chứng. Bài toán xử lý n đối tượng, có ba thuật toán với 3 mức phức tạp khác nhau sẽ chịu 3 hậu quả như sau: Sau 1 giờ: + Thuật toán A có độ phức tạp O(n): 3,6 triệu đối tượng. + Thuật toán B có độ phức tạp O(nlog n): 0,2 triệu đối tượng. + Thuật toán C có độ phức tạp O(2n): 21 đối tượng.