tailieunhanh - Bài giảng Đường cong elliptic

Bài giảng Đường cong elliptic được biên soạn nhằm trang bị cho các bạn những kiến thức về giới thiệu chung; đường cong elliptic trên trường số thực; đường cong elliptic trên trường hữu hạn; các phép toán trường hữu hạn, phép cộng, phép nhân; các bài toán kiểm tra điểm thuộc đường cong, đếm số điểm của đường cong, cộng hai điểm, nhân hai điểm, nhân nhanh; đường cong và hệ mã công khai; so sánh với RSA. | ĐƯỜNG CONG ELLIPTIC I. GIỚI THIỆU CONG TRÊN TRƯỜNG SỐ THỰC 2. ĐƯỜNG CONG TRÊN TRƯỜNG HỮU HẠN I. GIỚI THIỆU Định nghĩa: Đường cong elliptic trên trường K là tập hợp các điểm thỏa phương trình: (E):y2+a1xy+a3y=x3+a2x2+a4x+a6 (1) Với một đểm O gọi là điểm tại vô cùng. Phương trình phải thỏa điều kiện không kì dị. Nghĩa là khi viết dưới dạng F(x,y)=0 thì tại mọi điểm (x,y) có ít nhất một trong các đạo hàm riêng khác 0. Điều kiện không kì dị nghĩa là nếu xét tập các điểm trên một đường cong, thì dường cong đó không có điểm bội. Hay nếu biểu diễn y2 như một đa thứ bậc 3 của x thì đa thức không có nghiệm bội. CONG ELLIPTIC TRÊN TRƯỜNG SỐTHỰC Trong những trường đặc số khác 2,3 phương trình (1) có thể đưa dạng Weierstrass về: (E):y2=4x3+a4x+a6 Biệt thức: Δ=-16(4a43+27a62) Điều kiện không kì dị(không có điểm bội): 4a43+27a62≠0 (E):y2+y=x3-x (E): y2=x3+1/4*x+5/4 (E):y^2=x^3+2*x+1 (E):y^2=x^3-3*x+2 2. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠN Các điểmcủa đường cong (E) KH: E(Fq) | ĐƯỜNG CONG ELLIPTIC I. GIỚI THIỆU CONG TRÊN TRƯỜNG SỐ THỰC 2. ĐƯỜNG CONG TRÊN TRƯỜNG HỮU HẠN I. GIỚI THIỆU Định nghĩa: Đường cong elliptic trên trường K là tập hợp các điểm thỏa phương trình: (E):y2+a1xy+a3y=x3+a2x2+a4x+a6 (1) Với một đểm O gọi là điểm tại vô cùng. Phương trình phải thỏa điều kiện không kì dị. Nghĩa là khi viết dưới dạng F(x,y)=0 thì tại mọi điểm (x,y) có ít nhất một trong các đạo hàm riêng khác 0. Điều kiện không kì dị nghĩa là nếu xét tập các điểm trên một đường cong, thì dường cong đó không có điểm bội. Hay nếu biểu diễn y2 như một đa thứ bậc 3 của x thì đa thức không có nghiệm bội. CONG ELLIPTIC TRÊN TRƯỜNG SỐTHỰC Trong những trường đặc số khác 2,3 phương trình (1) có thể đưa dạng Weierstrass về: (E):y2=4x3+a4x+a6 Biệt thức: Δ=-16(4a43+27a62) Điều kiện không kì dị(không có điểm bội): 4a43+27a62≠0 (E):y2+y=x3-x (E): y2=x3+1/4*x+5/4 (E):y^2=x^3+2*x+1 (E):y^2=x^3-3*x+2 2. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠN Các điểmcủa đường cong (E) KH: E(Fq) trên trường Fq có q phần tử thỏa mãn phương trình trong Fq: y2=4x3+a4x+a6 Ví dụ: (E): y2=x3+1 (a1=0, a6=1) trên F5 Các điểm thuộc đường cong: (0,1),(0,-1),(2,2)(2,-2),(4,0) II. CÁC PHÉP TOÁN 1. TRƯỜNG HỮU HẠN 2. PHÉP CỘNG NHÂN HỮU HẠN Trường là tập K với hai phép toán cộng (+) và nhân(*) thỏa: K là nhóm aben với phép toán cộng có phần tử trung hòa (của phép cộng) K\{O} là nhóm aben với phép táon nhân có phần tử đơn vị Với mọi a,b,c thuộc K ta có:c(a+b)=ca+cb Và (a+b)c=ca+cb (luật phân phối) Trường có thể có vô hạn phần tử( VD: R) Một trường được gọi là hữu hạn nếu nó có hữu hạn phần tử. VD: ZP={0,1, ,p-2,p-1} Với p nguyên tố. (Zp với phép cộng theo mod p, phép nhân theo mod p)-->một trường Nếu p ngyên tố thì trường hữu hạn Fp là trừng gồm các phần tử từ 0 đến p-1 Nếu q=pr. Thì phần tử của trường Fq thỏa phương trình: Xq-X=0 Fq là tập nghiệm của pt này. Phần tử của trường Fq là các đa thức Đặc số của trường: K trường có phần tử đơn vị 1 với phép toán nhân. Khi đó đặc số