LUẬN VĂN TỐT NGHIỆP NGHIÊN CỨU, TÌM HIỂU VÀ TRÌNH BÀY VỀ CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG Elliptic, ỨNG DỤNG CỦA ĐƯỜNG CONG Elliptic TRONG HỆ THỐNG BỎ PHIẾU ĐIỆN TỬ VÀ HỆ THỐNG TIỀN ĐIỆN TỬ.

Chia sẻ: Lan Lan | Ngày: | Loại File: PDF | Số trang:61

Thêm vào BST

Báo xấu

323
lượt xem 109
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Lời đầu tiên, em xin được gửi lời cảm ơn sâu sắc tới PGS.TS. Trịnh Nhật Tiến, người thầy đã giúp đỡ em trong suốt quá trình làm khóa luận, đồng thời cũng là người thầy đã hướng dẫn em những bước đi đầu tiên để khám phá một lĩnh vực đầy bí ẩn và thách thức – lĩnh vực an toàn và bảo mật dữ liệu. Em xin được cảm ơn các thầy, các cô đã giảng dạy em trong suốt bốn năm qua. Những kiến thức mà các thầy, các cô đã dạy sẽ mãi là hành trang...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: LUẬN VĂN TỐT NGHIỆP NGHIÊN CỨU, TÌM HIỂU VÀ TRÌNH BÀY VỀ CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG Elliptic, ỨNG DỤNG CỦA ĐƯỜNG CONG Elliptic TRONG HỆ THỐNG BỎ PHIẾU ĐIỆN TỬ VÀ HỆ THỐNG TIỀN ĐIỆN TỬ.

TRƯỜNG……………………… KHOA…………………………….. LUẬN VĂN TỐT NGHIỆP NGHIÊN CỨU, TÌM HIỂU VÀ TRÌNH BÀY VỀ CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG Elliptic, ỨNG DỤNG CỦA ĐƯỜNG CONG Elliptic TRONG HỆ THỐNG BỎ PHIẾU ĐIỆN TỬ VÀ HỆ THỐNG TIỀN ĐIỆN TỬ. 1
LỜI CẢM ƠN Lời đầu tiên, em xin được gửi lời cảm ơn sâu sắc tới PGS.TS. Trịnh Nhật Tiến, người thầy đã giúp đỡ em trong suốt quá trình làm khóa luận, đồng thời cũng là người thầy đã hướng dẫn em những bước đi đầu tiên để khám phá một lĩnh vực đầy bí ẩn và thách thức – lĩnh vực an toàn và bảo mật dữ liệu. Em xin được cảm ơn các thầy, các cô đã giảng dạy em trong suốt bốn năm qua. Những kiến thức mà các thầy, các cô đã dạy sẽ mãi là hành trang giúp em vững bước trong tương lai . Em cũng xin được cảm ơn tập thể lớp K50CC, một tập thể lớp đoàn kết với những người bạn không chỉ học giỏi mà còn luôn nhiệt tình giúp đỡ mọi người, những người bạn đã giúp đỡ em trong suốt bốn năm học tập trên giảng đường Đại học. Cuối cùng, em xin được gửi lời cảm ơn sâu sắc tới gia đình em, những người luôn kịp thời động viên, khích lệ em, giúp đỡ em vượt qua những khó khăn trong cuộc sống. Hà nội, tháng 05 năm 2009 Sinh viên Nguyễn Minh Hải 2
TÓM TẮT NỘI DUNG KHÓA LUẬN Khóa luận là sự nghiên cứu, tìm hiểu và trình bày về chữ ký số trên đường cong Elliptic, ứng dụng của đường cong Elliptic trong Hệ thống bỏ phiếu điện tử và Hệ thống tiền điện tử. Khóa luận được trình bày thành bốn chương với nội dung như sau: Chương 1 : Tóm tắt các khái niệm cơ bản trong số học và trong đại số học. Chương 2 : Trình bày về khái niệm đường cong Elliptic, các dạng đường cong và các phép toán trên đường cong Elliptic. Chương 3 : Trình bày một số chữ ký số trên đường cong Elliptic và phương pháp tấn công hệ mã hóa đường cong Elliptic. Chương 4 : Trình bày ứng dụng của đường cong Elliptic trong Hệ thống bỏ phiếu điện tử và Hệ thống tiền điện tử. 3
CÁC KÝ HIỆU VIẾT TẮT Người gửi tin hoặc người thực hiện việc ký Tom BĐK Ban đăng ký Ban kiểm phiếu BKP Người nhận tin hoặc người yêu cầu ký Jerry Đường cong Elliptic (Elliptic Curve) EC Mã hóa đường cong Elliptic (Elliptic Curve Cryptosystem) ECC Thuật toán ký trên EC ECDSA Bài toán Logarith rời rạc trên EC EDLP Bỏ phiếu điện tử (Electronic Voting) E-Voting Ước số chung lớn nhất (Greatest Common Divisor) gcd Trường hữu hạn (Galois Field) GF IEEE Institute of Electrical and Electronics Engineers IETF Internet Engineer Task Force Bài toán ước số nguyên (Integer Factorization Problem) IFP Bội số chung nhỏ nhất (Least Common Multiple) lcm Phương pháp tấn công Menezes – Okamoto - Vanstone MOV NIST National Institute of Standards RFC Request For Comments Hàm băm 160 bit RIPEMD-160 Hệ mã hóa khóa công khai Rivest – Shamir – Adleman RSA Hàm cửa sập một chiều (Trapdoor One-way Function) TOF 4
CÁC KÝ HIỆU TOÁN HỌC Nhóm cyclic được sinh bởi g Số phần tử của đường cong elliptic #E Tập các bản mã có thể C Thuật toán giải mã dK Đường cong elliptic E Thuật toán mã hóa eK Nhóm nhân trên trường F F* Trường hữu hạn với q phần tử Fq Điểm cơ sở của E G K Không gian các khóa Phần tử trung hòa của E O Thuật toán ký số sigK Thuật toán kiểm tra chữ ký verK Vành các số nguyên dương p Zp φ(n) Hàm phi Euler các số nguyên trong Zn nguyên tố cùng nhau với n. 5
DANH MỤC CÁC HÌNH VẼ TRONG KHÓA LUẬN Hình 1: Một ví dụ về đường cong Elliptic................................ ....... Error! Bookmark not defined. Hình 2: Điểm ở vô cực ................................ ................................ ... Error! Bookmark not defined. Hình 3: Phép cộng trên đường cong elliptic ................................ .... Error! Bookmark not defined. Hình 4: Phép nhân đôi trên đường cong elliptic .............................. Error! Bookmark not defined. 6
MỤC LỤC LỜI MỞ ĐẦU ................................ ................................ ................................ .............................. 1 Chương 1 : CÁC KHÁI NIỆM CƠ BẢN ................................ ................................ .................. 11 1.1. KHÁI NIỆM TRONG SỐ HỌC ................................ ................................ .......................... 11 1.1.1. Ước chung lớn nhất và bội chung nhỏ nhất ................................ ................................ ....... 11 1.1.2. Quan hệ đồng dư ................................ ................................ ................................ ................ 12 1.1.3. Số nguyên tố ................................ ................................ ................................ ..................... 13 1.2. KHÁI NIỆM TRONG ĐẠI SỐ ................................ ................................ ............................ 15 1.2.1. Nhóm ................................ ................................ ................................ ................................ 15 1.2.2. Vành ................................ ................................ ................................ ................................ .. 17 1.2.3. Trường ................................ ................................ ................................ .............................. 18 1.2.4. Không gian vector ................................ ................................ ................................ ............ 22 Chương 2. ĐƯỜNG CONG ELLIPTIC ................................ ................................ .................... 23 2.1. CÔNG THỨC WEIERSTRASSE VÀ ĐƯỜNG CONG ELLIPTIC ................................ ....... 24 2.2. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG R2 ................................ ................................ . 24 2.2.1. Phép cộng ................................ ................................ ................................ .......................... 25 2.2.2. Phép nhân đôi................................ ................................ ................................ ..................... 28 2.3. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠN ................................ ................... 29 2.3.1. Đường cong elliptic trên trường Fp (p là số nguyên tố) ................................ ........................ 29 2.3.2. Đường cong elliptic trên trường F2m................................ ................................ .................... 30 2.3.3. Các phép toán trên đường cong elliptic trong hệ tọa độ Affine ................................ ............ 30 2.3.4. Các phép toán trên đường cong elliptic trong hệ tọa độ chiếu ................................ .............. 32 2.3.5. Chuyển đổi giữa hệ tọa độ Affine và hệ tọa độ chiếu ................................ .......................... 33 2.3.6. Các phép toán đường cong trong hệ tọa độ chiếu ................................ ................................ 33 2.3.6. Phép nhân đường cong ................................ ................................ ................................ ....... 34 2.4 BÀI TOÁN LOGARIT RỜI RẠC TRÊN ĐƯỜNG CONG ELLIPTIC ................................ ... 36 Chương 3. CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTC................................ .................... 37 3.1. CHỮ KÝ SỐ ................................ ................................ ................................ ........................ 37 3.1.1. Khá i niệm chữ ký số ................................ ................................ ................................ ......... 37 3.1.2. Sơ đồ chữ ký số ................................ ................................ ................................ ................ 38 3.2. MỘT SỐ SƠ ĐỒ CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC ................................ ...... 41 3.2.1. Sơ đồ chữ ký ECDSA ................................ ................................ ................................ ...... 41 3.2.2. Sơ đồ chữ ký Nyberg- Rueppel ................................ ................................ ........................ 43 3.2.3. Sơ đồ chữ ký mù Harn trên EC ................................ ................................ ......................... 44 7
3.2.4. Sơ đồ đa chữ ký mù của Harn trên EC ................................ ................................ ............. 47 3.3. MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG HỆ ECC ................................ ................................ 49 3.3.1. Phương pháp tấn công “baby - step giant - step” ................................ ............................... 49 3.3.2. Phương pháp tấn công MOV ................................ ................................ ............................ 50 Chương 4 . ỨNG DỤNG CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC .......................... 53 4.1.ỨNG DỤNG TRONG BỎ PHIẾU ĐIỆN TỬ ................................ ................................ ......... 54 4.1.1. Quy trình bỏ phiếu điện tử ................................ ................................ ................................ 54 4.1.2. Sử dụng ECC trong bỏ phiếu điện tử................................ ................................ ................. 55 4.2. ỨNG DỤNG TRONG HỆ THỐNG TIỀN ĐIỆN TỬ ................................ .......................... 57 4.2.1. Tạo tiền ecash ................................ ................................ ................................ ................... 57 4.2.2 Tiêu tiền ecash ................................ ................................ ................................ .................. 58 4.2.3 Đổi tiền ................................ ................................ ................................ .............................. 58 4.2.4 Kết thúc giao dịch ................................ ................................ ................................ ............. 58 KẾT LUẬN ................................ ................................ ................................ ................................ 59 TÀI LIỆU THAM KHẢO ................................ ................................ ................................ ......... 61 8
LỜI MỞ ĐẦU Mục tiêu cơ bản của mật mã học là đảm bảo tính bí mật. Nó cho phép 2 đối tác trao đổi thông tin với nhau một cách an toàn trên những kênh truyền thông công khai. Hệ mật mã khóa bí mật có thể định nghĩa như sau: Giả sử ký hiệu M là tập tất cả các bản rõ có thể. C là tập tất cả các bản mã có thể. K là tập các khóa có thể. Hệ mật mã khóa bí mật gồm 2 hàm: ek : M  C , d k : C  M , k  K sao cho d k (ek (m))  m với mọi m  M và k  K . Trong hệ mật mã này, người gửi (giả sử là Tom)và người nhận (Jerry) cùng thỏa thuận một khóa bí mật, bằng cách gặp mặt nhau trực tiếp hoặc nhờ một trung tâm tin cậy phân phối khóa. Nếu Tom muốn gửi cho Jerry một thông điệp m  M , cô ấy sẽ gửi bản mã c  e k (m) cho Jerry. Jerry sẽ khôi phục bản rõ m bằng việc dùng hàm giải mã d k . Hệ mật mã khóa bí mật phải đảm bảo rằng các hàm ek và d k phải dễ áp dụng nhưng vẫn an toàn trước kẻ tấn công, khi có bản mã c vẫn khó tính được m (hoặc khóa k). Dù hệ mật mã khóa bí mật vẫn đang được dùng trong nhiều ứng dụng, nhưng vẫn còn một số nhược điểm như vấn đề phân phối khóa, vấn đề quản lý khóa và nó không hỗ trợ việc tạo chữ ký điện tử. Ý tưởng chính của các thuật toán khóa công khai là sử dụng 2 khóa khác nhau cho 2 quá trình mã hóa và giải mã. Ý tưởng này được phát minh bởi Whitfield Diffie và Martin Hellman (1976), độc lập với Ralph Merkle (1978). Từ đó, nhiều hệ mật mã khóa công khai được đưa ra, nhưng hầu hết chúng đều hoặc không an toàn hoặc không khả thi. Các thuật toán khóa công khai đều chậm hơn rất nhiều so với các thuật toán khóa bí mật. Thuật toán RSA chậm hơn 1000 lần so với các thuật toán khóa bí mật phổ biến như DES khi triển khai trong các thiết bị phần cứng; và chậm hơn 100 lần trong các phần mềm mã hóa khi mã hóa cùng một khối lượng dữ liệu như nhau. Tuy nhiên, hệ mật mã khóa công khai có một ưu điểm nổi trội là cho phép tạo chữ ký điện tử. Khóa riêng được người sở hữu giữ bí mật và nó được sử dụng để tạo chữ ký điện tử hoặc để giải mã các thông điệp đã được mã hóa bằng khóa công khai. Khóa công khai không cần thiết phải giữ bí mật do tính chất “khó tính được khóa riêng từ khóa công khai” của cặp khóa. Vì vậy, người dùng có thể công bố khóa công khai 9
trên các kênh công cộng cho những ai muốn gửi thông tin cho họ hoặc xác minh chữ ký của họ. Trong lịch sử hơn 20 năm của mật mã khóa công khai, đã có nhiều bài toán “khó” được đưa ra xem xét để ứng dụng cho các vấn đề mật mã học. Trong đó có 2 bài toán nổi bật nhất là bài toán logarith rời rạc trên trường hữu hạn và bài toán tìm ước số nguyên tố. Năm 1985, Neal Koblitz và V.S.Miller đã độc lập nhau cùng đề xuấtviệc sử dụng các đường cong elliptic cho các hệ mã hóa khóa công khai. Họ không phát minh ra thuật toán mã hóa mới với các đường cong elliptic trên trường hữu hạn, mà họ dùng những thuật toán đã có như Diffie – Hellman, sử dụng các đường cong elliptic. Các đường cong Elliptic có thể dùng trong nhiều ứng dụng như kiểm thử số nguyên tố hoặc bài toán tìm ước số nguyên tố. Các hệ mật mã trên đường cong elliptic (ECC) được dự báo là sẽ phổ biến hơn RSA do khóa nhỏ gọn hơn nhiều (khoảng 163 bit) so với RSA (1024 bit). Vì vậy, tốc độ mã hóa nhanh hơn so với RSA. Như vậy ECC có thể được dùng trên các thiết bị cầm tay (có bộ nhớ nhỏ, và tốc độ tính toán không cao) . Việc thương mại hóa ECC đã được một số nơi thực hiện như công ty Certicom và công ty RSA đã hỗ trợ mã hóa ECC trong các bộ công cụ phát triển. Tuy nhiên, một vấn đề có thể ảnh hưởng đến sự chấp nhận ECC rộng rãi như một phần của cơ sở hạ tầng khóa công khai là các kỹ thuật thực thi đường cong elliptic, thói quen, các thuật toán, và các giao thức. ECC đòi hỏi các thủ tục toán học phức tạp trong việc khởi tạo các đường cong. Các chuyên gia công nghệ thông tin vẫn chưa hiểu thấu đáo để thiết kế các hệ thống bảo mật dựa trên mật mã học, trong khi hệ RSA thì không quá phức tạp và khó hiểu. 10
Chương 1. CÁC KHÁI NIỆM CƠ BẢN 1.1. KHÁI NIỆM TRONG SỐ HỌC 1.1.1. Ước chung lớn nhất và bội chung nhỏ nhất a. Khái niệm Cho hai số nguyên a và b, 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 là ước của a và a là bội của b. 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ố đó. Số nguyên m được gọi là bội chung của các số nguyên a1, a2, …, an , nếu nó là bội 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 của a1, a2, …, an . Ký hiệu d = gcd (a1, a2, …, an) hay d = UCLN(a1, a2, …, an). Nếu gcd(a1, a2, …, an) = 1,thì a1, a2, …, an được gọi là nguyên tố cùng nhau. Một bội chung m >0 của các số nguyên a1, a2, …, an , trong đó mọi bội chung của a1, a2, …, an đều là bội của m, thì m được goi là bội chung nhỏ nhất của a1, a2, …, an . Ký hiệu m = lcm(a1, a2, …, an) hay m = BCNN(a1, a2, …, an). b. Ví dụ Cho a =12, b =15, gcd(12,15) = 3, lcm(12,15) = 60. Hai số 8 và 13 là nguyên tố cùng nhau, vì gcd(8, 13) = 1. c. Tính chất 1. d = gcd(a1, a2, …, an) tồn tại x1, x2,…, xn sao cho: d = a1x1+a2x2+…+anxn a1,a2,..an nguyên tố cùng nhautồn tại x1,x2,.. xn sao cho: 1 = a1x1+a2x2+…+anxn 2. d = gcd(a1, a2, …, an)  gcd(a1/d, a2/d,…, an/d) =1. 3. m = lcm(a1, a2, …, an)  gcd(m/a1, m/a2,…, m/an) =1. 4. gcd(m a1, m a2, …, m an) = m * gcd(a1, a2, …, an) (với m ≠ 0). 5. Nếu gcd(a, b) =1 thì lcm(a, b) = a * b 6. Nếu b>0, a = bq+r thì gcd(a,b) = gcd(b, r). 11
1.1.2. Quan hệ đồng dư a. Khái niệm Cho các số nguyên a, b, m (m > 0). Ta nói rằng a và b “đồng dư” với nhau theo modulo m, nếu chia a và b cho m, ta nhận được cùng một số dư. Ký hiệu: a ≡ b (mod m). b. Ví dụ 17 ≡ 5 (mod 3) vì chia 17 và 5 cho 3, được cùng số dư là 2. c. Tính chất 1. Quan hệ “đồng dư” là quan hệ tương đương trong Z: Với mọi số nguyên dương m ta có: a ≡ a (mod m) với mọi a  Z; (tính chất phản xạ). a ≡ b (mod m) thì b ≡ a (mod m); (tính chất đối xứng). a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m); (tính chất bắc cầu). 2. Tổng hay hiệu các “đồng dư ”: (a+b) (mod n)  [(a mod n) + (b mod n)] (mod n) (a- b) (mod n)  [(a mod n) - (b mod n)] (mod n) Tổng quát: Có thể cộng hoặc trừ từng vế nhiều đồng dư thức theo cùng một modulo m, ta được một đồng dư thức theo cùng modulo m, tức là: k k  ti ai   tibi (mod m) Nếu ai ≡ bi (mod m) , i = 1...k, thì với ti = ± 1. i 1 i 1 3.. Tích các “đồng dư”: (a* b) (mod n)  [(a mod n) * (b mod n)] (mod n) Tổng quát: Có thể nhân từng vế nhiều đồng dư thức theo cùng một modulo m, ta được một đồng dư thức theo cùng modulo m, tức là: k k  ai   bi (mod m) Nếu ai ≡ bi (mod m) với i=1..k, thì ta có: i 1 i 1 12
1.1.3. Số nguyên tố a. Khái niệm Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ước là 1 và chính nó. b. Ví dụ 10 số nguyên tố lớn đã được tìm thấy : rank Prime Digits Who when reference 232582657-1 1 9808358 G9 2006 Mersenne 44?? 230402457-1 2 9152052 G9 2005 Mersenne 43?? 225964951-1 3 7816230 G8 2005 Mersenne 42?? 224036583-1 4 7235733 G7 2004 Mersenne 41?? 220996011-1 5 6320430 G6 2003 Mersenne 40?? 213466917-1 6 4053946 G5 2001 Mersenne 39 19249·213018586+1 3918990 7 SB10 2007 27653·29167433+1 8 2759677 SB8 2005 28433·27830457+1 9 2357207 SB7 2004 33661·27031232+1 10 2116617 SB11 2007 c. Định lý 1. Đị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 n n n =P1 1.P 2 2 ...P k k , 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. 2. Định lý Mersenne. Cho p = 2k -1, nếu p là số nguyên tố, thì k phải là số nguyên tố. 13
Chứng minh Bằng phản chứng, giả sử k không là nguyên tố. Khi đó k = a.b với 1< a, b < k. p = 2k -1 = 2ab -1 = (2a)b -1= (2a -1).E Như vậy : (Trong đó E là một biểu thức nguyên - áp dụng công thức nhị thức Niu-tơn). Điều này mâu thuẫn giả thiết p là nguyên tố. Vậy giả sử sai, hay k là số nguyên tố. 3. Hàm Euler: Cho số nguyên dương n, số lượng các số nguyên dương bé hơn n và nguyên  (n) tố cùng nhau với n được ký hiệu và gọi là hàm Euler. Nhận xét: Nếu p là số nguyên tố, thì  (p) = p-1 Ví dụ: Tập các số nguyên không âm nhỏ hơn 7 là Z 7 = {0, 1, 2, 3, 4, 5, 6, 7}. Do 7 là số nguyên tố, nên Tập các số nguyên dương nhỏ hơn 7 và nguyên tố cùng nhau với 7 là Z 7 * ={1, 2, 3, 4, 5, 6, 7}. Khi đó /Z/ =  (p) = p-1 =8-1 = 7. Định lý hàm Euler.  (n) =  (p).  (q) = (p-1).(q-1). Nếu n là tích của hai số nguyên tố n = p.q, thì 14
1.2. KHÁI NIỆM TRONG ĐẠI SỐ 1.2.1. Nhóm a. Khái niệm Nhóm là một bộ (G, *), trong đó G  , * là phép toán hai ngôi trên G thoả mãn ba tính chất sau: + Phép toán có tính kết hợp: (x*y)* z = x*(y*z) với mọi x, y, z  G. + Có phần tử phần tử trung lập e  G: x*e = e*x = x với mọi x  G. + Với mọi x G, có phần tử nghịch đảo x’ G: x * x’ = x’ * x = e. Cấp của nhóm G được hiểu là số phần tử của nhóm, ký hiệu là G . Cấp của nhóm có thể là  nếu G có vô hạn phần tử. Nhóm Abel là nhóm (G, *), trong đó phép toán hai ngôi * có tính giao hoán. Nếu a * b = a * c, thì b = c. Tính chất: Nếu a * c = b * c, thì a = b. * Tập hợp các số nguyên Z cùng với phép cộng (+) thông thường là nhóm giáo hoán, có phần tử đơn vị là số 0. Gọi là nhóm cộng các số nguyên. * Tập Q* các số hữu tỷ khác 0 (hay tập R* các số thực khác 0), cùng với phép nhân (*) thông thường là nhóm giao hoán. Gọi là nhóm nhân các số hữu tỷ (số thực) khác 0. * Tập các vectơ trong không gian với phép toán cộng vectơ là nhóm giao hoán. b. Nhóm Cyclic Nhóm (G, *) được gọi là Nhóm Cyclic nếu nó được sinh ra bởi một trong các phần tử của nó. Tức là có phần tử g  G mà với mỗi a  G, đều tồn tại số n  N để g n = g * g * … * g = a. (Chú ý g * g * … * g là g * g với n lần). Khi đó g được gọi là phần tử sinh hay phần tử nguyên thuỷ của nhóm G. Nói cách khác: G được gọi là Nhóm Cyclic nếu tồn tại g  G sao cho mọi phần tử trong G đều là một luỹ thừa nguyên nào đó của g. Nhóm (Z + , +) gồm các số nguyên dương là Cyclic với phần tử sinh g = 1. 15
Cho (G, *) là Nhóm Cyclic với phần tử sinh g. và phần tử trung lập e. n Nếu tồn tại số tự nhiên nhỏ nhất n mà g = e, thì G sẽ chỉ gồm có n phần tử khác nhau: e, g, g2 , g3 , . . . , g n - 1 . Khi đó G được gọi là nhóm Cyclic hữu hạn cấp n. Nếu không tồn tại số tự nhiên n để g n = e, thì G có cấp . c. Nhóm (Zn* , phép nhân mod n) * Kí hiệu Zn =  0, 1, 2, .. . , n-1 là tập các số nguyên không âm < n. Zn và phép cộng (+) lập thành nhóm Cyclic có phần tử sinh là 1, pt trung lập e = 0. (Zn , + ) gọi là nhóm cộng, đó là nhóm hữu hạn có cấp n. * Kí hiệu Zn * =  x  Zn , x là nguyên tố cùng nhau với n . Tức là x phải  0. Zn * được gọi là Tập thặng dư thu gọn theo mod n, có số phần tử là (n). Zn * với phép nhân mod n lập thành một nhóm (nhóm nhân), pt trung lập e = 1. Tổng quát (Zn * , phép nhân mod n ) không phải là nhóm Cyclic. Nhóm nhân Zn*là Cyclic chỉ khi n có dạng: 2,4, pk, hay 2pk với p là nguyên tố lẻ. * Định lý Lagrange: Nếu G là nhóm cấp n và   G, thì Cấp của  là ước của n. * Giả sử   Z n có Cấp m, thì m là ước của (n). * Hệ quả: * Định lý: Nếu p là số nguyên tố thì Z * là nhóm Cyclic. p Nếu b  Z n thì b (n)  1 (mod n). Nếu p là số nguyên tố thì (p) = p-1. * Do đó với b  Z * (tức b nguyên tố với p), thì b(p)  1 (mod n), hay bp -1  1(mod n). p d. Phần tử nghịch đảo đối với phép nhân * Định nghĩa Cho a  Zn , nếu tồn tại b  Zn sao cho a b  1 (mod n), ta nói b là phần tử nghịch đảo của a trong Zn và ký hiệu a -1. Một phần tử có phần tử nghịch đảo, gọi là khả nghịch. * Định lý: UCLN (a, n) = 1  Phần tử a  Zn có phần tử nghịch đảo. 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 + kn = 1 → a a-1 = 1+kn, do đó a a-1 ≡ 1 (mod n). 16
Mọi phần tử trong Zn* đều có phần tử nghịch đảo. * Hệ quả: 1.2.2. Vành Vành là một tập R với 2 toán tử + và . với các điều kiện sau: R,  là một nhóm Abel a . (b . c) = (a . b) . c với mọi a, b, c  R. a . (b + c) = a . b + a . c và (a + b) . c = a . c + b . c với mọi a, b, c  R. Vành tuyến tính F là một vành. Một đa thức bậc n trên F có dạng: n f ( x)   a i x i  a 0  a1 x  ...  a n x n i 0 với n là số nguyên dương, các hệ số ai  F ( 0  i  n ). n n Cho 2 đa thức f ( x)   a i x i và g ( x)   bi x i i0 i 0 n Ta định nghĩa tổng của f(x) và g(x) là f ( x)  g ( x)   (a i  bi ) x i i0 n m Cho 2 đa thức f ( x)   a i x i và g ( x )   b j x j i0 j 0 m n f ( x) g ( x)   c k x k với c k  a b Ta định nghĩa tích của f(x) và g(x) là i j k 0 i  j k 0i  n, 0 j  m Vành được tạo thành bởi tất cả các đa thức trên F với toán tử thông thường là cộng và nhân được gọi là vành đa thức trên F và ký hiệu là F[x]. (Thuật toán chia cho F[x]) Định lý Giả sử f(x) và g(x)  F[x] có bậc nguyên dương, tồn tại duy nhất đa thức q(x), r(x)  F[x] thỏa mãn f(x) = g(x) . q(x) + r(x) với bậc của r(x) nhỏ hơn bậc của g(x). Nếu r(x) là đa thức 0 thì g(x) được gọi là ước của f(x). Đa thức bất định f(x) trong F[x] là tối giản nếu nó không có ước có bậc thấp hơn f(x) trong F[x]. a  F là nghiệm của f(x)  F[x] nếu f(a) = 0. Hệ quả Một phần tử a  F là nghiệm của đa thức f(x)  F[x] khi và chỉ khi x – a là ước của f(x) trong F[x]. 17
Chứng minh Vì a là nghiệm nên f(a) = 0. Vì f(x) = (x –a).g(x) + r(x) nên bậc của r(x) nhỏ hơn 1, tức là r(x) = c  F. Vì vậy, c = f(a) = 0. Ngược lại, nếu f(x) = (x – a). q(x) thì f(a) = 0. Hệ quả Một đa thức khác không f(x)  F[x] bậc n có nhiều nhất n nghiệm trong F. 1.2.3. Trường Trường F là một vành với phần tử đơn vị e  0 sao cho F* = {a  F | a  0 } là một nhóm nhân. Định lý Vành Zp là một trường khi và chỉ khi p là số nguyên tố Chứng minh Với a, b  Z, ta có p là số nguyên tố  p|ab tức là p|a hoặc p|b Nếu Zp là một trường thì Z * tạo thành một nhóm nhân. Nếu p a thì a  0 mod p. p Điều này nghĩa là a  Z * và tồn tại a-1. Do đó nếu p|ab và p a thì p|(ab)-1 = b. Vậy p p là số nguyên tố. Ngược lại, giả sử p là số nguyên tố. Để chỉ ra rằng Z * là một nhóm nhân ta p chỉ cần chỉ ra rằng với mọi x  Z * sẽ luôn tồn tại nghịch đảo x-1. Với a, b  Zp và p x  Z * , nếu xa  xb mod p thì a  b mod p  a – b  0 mod p. p Vì p|x(a–b)  p|x hoặc p|a – b và x  Z * tức là p x. Điều này suy ra p xZp = {xa | a  Zp} = Zp trong đó xa = 1 với a  Zp vì luôn tồn tại phần tử 1 trong Zp. Vậy mỗi x  Z * luôn có phần tử nghịch đảo. p Định nghĩa F là một trường. Một tập con K của F cũng là một trường với các toán tử của F được gọi là trường con của F. Hay F là một trường mở rộng của K. Nếu K  F thì K được gọi là một trường con hợp lệ của F. Trường là tối giản nếu không có trường con hợp lệ nào. Với trường F bất kỳ, giao F0 của tất cả các trường con hợp lệ là trường tối giản. 18
Trường F được gọi là có đặc số 0 nếu F0  Q nghĩa là F chứa Q như một trường con. Trường F được gọi là có đặc số p nếu F0  Zp. Trường hữu hạn là trường chứa hữu hạn các phần tử. Mọi trường hữu hạn có một số nguyên tố là đặc số của trường. Một trường F có đặc số thì với mọi a  F, p    pa = a    a = 0 Định nghĩa Trường K với phần tử đơn vị nhân là 1. Với p thỏa mãn 1  ...  1  0 được  1   p gọi là đặc số của K. [5] (Các trường hữu tỷ Q, số thực R, số phức C có đặc số là 0 ) Với p là nguyên tố thì GF(pn) có đặc số p. Nếu H là trường con của K thì H và K có cùng đặc số. F là trường mở rộng của trường K. Ký hiệu F = K(  ) nếu F là trường mở rộng nhỏ nhất của K chứa  . Nếu F là trường hữu hạn đặc số p thì nhóm nhân F* = F \ {0} là nhóm cylic và F = Zp(  ) với  là phần tử sinh của nhóm F* và  được gọi là phần tử nguyên thủy của F. Với 2 toán tử nhị nguyên * và  trên các tập A và B, một ánh xạ f : A  B nếu với mọi a, b  A ta có: f(a * b) = f(a)  f(b) Giả sử A và B là 2 nhóm (hoặc 2 trường), ta gọi h: A  B là một đẳng cấu A đến B nếu h đảm bảo các tính chất của toán tử nhóm của A. Trường hữu hạn Trường hữu hạn là trường có hữu hạn các phần tử ký hiệu là Fq hoặc GF(q) với q là số các phần tử. Định lý F là trường mở rộng bậc n trên trường hữu hạn K. Nếu K có q phần tử thì F có qn phần tử. Chứng minh Giả sử {  1 ,..., n }là cơ sở của F như là một không gian vector trên K. Mọi   F sẽ có dạng   c1 1  ...  c n n trong đó c i  K (i = 1,…, n). Vì mỗi ci có thể là một trong q phần tử của K nên số các tổ hợp tuyến tính là qn. 19
Định lý Nếu F là một trường hữu hạn có đặc số p thì F có pn phần tử với n nguyên dương. Vì vậy, mọi trường hữu hạn là một mở rộng của trường đẳng cấu Zp với p là đặc số của F. Định lý Trường hữu hạn F = F p là một trường mở rộng của Zp bậc n và mọi phần tử n n của F p là một nghiệm của đa thức x p  x trên Zp. n Chứng minh Đặc số của F p là p. Tập hợp F* = F \ {0} tạo thành nhóm nhân bậc n pn -1. Với   F * , bậc của trong nhóm chia hết cho bậc của F*, pn – 1. Vì vậy, với n n n n 1 mọi   F * , chúng ta có  p  1 hay  p   . Vì x p  x có nhiều nhất p n nghiệm, F p gồm tất cả các nghiệm của x p  x trên Zp. n Ví dụ Trường F2 chứa F2(hoặc Z2).Nếu viết toán tử cộng trong F2 như là phép cộng r r vector và viết phép nhân k và v(k,v  F2 )là một tích vô hướng của k  F2 và v r F 2 r .Khi đó F2r được xem là không gian vector trên F2 với chiều r. Ký hiệu d là chiều của không gian vector này. Có thể thực hiện ánh xạ 1 – 1 giữa các phần tử trong không gian vector d chiều và các d-tuple của các phần tử trong F2. Vì vậy,có2d phần tử trong không gian vector này.Vì d = r, F2 là không gian vector r r chiều. Fq m là một mở rộng của Fq. 2 phần tử  ,   Fq m là liên hợp trên Fq nếu  và m 1 2  là các nghiệm của cùng một đa thức tối giản bậc m trên Fq.  ,  q ,  q ,...,  q là các liên hợp của   Fq với Fq. m Fq m là một mở rộng của Fq. Một cơ sở của Fq m (không gian vector trên Fq) m 1 2 của {  ,  q ,  q ,..., q } gồm   Fq và các liên hợp của nó với Fq , được gọi là cơ m sở trực giao của Fq trên Fq. Mọi trường mở rộng bậc hữu hạn của một trường hữu m hạn có một cơ sở trực giao. Không gian chiếu 20