Làm cách nào để chúng tôi tính toán các phân biệt CM mà không cần bao thanh toán?

Trong ECC, có một tham số được gọi là phân biệt CM. Giả sử rằng vết của đường cong là $t$ Trong $Z_p$. số lượng $s^2$ là phép chia bình phương lớn nhất $t^2-4p$ sau đó $\frac{t^2-4p}{s^2}$ là số nguyên âm không vuông góc. Phân biệt CM là $\frac{t^2-4p}{s^2}$ nếu $\frac{t^2-4p}{s^2} \mod 4 = 1$, mặt khác như $4(\frac{t^2-4p}{s^2})$. Làm thế nào để chúng tôi tính toán tham số này mà không bao thanh toán? Có thuật toán nào cho việc này không? Có ai có thể viết chương trình bằng Sage để tính toán D không?

chúng tôi muốn tìm $D=-n/s^2$ vì $s^2$ phép chia hình vuông lớn nhất được biết $n=4p-t^2>0$ (ở đâu $t$ là dấu vết và $n$ là thứ tự của một đường cong Elliptic với một phương trình trong $\mathbb F_p$), cho cùng một lý do SafeCurve không: xác định $-D\ge B$ cho một số ràng buộc $B$ (SafeCurves có $2^{-100}=B$ ). Tôi chưa bao giờ cố gắng hoặc nghiên cứu điều đó. Câu trả lời này là một phỏng đoán hoang dã dự kiến.

Không có phương pháp nào được biết đến với đa thức thời gian heuristic ở kích thước của $n$ kéo các thừa số bình phương của $n$ một cách chắc chắn (hoặc thậm chí là AFAIK có độ tin cậy cao), như mong muốn; và tôi không có ý tưởng cho một người làm việc cho các loại $n$ xem xét.

Điều tốt nhất tôi phải đề xuất là cố gắng yếu tố $n$ sử dụng các phương pháp được sử dụng cho các số nguyên nói chung, đặc biệt ECM của Lenstra, khác với những (PPMPQS hoặc GNFS) sẽ được sử dụng cho mô-đun RSA có kích thước được xem xét (theo thứ tự $p$ tệ hơn); và thực hiện hủy bỏ sớm trong trường hợp tương đối hiếm, khó có được hệ số đầy đủ.

Phương pháp (đã sửa đổi) mà tôi đề xuất là:

1. Kéo càng nhiều yếu tố của $n$ càng tốt bằng cách sử dụng phép chia thử cho các số nguyên tố nhỏ và tùy chọn một chút Pollard's rho.

2. Tại thời điểm này, chúng tôi đã bày tỏ $n$ như $n=u\prod{p_i}^{k_i}$ với sự khác biệt $p_i$, và mỗi $k_i\ge1$. Cải thiện điều đó (ví dụ: bằng cách chia thử $u$ bởi mỗi $p_i$) sao cho không $p_i$ phân chia $u$.

3. Nếu $u$ là số nguyên tố hoặc $1$, sau đó $D=-u\prod{p_i}^{k_i\bmod 2}$, chúng ta có thể kiểm tra $-D\ge B$, dừng lại.

4. Nếu $u$ là một hình vuông (có thể dễ dàng kiểm tra), sau đó $D=-\prod p_i^{k_i\bmod 2}$, chúng ta có thể kiểm tra $-D\ge B$, dừng lại.

5. [tùy chọn] Cố gắng rút ra nhiều yếu tố hơn $u$ sử dụng một số lượng hạn chế Pollard's p-1, và p+1 của Williams (chẳng hạn như trong GMP-ECM); và nếu điều đó thành công, hãy cải thiện hệ số hóa và tiếp tục ở (2.)

6. Tại thời điểm này, chúng tôi biết một trong hai điều sau đây:

   • $u$ là tích của hai số nguyên tố khác nhau, không có số nào là một trong $p_i$;
   • $u$ là tích của ba thừa số nguyên tố trở lên (nghĩa là nếu $u=\prod{p_j}^{k_j}$ với $p_j$ thủ rồi $\sum k_j\ge3$ ), vì thế $u$ chia hết cho một số nguyên tố nhiều nhất $\sqrt[3]u$.

   Bây giờ chúng tôi sử dụng ECM của Lenstra chẳng hạn như Trong GMP-ECM với hy vọng tìm thấy một yếu tố nhỏ hơn $\sqrt[3]u$, hoặc nhỏ hơn giới hạn $B$. Nếu điều đó thành công, hãy cải thiện hệ số hóa và tiếp tục ở (2.)

7. Nếu bước (6.) không phát hiện ra một yếu tố, chúng tôi có các tùy chọn:

   • Hãy từ bỏ nỗ lực của chúng ta đối với đường cong này và thử một đường cong mới với hy vọng việc kiểm tra sẽ dễ dàng hơn;
   • Hệ số $u$ với PPMPQS hoặc GNFS;
   • đầu ra $D=-u\prod{p_i}^{k_i\bmod 2}$ chỉ có xác suất sai thấp, bị giới hạn bởi xác suất tính toán được rằng lượng ECM của Lenstra mà chúng tôi đã thực hiện không thể rút ra một hệ số nhỏ hơn $\sqrt[3]u$
   • Xác nhận $-D\ge B$ chỉ có xác suất sai thấp, bị giới hạn bởi xác suất tính toán được rằng lượng ECM của Lenstra mà chúng tôi đã thực hiện không thể rút ra một hệ số nhỏ hơn $B$