Tầm quan trọng của trường nhân tố trong Lenstraâs ECM

Báo giá mời máy tính $5\,P$ trên Đường cong Elliptic của phương trình $E:\ Y^2\equiv X^3+3X+7\pmod{11}$ để thực nghiệm nhận ra đây là điểm ở vô cực $\mathcal O$ (trung tính của phép cộng điểm) và có được trực giác đó là lý do tại sao tính toán của $5\,P$ trên Đường cong Elliptic của phương trình $E:\ Y^2\equiv X^3+3X+7\pmod{187}$ (như được thực hiện bởi thuật toán) mang lại một giá trị không thể đảo ngược modulo $187$.

Tất cả điều này xuất phát từ Định lý phần dư của Trung Quốc. Các tuyên bố và hậu quả có thể xảy ra của điều đó là: đối với $n=p\,q$ với $\gcd(p,q)=1$ (bao gồm $n=187$ , $p=11$ , $q=17$ giống như ví dụ)

• bất kỳ số lượng modulo $n$ có thể được tính toán tương đương modulo $p$ và modulo $q$.
• Các vành số nguyên modulo $n$, lưu ý $\mathbb Z_n$, có đẳng cấu chính tắc với $\mathbb Z_p\times\mathbb Z_q$.
• Đối với bất kỳ số nguyên $z$ Trong $[0,n)$ chúng ta có thể xác định duy nhất $z_p=z\bmod p$ và $z_q=z\bmod q$, và sau đó nó giữ $z=\left((q^{-1}\bmod p)\,(z_p-z_q)\bmod p\right)\,q+z_q$.
• Đối với một Đường cong Elliptic đã cho của phương trình được lấy modulo $n$, và điểm $U$ và $V$ trên đường cong đó, nếu chúng ta có thể tính toán $U+V$ theo các phương trình cộng điểm của Đường cong Elliptic trong một trường, mang lại $(X,Y)$ ; sau đó chúng ta có thể làm tương tự cho các đường cong có cùng phương trình lấy modulo $p$ và modulo $q$ mang lại tọa độ $(X_p,Y_p)$ và $(X_q,Y_q)$ , sau đó thu được $(X,Y)$ bằng cách áp dụng hai lần phương pháp trong gạch đầu dòng ở trên.
• Phép cộng điểm ở trên mở rộng thành phép nhân điểm với một số nguyên.

Điều này mang lại cho chúng ta cái nhìn sâu sắc gì?

Chúng tôi có được cái nhìn sâu sắc rằng bằng cách tính toán trên Đường cong Elliptic trong vòng $\mathbb Z_n$ vì $n$ của (ban đầu) hệ số không xác định như thể nó là một trường (không phải vậy), chúng tôi cũng đã tính toán trên Đường cong Elliptic trong vòng $\mathbb Z_p$ ở đâu $p$ là một thừa số (ban đầu) chưa biết của $n$. Và (vẫn chưa có bằng chứng chính thức, nhưng với một ví dụ minh họa) lý do tính toán trên một đường cong trong $\mathbb Z_n$ trúng một nghịch đảo không tính toán được là điểm ở vô cực $\mathcal O$ đã đạt được trên đường cong ở một trong $\mathbb Z_p$ hoặc $\mathbb Z_q$ (giả định $p$ và $q$ là nguyên tố, làm cho $\mathbb Z_p$ và $\mathbb Z_p$ lĩnh vực, và $\mathcal O$ trên đường cong tương ứng được xác định rõ).

Điều này cho chúng ta hiểu tại sao thuật toán hoạt động, do đó cho phép suy luận về nó và đánh giá xác suất thành công của nó (nghĩa là phát hiện ra một yếu tố không tầm thường của $n$). Khi nào $n$ là tích của các số nguyên tố phân biệt $p_i$, xác suất đó là tổng các xác suất đạt được điểm ở vô cực đối với một đường cong cho mỗi đường cong $p_j$, trừ đi xác suất (rất thấp) mà nó va chạm đồng thời trên tất cả các đường cong.