Tiếp tục theo cách tương tự, có thể tính được các bội còn lại như sau: α = (2,7) 2α = (5,2) 3α = (8,3) 4α = (10,2) 5α = (3,6) 6α = (7,9) 7α = (7,2) 8α = (3,5) 9α = (10,9) 10α = (8,8) 11α = (5,9) 12α = (2,4) Do đó α = (2,7) thực sự là phần tử nguyên thuỷ. | Vietebooks Nguyễn Hoàng Cương Tiếp tục theo cách tương tự có thể tính được các bôi còn lại như sau a 2 7 2a 5 2 3a 8 3 4a 10 2 5a 3 6 6a 7 9 7a 7 2 8a 3 5 9a 10 9 10a 8 8 11a 5 9 12a 2 4 Do đó a 2 7 thực sự là phần tử nguyên thuỷ. Môt đường cong elliptic xác định trên Zp p là số nguyên tố 3 sẽ có khoảng p điểm. Chính xác hơn theo môt định lý nổi tiếng của Hasse số các điểm trên E kí hiệu là E thảo mãn bất đẳng thức sau p 1 - 2y p E p 1 2 p Việc tính toán chính xác giá trị của E có khó hơn nhưng đã có môt thuật toán hữu hiệu do Schoof đưa ra giúp tính toán dễ dàn hơn. Nghĩa hữu hiệu ở đây được hiểu là thời gian chạy của thuật toán là thời gian đa thức theo log p. Thuật toán Schoof có thời gian chạy khoảng O log p 8 phép tính trên bít và có thể thực hiện đối với các số nguyên tố p có vài trăm chữ số . Bây giờ giả sử có thể tính được E. Vấn đề tiếp theo là phải tìm môt nhóm con cyclic trong E sao cho bài toán DL trong nó là khó. Bởi vậy ta phải biết môt vài điều về cấu trúc của nhóm E. Định lý sau đây cung cấp môt thông tin đáng kể về cấu trúc nhóm của E. Định lý Cho E là một đường cong elliptic trên Zp p là số nguyên tố 3. Khi đó tồn tại các số nguyên n1 và n2 sao cho E là đẳng cấu với Zn1xZn2. Ngoài ra n21 n1 và n21 p-1 . Bởi vậy nếu có thể tính được các số n1 và n2 thì ta sẽ biết rằng E có môt nhóm con cyclic đẳng cấu với Zn1 và có thể dùng E để thiết lập môt hẹe mật Elgamal. Chú ý là nếu n2 1 thì E là môt nhóm cyclic. Cũng vậy nếu E là môt số nguyên tố hoặc là tích của các số nguyên tố khác nhau thì E là nhóm cyclic có chỉ số nhóm cyclic. Các thuật toán Shanks và Pohlig - Hellman có thể áp dụng cho bài toán rời rạc trên đường cong Elliptic song tới nay vẫn chưa có môt thuật toán Trang 26 Vietebooks Nguyễn Hoàng Cương thích hợp cho phương pháp tính chỉ số đối với các đường cong nhiên đã có một phương pháp khai thác đẳng cấu một cách tường minh giữa các đường cong Elliptic trong trường hữu hạn. Phương pháp này dẫn đến các thuật toán hữu hiệu đối với
