ตะแกรงกำลังสอง: มีกฎง่ายๆ ในการตัดสินใจว่าจะกรองตัวเลขจำนวนเท่าใด?

ใน Quadratic Sieve บริสุทธิ์ เราจำเป็นต้องค้นหาความสัมพันธ์เพิ่มเติมอีกเล็กน้อย (เทียบเท่า, ราบรื่น) มากกว่าจำนวนเฉพาะในฐานตัวประกอบ ในนี้ เรานับจำนวนเฉพาะขนาดเล็ก $p_i$ ที่ทำให้ $N$ โมดูโลสารตกค้างกำลังสอง $p_i$ไม่ใช่พลังของพวกเขา การนับนี้ยังเป็นจำนวนของคอลัมน์ในเมทริกซ์ของความสัมพันธ์ (กระจัดกระจาย) โดยที่ความสัมพันธ์คือเส้น ซึ่งทำหน้าที่เป็นอินพุตให้กับเฟสพีชคณิตเชิงเส้น โดยทั่วไปแล้ว 5 บรรทัดมากกว่าคอลัมน์ก็เพียงพอแล้ว แต่ละความสัมพันธ์พิเศษเพิ่มเติมจะลดความน่าจะเป็นของความล้มเหลวลงสองเท่า

สิ่งนี้ให้เกณฑ์การทำงานเพื่อหยุดการกรองและเริ่มพีชคณิตเชิงเส้น แต่ไม่ได้บอกโดยตรงว่าเราจะต้องกรองจำนวนเต็มจำนวนเท่าใด กฎง่ายๆ สำหรับสิ่งนั้นและพารามิเตอร์อื่นๆ ขึ้นอยู่กับหลายสิ่งหลายอย่าง รวมถึง

• วิกฤตถ้าเรากรองหนึ่ง (QS) หรือพหุนามหลาย (MPQS/SIQS) ด้วยคำพูดคำจา บ่อยครั้งเกินไปที่พหุนามจะเติบโตจนมีค่าสูงเกินไป ดังนั้นความราบรื่นจึงกลายเป็นสิ่งที่หายาก จากนั้น การขยายตะแกรงหรือใช้ซ้ำเพื่อตะแกรงให้ไกลขึ้นในโพลิโนเมียลเดียวกันจะไม่ช่วยอะไรมากนัก
• กลยุทธ์ w.r.t. ค่าพหุนามที่เราไม่แน่ใจ (หรือมีความมั่นใจสูง) โดยการสรุปบันทึกของปัจจัยที่พบโดยการกรองว่ามีความราบรื่นเพียงพอสำหรับวัตถุประสงค์ของเรา เราสามารถ
  • เพิกเฉยต่อพวกเขาแม้คิดว่าพวกเขายังคงสามารถเป็นได้ $B$-เรียบ.
  • ลองใช้ตัวประกอบเฉพาะขนาดเล็กไปจนถึงการกรองจำนวนเฉพาะสูงสุด $B$และพลังของพวกเขาแม้ว่าจะเกินก็ตาม $B$ (หรืออีกนัยหนึ่ง เราจำกัดไว้ที่ $B$- ค่าเรียบของพหุนามที่ผ่านขั้นตอนการกรอง) เป็นเรื่องง่ายและเป็นเรื่องปกติสำหรับพื้นฐาน (MP/SI)QS
  • ลองใช้ปัจจัยเล็ก ๆ ไปจนถึงขีดจำกัดที่สูงขึ้น $B'$ (กล่าวอีกนัยหนึ่งคือเราคัดแยกอำนาจเฉพาะและสำคัญไปที่ $B<B'$, และจำกัดให้ $B'$-สมูทที่ผ่านขั้นตอนการร่อน)
  • นอกจากนี้ ให้ปัจจัยสำคัญขนาดใหญ่หนึ่งปัจจัย (PMPQS) มีขีดจำกัดที่สูงขึ้น โดยหวังว่าการชนกันของจำนวนเฉพาะขนาดใหญ่เหล่านี้จะทำให้ความสัมพันธ์ที่ใช้ไม่ได้สองความสัมพันธ์สร้างความสัมพันธ์ใหม่ที่ใช้งานได้ (นั่นคือไม่มีจำนวนเฉพาะขนาดใหญ่ เพื่อให้พอดีกับจำนวนคอลัมน์ที่จำกัดใน เมทริกซ์)
  • นอกจากนี้ยังอนุญาตให้มีปัจจัยสำคัญขนาดใหญ่สองตัว (PPMPQS)
• เกณฑ์การกรอง (สำหรับผลรวมของล็อกของช่วงเวลาที่สะสมในรายการตะแกรง) ซึ่งเป็นการประนีประนอมระหว่างการปฏิเสธ $B$- ราบรื่นและใช้เวลามากเกินไปในการพยายามพิจารณาผู้สมัครที่ไม่ให้ความสัมพันธ์ที่ใช้งานได้

คำแนะนำเพื่อให้ QS ทำงาน:

• ขั้นแรกให้ทำบางสิ่งที่พอประมาณ $N$ ไม่มีอาร์เรย์ตะแกรง!
  • ใช้ฐานตัวประกอบของ $p_i$ การทำ $N$ สารตกค้างกำลังสอง ถึงขีดจำกัดบางอย่าง $B$. ปลอดภัยกว่าที่จะทำผิดด้านใหญ่ของที่เหมาะสมก่อน $B$.
  • หา $B$- เรียบระหว่างค่าของพหุนาม $t^2-N$ กับ $t\gtrsim\left\lceil\sqrt N\,\right\rceil$ โดยวิธีพื้นฐานที่สุด (เช่น การแบ่งการทดลอง)หาส่วนที่เรียบกว่าจำนวนไพรม์เล็กน้อย
  • ให้พีชคณิตเชิงเส้นทำงานเพื่อแยกตัวประกอบ $N$.
• เพิ่มประสิทธิภาพแผนกทดลองส่วนใหญ่ (หรือทั้งหมด) ของ $t^2-N$ โดยการทดสอบนั้น $t\bmod(p_i^k)$ ตกอยู่ในชุดของค่าที่คำนวณไว้ล่วงหน้าสองค่า
• ในขั้นตอนนั้น คอขวดควรหาทางราบเรียบโดยพยายามแยกตัวประกอบจำนวนมาก $t^2-N$ ใช้แผนกทดลอง (ที่ปรับให้เหมาะสม) โดยที่ส่วนใหญ่ไม่ได้เป็นเช่นนั้น $B$-เรียบ. แนะนำ sieve array ซึ่งมีวัตถุประสงค์เพื่อ (อย่างมาก) ลดจำนวนผู้สมัครที่ราบรื่น โดยเสียค่าใช้จ่ายในการปฏิเสธเพียงไม่กี่คนอย่างผิดๆ สิ่งนี้ทำให้สามารถเพิ่มขึ้นได้ $N$ (จึงเป็นการเพิ่มสิ่งที่ดีที่สุด $B$).
• แนะนำการเพิ่มประสิทธิภาพเพิ่มเติมทีละรายการ:
  • มี $-1$ ในฐานปัจจัยนั้นก็มีการร่อนด้วย $N-t^2$ สำหรับ $t\lesssim\left\floor\sqrt N\,\right\rfloor$
  • การปรับปรุง "ตัวคูณ" อย่างง่าย ซึ่งปัจจัยต่างๆ $ม\,N$ สำหรับจำนวนเต็มขนาดเล็กที่เลือกไว้ $m$เพื่อให้ฐานตัวประกอบดีขึ้น (มีจำนวนเฉพาะค่อนข้างน้อย)
  • การใช้พหุนามหลายตัว ซึ่งช่วยให้สามารถกรองและแยกตัวประกอบของผู้สมัครที่มีขนาดเล็กกว่ามากได้ ดังนั้นจึงมีความเป็นไปได้มากกว่า $B$- เรียบ
  • คอขวดอาจยังคงพยายามแยกตัวประกอบของแผ่นเรียบที่ผ่านการทดสอบตะแกรง (ขึ้นอยู่กับเกณฑ์ในการร่อนและขนาดของฐานปัจจัย) การประหยัดบางอย่างทำได้โดยการใช้การแบ่งการทดลอง (ที่ปรับให้เหมาะสมที่สุด) โดยไพรม์ขนาดเล็กเท่านั้น จากนั้นจึงใช้สิ่งที่ดีกว่า บางทีอาจเป็นโพลลาร์ดโรโฮที่มีการทดสอบลำดับแรกเมื่อไม่ได้ผลลัพธ์อย่างรวดเร็ว การทดสอบดังกล่าวจะจำเป็นสำหรับการปรับปรุงที่สำคัญขนาดใหญ่
  • หนึ่งการปรับปรุงสำคัญขนาดใหญ่สองรายการ (PMPQS และ PPMPQS)
• ปรับให้เหมาะสมไม่ว่าคอขวดคืออะไร และปรับพารามิเตอร์ต่างๆ มากมาย ในที่สุด คอขวดควรจะถูกกรอง การใช้งานที่ปรับให้เหมาะสมนั้นใช้ความพยายามอย่างมาก โดยมีเทคนิคและโค้ดเฉพาะตามขนาดของไพรม์ที่ร่อน และการโต้ตอบกับแคชของ CPU