เราต้องการหา $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$ ที่แย่กว่านั้น); และทำการยกเลิกก่อนกำหนดในกรณีที่หาได้ยากซึ่งการแยกตัวประกอบแบบเต็มนั้นทำได้ยาก
วิธี (แก้ไข) ที่ฉันเสนอคือ:
ดึงปัจจัยหลายอย่างของ $n$ มากที่สุดเท่าที่จะเป็นไปได้โดยใช้การหารการทดลองด้วยจำนวนเฉพาะขนาดเล็กและเล็กน้อย โรของพอลลาร์ด.
ณ จุดนี้เราได้แสดง $n$ เช่น $n=u\ผลิตภัณฑ์{p_i}^{k_i}$ ด้วยความแตกต่าง $p_i$, และแต่ละ $k_i\ge1$. ปรับปรุงสิ่งนั้น (เช่น โดยการแบ่งการทดลองของ $u$ โดยแต่ละคน $p_i$) เพื่อไม่ให้ $p_i$ แบ่ง $u$.
ถ้า $u$ เป็นนายกหรือ $1$, แล้ว $D=-u\prod{p_i}^{k_i\bmod 2}$เราสามารถทดสอบได้ $-D\ge B$, หยุด.
ถ้า $u$ เป็นรูปสี่เหลี่ยมจัตุรัส (ซึ่งทดสอบได้ง่าย) แล้ว $D=-\prod p_i^{k_i\bmod 2}$เราสามารถทดสอบได้ $-D\ge B$, หยุด.
[ไม่บังคับ] พยายามดึงปัจจัยต่างๆ ของ $u$ โดยใช้จำนวนจำกัด พอลลาร์ด p-1, และ วิลเลียมส์ p+1 (เช่นใน GMP-ECM); และถ้าสำเร็จให้ปรับปรุงการแยกตัวประกอบและดำเนินการต่อที่ (2.)
ณ จุดนี้ เราทราบหนึ่งในสองสิ่งต่อไปนี้:
- $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.)
หากขั้นตอน (6.) ไม่พบปัจจัย เรามีตัวเลือก:
- ละทิ้งความพยายามของเราสำหรับเส้นโค้งนี้และลองใหม่โดยหวังว่าการตรวจสอบจะง่ายขึ้น
- ปัจจัย $u$ กับ PPMPQS หรือ จีเอ็นเอฟเอส;
- เอาต์พุต $D=-u\prod{p_i}^{k_i\bmod 2}$ ซึ่งมีความเป็นไปได้ต่ำเท่านั้นที่จะไม่ถูกต้อง โดยมีขอบเขตด้วยความน่าจะเป็นที่คำนวณได้ ซึ่งจำนวน ECM ของ Lenstra ที่เราทำไม่สามารถดึงปัจจัยออกมาน้อยกว่า $\sqrt[3]u$
- ยืนยัน $-D\ge B$ ซึ่งมีความเป็นไปได้ต่ำเท่านั้นที่จะไม่ถูกต้อง โดยมีขอบเขตด้วยความน่าจะเป็นที่คำนวณได้ ซึ่งจำนวน ECM ของ Lenstra ที่เราทำไม่สามารถดึงปัจจัยออกมาน้อยกว่า $B$