Tài liệu Luận văn cấu trúc của đường cong elliptic

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI PHẠM HỒNG ANH CẤU TRÚC CỦA ĐƯỜNG CONG ELLIPTIC LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI, NĂM 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI PHẠM HỒNG ANH CẤU TRÚC CỦA ĐƯỜNG CONG ELLIPTIC Chuyên ngành : ĐẠI SỐ VÀ LÝ THUYẾT SỐ Mã số : 60.46.01.04 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. Phạm Đức Hiệp HÀ NỘI, NĂM 2017 Mục lục MỤC LỤC 2 LỜI MỞ ĐẦU 4 1 Đường cong elliptic 6 1.1 1.2 Cấu trúc nhóm trên đường cong elliptic . . . . . . . . . . . . . . 6 1.1.1 Phương trình đường cong elliptic . . . . . . . . . . . . . 6 1.1.2 Luật nhóm 1.1.3 Tự đồng cấu, đẳng cấu, tự đẳng cấu của đường cong elliptic 13 1.1.4 Đường cong elliptic trong tọa độ xạ ảnh . . . . . . . . . 18 1.1.5 Số đường cong elliptic trên Zp . . . . . . . . . . . . . . . 20 1.1.6 Cấp của nhóm . . . . . . . . . . . . . . . . . . . . . . . . 20 . . . . . . . . . . . . . . . . . . . . . . . . . Ứng dụng Maple thực hiện một số thuật toán đối với đường cong elliptic trên trường Zp . . . . . . . . . . . . . . . . . . . . . . . 27 1.2.1 Tìm và tính số điểm của đường cong elliptic trên Zp . . . 27 1.2.2 Phép cộng điểm và nhân đôi điểm trên đường cong elliptic 28 1.2.3 Phép nhân vô hướng trên đường cong elliptic . . . . . . . 2 Một số ứng dụng của đường cong elliptic 2.1 2.2 10 31 34 Mật mã đường cong elliptic . . . . . . . . . . . . . . . . . . . . 34 2.1.1 Mật mã và những vấn đề cơ bản . . . . . . . . . . . . . . 34 2.1.2 Hệ thống đường cong elliptic . . . . . . . . . . . . . . . . 39 2.1.3 Tại sao sử dụng mật mã đường cong elliptic? . . . . . . . 44 2.1.4 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Phân tích một số nguyên thành nhân tử . . . . . . . . . . . . . 49 1 2.3 2.2.1 Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.2 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Phép thử tính chất nguyên tố của một số nguyên . . . . . . . . 55 KẾT LUẬN 58 TÀI LIỆU THAM KHẢO 59 2 LỜI CẢM ƠN Với tất cả lòng kính trọng, tôi xin được gửi lời cảm ơn sâu sắc đến thầy giáo, TS. Phạm Đức Hiệp, người đã trực tiếp hướng dẫn và tận tình chỉ bảo tôi trong suốt quá trình thực hiện hoàn thành luận văn này. Qua đây, tôi cũng xin được gửi lòng biết ơn chân thành đến thầy giáo, TS. Lưu Bá Thắng, người đã cho tôi ý tưởng đề tài luận văn này và góp ý, hướng dẫn tôi trong quá trình nghiên cứu đề tài. Tôi xin được gửi lời cảm ơn đến quý thầy cô khoa Toán - Tin trường Đại học Sư phạm Hà Nội, những người đã dạy dỗ tôi trong thời gian qua. Cuối cùng, tôi gửi sự trân trọng và biết ơn đến tất cả người thân, bạn bè vì sự quan tâm, động viên, giúp đỡ cho tôi trong suốt quá trình học tập nghiên cứu. Tác giả Phạm Hồng Anh 3 LỜI MỞ ĐẦU Từ khoảng ba, bốn thập kỉ gần đây, đường cong elliptic đã và đang đóng vai trò ngày càng quan trọng trong toán học. Các đường cong này có mặt trong nhiều lĩnh vực khác nhau của toán học vì nó rất phong phú về mặt cấu trúc. Một mặt, nó là đường cong không kỳ dị (tức là các đa tạp một chiều), mặt khác tập hợp các điểm của đường cong lập thành nhóm Abel. Vì thế hầu như mọi công cụ của toán học đều được áp dụng vào nghiên cứu đường cong elliptic. Những kết quả về đường cong elliptic có ý nghĩa rất quan trọng đối với nhiều vấn đề khác nhau [3]. Trong số học, từ những năm 80 của thế kỉ XX, đường cong elliptic đã được ứng dụng trong việc phân tích một số nguyên thành thừa số nguyên tố [10] và được sử dụng để thử tính chất nguyên tố của một số nguyên lớn [17]. Sau đó, định lý cuối của Fermat cũng đã được chứng minh (trong công trình của Andrew Wiles) bằng cách chứng minh giả thuyết Taniyama - Weil về các đường cong elliptic. Về mặt ứng dụng, đường cong elliptic được dùng trong việc xây dựng một số hệ mã hóa công khai mà đã được Koblits [9] và Miller [12] nghiên cứu vào những năm giữa thập niên 80 của thế kỷ XX. Đây là sự khẳng định mạnh mẽ nhất của toán học hiện đại trong công nghệ mã hóa. Hiện nay, hệ mã hóa công khai dùng đường cong elliptic đã trở thành một hệ mã hóa công khai thông dụng, được nhiều người trên thế giới quan tâm. Nghiên cứu về đường cong elliptic hiện vẫn đang là một vấn đề mới, nó đòi hỏi sự kết hợp giữa lý thuyết số và hình học đại số. Để nghiên cứu việc ứng dụng đường cong này vào các mục đích nêu trên, trước hết ta cần tìm hiểu về cấu trúc của đường cong elliptic. Do đó, cùng với sự hướng dẫn nhiệt tình của người hướng dẫn khoa học, tôi quyết định chọn đề tài “Cấu trúc của đường cong elliptic” để làm đề tài luận văn. 4 Vấn đề được nghiên cứu trọng tâm trong luận văn này là cấu trúc nhóm của đường cong elliptic và một số ứng dụng của đường cong này. Bố cục của luận văn được trình bày gồm 2 chương: Chương I : Đường cong elliptic Tác giả trình bày các khái niệm cơ bản, cấu trúc, các phép toán của đường cong elliptic trên trường hữu hạn và ứng dụng Maple để thực hiện một số tính toán trên đường cong. Chương II : Một số ứng dụng của đường cong elliptic Ở chương này, tác giả đề cập đến ba ứng dụng của đường cong elliptic: • Hệ thống mật mã sử dụng đường cong elliptic. • Thuật toán phân tích một số nguyên thành thừa số. • Phép thử tính chất nguyên tố của một số nguyên. 5 Chương 1 Đường cong elliptic 1.1 Cấu trúc nhóm trên đường cong elliptic 1.1.1 Phương trình đường cong elliptic Định nghĩa 1.1. Đường cong elliptic E trên trường K được định nghĩa bởi phương trình: E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 (1.1) với a1 , a2 , a3 , a4 , a6 ∈ K, ∆ 6= 0, với ∆ là biệt thức của E và được xác định như sau: ∆ d2 d4 d6 d8 = = = = = −d22 d8 − 8d34 − 27d26 + 9d2 d4 d6 , a21 + 4a2 , 2a4 + a1 a3 , a23 + 4a6 , a21 a6 + 4a2 a6 − a1 a3 a4 + a2 a23 − a24 . (1.2) Nếu L là một trường mở rộng của K thì với ∞ là điểm ở vô cực, tập hợp các điểm L - hữu tỷ trên E là: E(L) = {(x, y) ∈ L × L : y 2 + a1 xy + a3 y − x3 − a2 x2 − a4 x − a6 = 0} ∪ {∞}. Chú ý 1.2. Với các định nghĩa như trên: (i) Phương trình (1.1) được gọi là phương trình Weierstrass. (ii) Ta nói rằng E được định nghĩa trên K vì các hệ số a1 , a2 , a3 , a4 , a6 đều là các phần tử của K. Đôi khi ta có thể viết E/K để nhấn mạnh rằng E được định nghĩa trên K và K được gọi là trường cơ sở. Chú ý rằng nếu E được định nghĩa trên K thì E cũng định nghĩa được trên trường mở rộng của K. 6 Hình 1.1: Đường cong elliptic trên R. (iii) Điều kiện ∆ 6= 0 để đảm bảo rằng đường cong elliptic là trơn (smooth), tức là không có điểm nào trên đường cong có hai hay nhiều tiếp tuyến phân biệt. (iv) Điểm ∞ là điểm trên đường thẳng ở vô cực thỏa mãn các tính chất của phương trình Weierstrass. (v) Các điểm L - hữu tỷ trên E là các điểm (x, y) thỏa mãn phương trình đường cong và các tọa độ x, y thuộc L. Điểm ở vô cực được xét là một điểm L - hữu tỷ với mọi trường mở rộng L của K. Ví dụ 1.3. Đường cong elliptic trên R. Xét hai đường cong elliptic: E1 : y 2 = x3 − x, 1 5 E2 : y 2 = x3 + x + . 4 4 định nghĩa trên trường các số thực R. Các điểm E1 (R)\{∞} và E2 (R)\{∞} được biểu diễn trên hình 1.1. 7 Định nghĩa 1.4. Hai đường cong elliptic E1 và E2 định nghĩa trên K được cho bởi phương trình Weierstrass: E1 : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 , E2 : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 được gọi là đẳng cấu trên K nếu tồn tại u, r, s, t ∈ K, u 6= 0 sao cho phép đổi biến (x, y) 7−→ (u2 x + r, u2 sx + u3 y + t) (1.3) biến đổi phương trình E1 thành phương trình E2 . Phép đổi biến (1.3) được gọi là phép đổi biến chấp nhận được (admissiable change of variables). Một phương trình Weierstrass: E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 được định nghĩa trên K có thể được đơn giản hóa bằng việc áp dụng một phép đổi biến chấp nhận được. Ta xét các trường hợp riêng với trường cơ sở K có đặc số khác 2 và 3 hoặc có đặc số bằng 2 hoặc 3. 1. Nếu đặc số của K khác 2 và 3, thì phép đổi biến:   x − 3a21 − 12a2 y − 3a1 x a31 + 4a1 a2 − 12a3 (x, y) 7−→ , − 36 216 24 biến E thành đường cong có phương trình: y 2 = x3 + ax + b (1.4) với a, b ∈ K. Biệt thức của đường cong này là ∆ = −16(4a3 + 27b2 ). Đường cong elliptic được định nghĩa bởi phương trình (1.4) còn được kí hiệu là Ea,b . 2. Nếu đặc số của K là 2, thì ta có hai trường hợp để xét: TH1: a1 6= 0 thì phép đổi biến chấp nhận được:   a3 3 a21 a4 + a23 2 (x, y) 7−→ a1 x + , a1 y + a1 a31 8 biến E thành đường cong: y 2 + xy = x3 + ax2 + b (1.5) với a, b ∈ K. Đường cong có dạng trên được gọi là không suy biến mạnh (non-supersingular) (định nghĩa 1.19) và có biệt thức ∆ = b. TH2: a1 = 0, thì phép đổi biến: (x, y) 7−→ (x + a2 , y) biến E thành đường cong y 2 + cy = x3 + ax + b (1.6) với a, b, c ∈ K. Đường cong có dạng trên được gọi là suy biến mạnh (supersingular) (định nghĩa 1.19) và có biệt thức ∆ = c4 . 3. Nếu K có đặc số 3, ta cũng xét 2 trường hợp: TH1: Nếu a21 6= a2 thì phép đổi biến chấp nhận được:   d4 d4 (x, y) 7−→ x + , y + a1 x + a1 + a3 d2 d2 với d2 = a21 + a2 và d4 = a4 − a1 a3 , biến E thành đường cong: y 2 = x3 + ax2 + b (1.7) với a, b ∈ K. Đường cong có dạng trên được gọi là không suy biến mạnh và có biệt thức ∆ = −a3 b. TH2: Nếu a21 = −a2 thì phép đổi biến chấp nhận được: (x, y) 7−→ (x, y + a1 x + a3 ) biến E thành đường cong: y 2 = x3 + ax + b (1.8) với a, b ∈ K. Đường cong như vậy được gọi là suy biến mạnh và có biệt thức ∆ = −a3 . 9 Cấp của một trường hữu hạn là số phần tử trong trường ấy. Tồn tại một trường hữu hạn có cấp là q khi và chỉ khi q là lũy thừa của một số nguyên tố (q = pm với p là số nguyên tố, m là số nguyên dương, khi đó p được gọi là đặc số của trường). Ta kí hiệu trường đó là Fq . Khi p là số nguyên tố thì Fp đẳng cấu với Zp . Với mọi số nguyên tố p và số nguyên dương n, tồn tại trường hữu hạn có cấp pn , kí hiệu là Fpn . Từ phần này trở đi, luận văn chủ yếu nghiên cứu và đưa các ví dụ minh họa về đường cong elliptic có phương trình dạng (1.4) trên trường hữu hạn K = Fq có đặc số p khác 2 và 3. 1.1.2 Luật nhóm a. Phép cộng Cho E là một đường cong elliptic định nghĩa trên trường K. Ta sử dụng quy tắc cộng hợp để cộng hai điểm thuộc E(K) cho ra điểm thứ ba trên E(K). Cùng với phép toán cộng này, tập hợp các điểm thuộc E(K) trở thành một nhóm Abel với ∞ là phần tử trung hòa. Nhóm này được sử dụng trong cấu trúc của hệ mật mã đường cong elliptic. Quy tắc cộng được diễn tả tốt nhất thông qua hình học. Cho P = (x1 , y1 ) và Q = (x2 , y2 ) là hai điểm phân biệt trên đường cong elliptic E. Tổng R của P và Q được xác định như sau: đầu tiên vẽ đường thẳng đi qua hai điểm P và Q, đường thẳng này cắt đường cong E tại điểm thứ ba. Lấy R là điểm đối xứng của điểm đó qua trục hoành. Điều này được mô tả ở hình 1.2(a). Điểm nhân đôi R của P được xác định như sau: đầu tiên vẽ tiếp tuyến của đường cong E tại P , đường này cắt E tại điểm thứ hai. Lấy R là điểm đối xứng của điểm đó qua trục hoành. Điều này được mô tả ở hình 1.2(b). Từ mô tả hình học ở trên, ta xây dựng được công thức đại số của phép toán trên các đường cong elliptic E có dạng phương trình Weierstrass đơn giản (1.4) trong tọa độ affine với trường cơ sở K hữu hạn có đặc số khác 2 và 3 (ví dụ như K = Zp với p > 3 là số nguyên tố) như sau: 1. Phần tử trung hòa là ∞: P + ∞ = ∞ + P = P với mọi P ∈ E(K). 2. Phần tử đối: Nếu P = (x, y) ∈ E(K) thì (x, y) + (x, −y) = ∞. 10 Hình 1.2: Mô tả hình học phép cộng và phép nhân đôi điểm trên đường cong elliptic. Điểm (x, −y) được kí hiệu là −P , được gọi là phần tử đối của P ; chú ý rằng −P cũng là một điểm thuộc E(K). Ta cũng có −∞ = ∞. 3. Phép cộng điểm: Cho P (x1 , y1 ) ∈ E(K) và Q(x2 , y2 ) ∈ E(K), và P 6= ±Q. Ta có P + Q = (x3 , y3 ) với:  2   y 2 − y1 y 2 − y1 x3 = − x1 − x2 và y3 = (x1 − x3 ) − y1 . x2 − x1 x2 − x1 4. Nhân đôi điểm: Cho P = (x1 , y1 ) ∈ E(K), với: P 6= −P . Ta có 2P = (x3 , y3 ) với  x3 = 3x21 + a 2y1 2  − 2x1 và y3 =  3x21 + a (x1 − x3 ) − y1 . 2y1 Ví dụ 1.5. Đường cong elliptic trên trường nguyên tố Z29 . Cho p = 29, a = 4 và b = 20, xét đường cong elliptic E : y 2 = x3 + 4x + 20 định nghĩa trên Z29 . Chú ý rằng ∆ = −16(4a3 +27b2 ) = −176896 6= 0 (mod 29), 11 vì vậy E thực sự là một đường cong elliptic. Ta có các điểm trên Z29 như sau: ∞ (0, 7) (0, 22) (1, 5) (1, 24) (2, 6) (2, 23) (3, 1) (3, 28) (4, 10) (4, 19) (5, 7) (5, 22) (6, 12) (6, 17) (8, 10) (8, 19) (10, 4) (10, 25) (13, 6) (13, 23) (14, 6) (14, 23) (15, 2) (15, 27) (16, 2) (16, 27) (17, 10) (17, 19) (19, 13) (19, 16) (27, 2) (20, 3) (27, 27) (20, 26) (24, 7) (24, 22) Ví dụ phép cộng điểm trên đường cong: (5, 22) + (16, 27) = (13, 6); phép nhân đôi điểm: 2(5, 22) = (14, 6). b. Phép nhân vô hướng Phần này ta xét phương pháp để tính kP với k là một số nguyên và P là một điểm trên đường cong elliptic E định nghĩa trên trường Fq . Phép toán này được gọi là phép nhân vô hướng và chi phối thời gian thực hiện chương trình mã hóa của các đường cong elliptic. Để tìm bội của các điểm trên đường cong elliptic, ta sử dụng phương pháp nhân đôi liên tiếp. Giả sử cần tính 250P , ta viết: 250P = 2(2(2(2(2(2(2P + P ) + P ) + P ) + P )) + P ). Việc tính 250P được đưa về tính 5 phép cộng và 7 phép nhân đôi điểm của đường cong. Thuật toán 1.6 xử lý các bit số nhị phân của k từ phải sang trái trong khi thuật toán 1.7 xử lý các bit từ trái sang phải. Thuật toán 1.6. Phương pháp nhị phân hóa từ phải sang trái cho phép nhân điểm. INPUT: k = (kt−1 , . . . , k1 , k0 )2 , P ∈ E(Fq ). OUTPUT: Q = kP . 1. Q ← ∞. 2. Cho i chạy từ 0 đến t − 1, thực hiện: 2.1 Nếu ki = 1 thì Q ← Q + P . 12 2.2 P ← 2P. 3. Thu được Q. Thuật toán 1.7. Phương pháp nhị phân hóa từ trái sang phải cho phép nhân điểm. INPUT: k = (kt−1 , . . . , k1 , k0 )2 , P ∈ E(Fq ). OUTPUT: Q = kP . 1. Q ← ∞. 2. Cho i chạy từ t − 1 về 0, thực hiện: 2.1 Q ← 2Q. 2.2 Nếu ki = 1 thì Q ← Q + P . 3. Thu được Q. Ví dụ 1.8. Xét đường cong elliptic E : y 2 = x3 + 4x + 20 trên trường Z29 như trong ví dụ 1.5. Ta có điểm P (5, 22) thuộc E. Tính được 10P = 2(2.2P + P ) = (8, 19). 1.1.3 Tự đồng cấu, đẳng cấu, tự đẳng cấu của đường cong elliptic Định nghĩa 1.9. Cho E là một đường cong elliptic định nghĩa trên trường hữu hạn K. Một tự đồng cấu φ của E trên K là một đồng cấu φ : E −→ E thỏa mãn φ(∞) = ∞ và φ(P ) = (R1 (P ), R2 (P )) với mọi P ∈ E (tức là φ(x, y) = (R1 (x, y), R2 (x, y)) với mọi (x, y) ∈ E(K)), R1 và R2 là hàm hữu tỷ với hệ số trên K. Tập hợp tất cả các tự đồng cấu của E trên K là một vành, gọi là vành tự đồng cấu của E trên K. Ví dụ 1.10. Cho đường cong elliptic E định nghĩa trên trường K được cho bởi phương trình y 2 = x3 + ax + b. Xét φ : E −→ E được cho bởi φ(P ) = 2P . ta có φ là một đồng cấu và φ(x, y) = (R1 (x, y), R2 (x, y)), 13 trong đó: 2 3x2 + a R1 (x, y) = − 2x, 2y  2 !  2  2 3x + a 3x + a 3x − − y. R2 (x, y) = 2y 2y  Vì vậy, φ là một tự đẳng cấu của E. Xét đường cong elliptic E : y 2 = x3 + ax + b và R(x, y) là một hàm hữu tỷ với hệ số trên K. Vì y 2 = x3 + ax + b với mọi (x, y) ∈ E(K) nên ta có thể thay các lũy thừa bậc chẵn của y bởi một đa thức của x và thay các lũy thừa bậc lẻ của y bởi y nhân với đa thức của x và thu được hàm hữu tỷ giống với R(x, y) trên E(K). Do vậy, ta giả sử R(x, y) có dạng: R(x, y) = p1 (x) + p2 (x)y p3 (x) + p4 (x)y Hơn nữa, ta có thể nhân cả tử và mẫu của R(x, y) với p3 (x) − p4 (x)y sau đó thay y 2 bởi x3 + ax + b, điều đó kéo theo R(x, y) = q1 (x) + q2 (x)y . q3 (x) (1.9) Xét một tự đồng cấu của E được cho bởi φ(x, y) = (R1 (x, y), R2 (x, y)) như trên. Vì φ là đồng cấu nên φ(x, −y) = φ(−(x, y)) = −φ(x, y). Điều đó có nghĩa là R1 (x, −y) = R1 (x, y) và R2 (x, −y) = −R2 (x, y). Do đó, nếu R1 được viết ở dạng (1.9) thì q2 (x) = 0 và nếu R2 được viết ở dạng (1.9) thì tương ứng q1 (x) = 0. Vì vậy, ta giả sử được rằng φ(x, y) = (r1 (x), r2 (x)y) với các hàm hữu tỷ r1 (x), r2 (x). 14 Bây giờ, ta xét đến việc điều gì xảy ra nếu một trong các hàm hữu tỷ không xác định tại một điểm. Ta viết: r1 (x) = p(x)/q(x) với p(x), q(x) không có nhân tử chung. Nếu q(x) = 0 với điểm (x, y) nào đó thì ta giả sử φ(x, y) = ∞. Nếu q(x) 6= 0 thì r1 (x) được xác định; do đó φ cũng xác định. Ta định nghĩa bậc của φ: deg(φ) = max {deg p(x), deg q(x)} nếu φ không tầm thường. Khi φ = 0, đặt deg(0) = 0. Ví dụ 1.11. Xét tự đồng cấu φ(P ) = 2P của E ở ví dụ 1.10. Ta có  R1 (x, y) = 3x2 + a 2y 2 − 2x. Thay y 2 = x3 + ax + b và thực hiện một số phép biến đổi đại số, ta thu được r1 (x) = x4 − 2ax2 − 8bx + a2 . 4(x3 + ax + b) Vì vậy, deg(φ) = 4. Đa thức đặc trưng của tự đồng cấu φ là một đa thức lồi f (X) có bậc nhỏ nhất trong Z[X] thỏa mãn f (φ) = 0, nghĩa là f (φ)(P ) = ∞ với mọi P ∈ E. Nếu E là đường cong elliptic không suy biến mạnh thì đa thức đặc trưng của φ có bậc 1 hoặc 2. Ví dụ 1.12. Tự đồng cấu của đường cong elliptic. (i) Cho E là đường cong elliptic định nghĩa trên Fq . Với mỗi số nguyên m, ánh xạ nhân [m] : E −→ E được xác định bởi: [m] : P 7−→ mP là một tự đồng cấu của E định nghĩa trên Fq . Một trường hợp đặc biệt là ánh xạ đối xác định bởi P 7−→ −P . Đa thức đặc trưng của [m] là X − m. 15 (ii) Cho E là đường cong elliptic định nghĩa trên Fq . Ánh xạ lũy thừa thứ q: φ : E −→ E xác định bởi: φ : (x, y) 7−→ (xq , y q ), φ : ∞ 7−→ ∞ là một tự đồng cấu của E định nghĩa trên Fq , được gọi là tự đồng cấu Frobenius. Đa thức đặc trưng của φ là X 2 − tX + q với t = q + 1 − #E(Fq ) (với #E(Fq ) là số điểm trong E(Fq )). (iii) Cho p ≡ 1 (mod 4) là một số nguyên tố, xét đường cong elliptic E : y 2 = x3 + ax định nghĩa trên Fp . Cho i ∈ Fp là một phần tử có cấp 4 thì ánh xạ φ : E −→ E xác định bởi: φ : (x, y) 7−→ (−x, iy), φ : ∞ 7−→ ∞ là một tự đồng cấu của E định nghĩa trên Fp . Chú ý rằng φ(P ) có thể được tính bằng cách chỉ sử dụng một phép nhân. Đa thức đặc trưng của φ là X 2 + 1. (iv) Cho p ≡ 1 (mod 3) là một số nguyên tố, xét đường cong elliptic E : y 2 = x3 + b định nghĩa trên Fp . Cho β ∈ Fp là một phần tử có cấp 3. Ánh xạ φ : E −→ E xác định bởi: φ : (x, y) 7−→ (βx, y), φ : ∞ 7−→ ∞ là một tự đồng cấu của E trên Fp . Chú ý rằng φ(P ) có thể được tính chỉ sử dụng một phép nhân. Đa thức đặc trưng của φ là X 2 + X + 1. Lớp đẳng cấu Nhớ lại định nghĩa đẳng cấu đường cong elliptic (định nghĩa 1.4), ta có quan hệ đẳng cấu là một quan hệ tương đương trên tập hợp các đường cong elliptic định nghĩa trên trường hữu hạn K. Nếu hai đường cong elliptic E1 và E2 là đẳng cấu trên K thì nhóm E1 (K) và E2 (K) của các điểm K - hữu tỷ cũng đẳng cấu. Tuy nhiên, điều ngược lại không đúng (điều này được chỉ ra trong ví dụ 1.14 và 1.15). 16 Định lý 1.13 (Lớp đẳng cấu của đường cong elliptic). Cho K = Fq là một trường hữu hạn với char(K) 6= 2, 3. Hai đường cong elliptic: E1 : y 2 = x3 + ax + b, (1.10) E2 : y 2 = x3 + ax + b (1.11) định nghĩa trên K được gọi là đẳng cấu trên K nếu và chỉ nếu tồn tại u ∈ K∗ thỏa mãn u4 a = a và u6 b = b. Nếu a, u tồn tại thì phép đổi biến chấp nhận được: (x, y) → (u2 x, u3 y) biến phương trình (1.10) thành phương trình (1.11). Ví dụ 1.14 (Lớp đẳng cấu của đường cong elliptic trên Z5 ). Bảng 1.1 liệt kê 12 lớp đẳng cấu của đường cong elliptic trên Z5 . Chú ý rằng nếu nhóm E1 (Fq ) và E2 (Fq ) của các điểm Fq - hữu tỷ là đẳng cấu thì không kéo theo đường cong elliptic E1 và E2 đẳng cấu trên Fq . Ví dụ, đường cong elliptic E1 : y 2 = x3 + 1 và E2 : y 2 = x3 + 2 là không đẳng cấu trên Z5 nhưng E1 (Z5 ) và E2 (Z5 ) đều có cấp là 6 và do đó cả hai nhóm cùng đẳng cấu với Z6 . #E(Z5 ) Cấu trúc nhóm của E(Z5 ) Lớp đẳng cấu {y 2 = x3 + 1, y 2 = x3 + 4} 6 Z6 2 3 2 3 {y = x + 2, y = x + 3} 6 Z6 2 3 {y = x + x} 4 Z2 ⊕ Z2 {y 2 = x3 + 2x} 2 Z2 2 3 {y = x + 3x} 10 Z10 {y 2 = x3 + 4x} 8 Z4 ⊕ Z2 2 3 2 3 {y = x + x + 1, y = x + x + 4} 9 Z9 {y 2 = x3 + x + 2, y 2 = x3 + x + 3} 4 Z4 2 3 2 3 {y = x + 2x + 1, y = x + 2x + 4} 7 Z7 {y 2 = x3 + 3x + 2, y 2 = x3 + 3x + 3} 5 Z5 2 3 2 3 {y = x + 4x + 1, y = x + 4x + 4} 8 Z8 {y 2 = x3 + 4x + 2, y 2 = x3 + 4x + 3} 3 Z3 Bảng 1.1: Lớp đẳng cấu của đường cong elliptic trên Z5 . 17 Ví dụ 1.15. Cho p = 73. Dễ dàng sử dụng định lý 1.13 để kiểm tra rằng hai đường cong elliptic: E1 : y 2 = x3 + 25x E2 : y 2 = x3 + 53x + 55 định nghĩa trên Zp là không đẳng cấu trên Zp . Tuy nhiên, nhóm E1 (Zp ) và E2 (Zp ) của các điểm Zp - hữu tỷ đẳng cấu với nhau. Tự đẳng cấu Cho E là một đường cong elliptic có phương trình dạng (1.4) định nghĩa trên trường K. Một tự đẳng cấu của E là một đẳng cấu đi từ E đến E. Tập hợp các tự đẳng cấu của E là một nhóm con của K∗ , được kí hiệu là Aut(E) hoặc AutK (E). Dễ dàng chứng minh được kết quả sau: (i) Nếu a = 0 và K∗ có một phần tử ρ cấp 6 thì ρ sinh ra nhóm Aut(E) và #Aut(E)=6; (ii) Nếu b = 0 và K∗ có một phần tử i cấp 4 thì i sinh ra nhóm Aut(E) và #Aut(E)=4; (iii) Trong các trường hợp còn lại thì Aut(E)= {1, −1} và #Aut(E)=2. 1.1.4 Đường cong elliptic trong tọa độ xạ ảnh Không gian xạ ảnh Cho K là một trường, trên K ta định nghĩa quan hệ tương đương ∼ trên tập 3 K \ {(0, 0, 0)} như sau: (X1 , Y1 , Z1 ) ∼ (X2 , Y2 , Z2 ) nếu tồn tại λ ∈ K∗ sao cho X1 = λX2 , Y1 = λY2 và Z1 = λZ2 . Lớp tương đương chứa (X, Y, Z) ∈ K3 \ {(0, 0, 0)} kí hiệu là: (X : Y : Z) = {(λX, λY, λZ), λ ∈ K∗ } . (X : Y : Z) được gọi là một điểm xạ ảnh và (X, Y, Z) là một đại diện của (X : Y : Z). 18