Điểm:3

Phân biệt các điểm trong đường cong elip trên các trường mở rộng nhị phân bằng Trace

lá cờ lu

Để cho $E$ là một đường cong elliptic $^2 + xy â¡ ^3+^2+$ (đường cong Weierstrass) (trong trường hợp này, với đặc tính 2) trên trường mở rộng nhị phân $(2^{m})$ với việc xây dựng đa thức $()$ là một đa thức nguyên thủy bất khả quy trên $GF(2)$, và để $P(x_p,y_p)$ là một điểm trên đường cong.

Tôi đã thấy nhiều triển khai và thảo luận khác nhau (như cái này câu trả lời ở phía dưới) đề cập đến điểm đó $P$ có thể được phân biệt bằng chức năng Theo dõi trường và "có thể chỉ ra rằng đối với các điểm trong nhóm con thứ tự nguyên tố của đường cong, vết của $x_p$ tọa độ phải bằng dấu vết của $a$ từ phương trình đường cong elip", I E.

$Tr(x_p) = \begin{cases} \mbox{a,} & \mbox{if } P \in E \ \mbox{1,} & \mbox{otherwise} \end{cases}$

Tuy nhiên, tôi không thể tìm thấy bất kỳ thư mục liên quan nào giải thích rõ ràng lý do tại sao điều này đúng từ góc độ toán học. Bất cứ ai có thể cung cấp các lý thuyết có liên quan đằng sau này? Ngoài ra, các hạn chế và điều kiện cơ bản cần thiết để Trace có thể phản ánh liệu một điểm có nằm trên đường cong hay không?

Cảm ơn bạn đã dành thời gian,

poncho avatar
lá cờ my
Trên thực tế, các phương trình Weierstrass cho các đường cong đặc trưng đều khác nhau
G. Stergiopoulos avatar
lá cờ lu
Tôi đã sửa đổi phương trình để phù hợp với 2 đường cong đặc trưng, ​​cảm ơn.
kelalaka avatar
lá cờ in
[Phân tích các công thức hiệu quả cho Elliptic Phép cộng điểm đường cong trên các trường mở rộng nhị phân](https://sci-hub.st/https://doi.org/10.1109/CISS.2011.5766253)
Điểm:3
lá cờ us

Đây là những gì tôi có thể tìm ra dựa trên các ghi chú về đường cong elip ở đây: https://crypto.stanford.edu/pbc/notes/elliptic/explicit.html, cho một điểm $P=(x_1,y_1)$ và một đường cong được xác định bởi $$Y^2+a_1XY = X^3+a_2X^2+a_4X+a_6$$ sau đó $x$-phối hợp của $2P$ được đưa ra bởi

$$x_2 = \lambda^2 + a_1\lambda - a_2 - 2x_1$$

Trong trường hợp của bạn, $a_1=1$. Cũng thế $2x_1=0$ bởi vì trường có đặc điểm 2 và chúng ta có thể chuyển tất cả các dấu trừ sang dấu cộng vì lý do tương tự. Do đó, công thức trở thành:

$$x_2=\lambda^2 + \lambda + a$$

dấu vết của $x_2$ sẽ là $\text{tr}(\lambda^2) + \text{tr}(\lambda)+\text{tr}(a)$. Từ $\text{tr}(\lambda^2) = \text{tr}(\lambda)$, điều này có nghĩa là $\text{tr}(x)=\text{tr}(a)$. Như vậy, với bất kỳ điểm nào $P$ trên đường cong, nếu $P=2Q$ cho một số $Q$, thì dấu vết của $P$'S $x$-tọa độ bằng dấu vết của $a$.

Nếu chúng ta có một nhóm con tuần hoàn với thứ tự lẻ $n$, sau đó $2$ có một số nghịch đảo $2^{-1}$ modulo $n$. Như vậy, bắt đầu từ một điểm bất kỳ $P$ trong phân nhóm này, chúng tôi biết rằng $2(2^{-1}P)=P$, do đó tồn tại một điểm $Q=2^{-1}P$ như vậy mà $P=2Q$, và do đó nó $x$-tọa độ có cùng dấu vết với $a$.

Nói chung, mọi phần tử của nhóm con $2E(GF(2^m)) = \{x+x : x\in E(GF(2^m))\}$ đều sẽ có dấu vết giống nhau.

Còn những điểm khác thì sao? Tôi không biết. Đó có thể là điểm $P$ mà không bằng $2Q$ bất cứ gì $Q$ vẫn có thể có dấu vết bằng $\text{tr}(a)$hoặc có thể bạn có thể chứng minh rằng họ không thể.

knaccc avatar
lá cờ es
Tr(x-tọa độ) được tính như thế nào?
G. Stergiopoulos avatar
lá cờ lu
Rất vui khi tìm thấy @SamJaques. Tôi sẽ có một cái nhìn mở rộng vào cuối tuần và quay lại với bạn về điều đó.
G. Stergiopoulos avatar
lá cờ lu
@knaccc $Tr(x)$ trên trường mở rộng nhị phân có thể được tính bằng tổng các liên hợp của biểu diễn đa thức của phần tử (trong trường hợp đó là $x$).Xét về các đường cong elip, dấu vết liên quan đến Frobenius và có thể được tính toán theo cách tương tự (mặc dù không giống nhau). Kiểm tra điều này: https://www.math.uci.edu/~asilverb/bibliography/compress.pdf
kelalaka avatar
lá cờ in
[Phân tích các công thức hiệu quả cho Elliptic Phép cộng điểm đường cong trên các trường mở rộng nhị phân](https://sci-hub.st/https://doi.org/10.1109/CISS.2011.5766253)
kelalaka avatar
lá cờ in
nếu một phần tử tạo ra một nhóm có thứ tự lẻ thì tất cả các phần tử đều gấp đôi một số phần tử khác. Thật. chúng ta cần nhiều hơn thứ tự lẻ, nguyên tố. Phần H, của bài báo trên, viết hay hơn và đề cập đến trường hợp chẵn một cách rõ ràng!
Sam Jaques avatar
lá cờ us
Thứ tự lẻ là đủ để mỗi điểm gấp đôi một số điểm khác. Tôi không thể tìm thấy bất cứ điều gì trong phần H đề cập đến trường hợp các điểm có thứ tự đầy đủ trong một nhóm con có thứ tự chẵn.
G. Stergiopoulos avatar
lá cờ lu
Điều này bao gồm đầy đủ tất cả các tình huống có thể xảy ra đối với các đơn đặt hàng lẻ và, như @SameJaques đã nêu, các đường cong theo thứ tự chẵn theo các giả định đã nói ở trên. Cảm ơn! [tiếp]
G. Stergiopoulos avatar
lá cờ lu
[tiếp tục] Tôi đã cố gắng chuyển cái này sang các đường cong trên các trường nguyên tố, nhưng vì $tr$ không phải là nhị phân và không có đặc trưng = 2, nên tôi không chắc liệu điều này có khái quát hóa theo một cách nào đó trên các trường nguyên tố hay không.Bất kỳ suy nghĩ?

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.