เราจะคำนวณ CM discriminants โดยไม่แยกตัวประกอบได้อย่างไร

ใน ECC มีพารามิเตอร์ที่เรียกว่า CM discriminants สมมติว่าร่องรอยของเส้นโค้งคือ $t$ ใน $Z_p$. จำนวน $s^2$ เป็นการแบ่งช่องสี่เหลี่ยมที่ใหญ่ที่สุด $t^2-4p$ แล้ว $\frac{t^2-4p}{s^2}$ เป็นจำนวนเต็มลบที่ไม่มีกำลังสอง การเลือกปฏิบัติ CM คือ $\frac{t^2-4p}{s^2}$ ถ้า $\frac{t^2-4p}{s^2} \mod 4 = 1$มิฉะนั้นเป็น $4(\frac{t^2-4p}{s^2})$. เราจะคำนวณพารามิเตอร์นี้โดยไม่แยกตัวประกอบได้อย่างไร มีอัลกอริทึมสำหรับสิ่งนี้หรือไม่? ใครสามารถเขียนโปรแกรมใน Sage เพื่อคำนวณ D ได้บ้าง

เราต้องการหา $D=-n/s^2$ สำหรับ $s^2$ การแบ่งตารางที่ใหญ่ที่สุดที่รู้จัก $n=4p-t^2>0$ (ที่ไหน $t$ เป็นร่องรอยและ $n$ เป็นลำดับของ Elliptic Curve ที่มีสมการใน $\mathbb F_p$) ด้วยเหตุผลเดียวกัน เซฟเคิร์ฟ ไม่: ตรวจสอบ $-D\ge B$ สำหรับบางผูกพัน $B$ (เซฟเคิร์ฟมี $2^{-100}=B$ ). ฉันไม่เคยพยายามหรือค้นคว้าสิ่งนั้น คำตอบนี้เป็นการคาดเดาคร่าวๆ.

ไม่มีวิธีการใดที่รู้จักโดยใช้พหุนามเวลาแบบฮิวริสติกในขนาดของ $n$ ที่ดึงตัวประกอบกำลังสองของ $n$ ด้วยความมั่นใจ (หรือแม้แต่ AFAIK ที่มีความมั่นใจสูง) ตามต้องการ และฉันไม่มีความคิดสำหรับคนที่ทำงานประเภทนี้ $n$ ที่พิจารณา.

สิ่งที่ดีที่สุดที่ฉันต้องเสนอคือ การพยายาม เพื่อแยกตัวประกอบ $n$ โดยใช้วิธีการที่ใช้กับจำนวนเต็มทั่วไปโดยเฉพาะ ECM ของ Lenstraแตกต่างจากพวก (PPMPQS หรือ จีเอ็นเอฟเอส) ที่จะใช้สำหรับโมดูล RSA ที่มีขนาดพิจารณา (ตามลำดับของ $p$ ที่แย่กว่านั้น); และทำการยกเลิกก่อนกำหนดในกรณีที่หาได้ยากซึ่งการแยกตัวประกอบแบบเต็มนั้นทำได้ยาก

วิธี (แก้ไข) ที่ฉันเสนอคือ:

1. ดึงปัจจัยหลายอย่างของ $n$ มากที่สุดเท่าที่จะเป็นไปได้โดยใช้การหารการทดลองด้วยจำนวนเฉพาะขนาดเล็กและเล็กน้อย โรของพอลลาร์ด.

2. ณ จุดนี้เราได้แสดง $n$ เช่น $n=u\ผลิตภัณฑ์{p_i}^{k_i}$ ด้วยความแตกต่าง $p_i$, และแต่ละ $k_i\ge1$. ปรับปรุงสิ่งนั้น (เช่น โดยการแบ่งการทดลองของ $u$ โดยแต่ละคน $p_i$) เพื่อไม่ให้ $p_i$ แบ่ง $u$.

3. ถ้า $u$ เป็นนายกหรือ $1$, แล้ว $D=-u\prod{p_i}^{k_i\bmod 2}$เราสามารถทดสอบได้ $-D\ge B$, หยุด.

4. ถ้า $u$ เป็นรูปสี่เหลี่ยมจัตุรัส (ซึ่งทดสอบได้ง่าย) แล้ว $D=-\prod p_i^{k_i\bmod 2}$เราสามารถทดสอบได้ $-D\ge B$, หยุด.

5. [ไม่บังคับ] พยายามดึงปัจจัยต่างๆ ของ $u$ โดยใช้จำนวนจำกัด พอลลาร์ด p-1, และ วิลเลียมส์ p+1 (เช่นใน GMP-ECM); และถ้าสำเร็จให้ปรับปรุงการแยกตัวประกอบและดำเนินการต่อที่ (2.)

6. ณ จุดนี้ เราทราบหนึ่งในสองสิ่งต่อไปนี้:

   • $u$ เป็นผลคูณของจำนวนเฉพาะสองตัวที่ต่างกัน ซึ่งไม่ใช่หนึ่งในนั้นของเรา $p_i$;
   • $u$ เป็นผลคูณของปัจจัยเฉพาะตั้งแต่สามตัวขึ้นไป (นั่นคือ ถ้า $u=\prod{p_j}^{k_j}$ กับ $p_j$ สำคัญแล้ว $\sum k_j\ge3$ ), ดังนั้น $u$ หารด้วยจำนวนเฉพาะมากที่สุด $\sqrt[3]u$.

   ตอนนี้เราใช้ ECM ของ Lenstra เช่น ใน GMP-ECM โดยหวังว่าจะหาตัวประกอบได้น้อยกว่า $\sqrt[3]u$หรือน้อยกว่าที่กำหนด $B$. หากสำเร็จให้ปรับปรุงการแยกตัวประกอบและดำเนินการต่อที่ (2.)

7. หากขั้นตอน (6.) ไม่พบปัจจัย เรามีตัวเลือก:

   • ละทิ้งความพยายามของเราสำหรับเส้นโค้งนี้และลองใหม่โดยหวังว่าการตรวจสอบจะง่ายขึ้น
   • ปัจจัย $u$ กับ PPMPQS หรือ จีเอ็นเอฟเอส;
   • เอาต์พุต $D=-u\prod{p_i}^{k_i\bmod 2}$ ซึ่งมีความเป็นไปได้ต่ำเท่านั้นที่จะไม่ถูกต้อง โดยมีขอบเขตด้วยความน่าจะเป็นที่คำนวณได้ ซึ่งจำนวน ECM ของ Lenstra ที่เราทำไม่สามารถดึงปัจจัยออกมาน้อยกว่า $\sqrt[3]u$
   • ยืนยัน $-D\ge B$ ซึ่งมีความเป็นไปได้ต่ำเท่านั้นที่จะไม่ถูกต้อง โดยมีขอบเขตด้วยความน่าจะเป็นที่คำนวณได้ ซึ่งจำนวน ECM ของ Lenstra ที่เราทำไม่สามารถดึงปัจจัยออกมาน้อยกว่า $B$