โครงสร้างพื้นฐานของการกรองตัวเลขในขอบเขตแบบธรรมดา ของ การกรองตัวเลขในขอบเขตแบบธรรมดา

เราสามารถทำการกรองตัวเลขในขอบเขตแบบธรรมดา ได้ในขั้นตอนต่อไปนี้[4]

  1. ทำการเลือกพหุนาม เวลาของขั้นตอนวิธีการนี้ต้องขึ้นอยู่กับคุณภาพของพหุนามที่เลือก ดังนั้นเราต้องเลือกอย่างระมัดระวังและเรากำหนดให้ค่าพหุนามที่เลือกเป็น p 1 , p 2 {\displaystyle p_{1},p_{2}} โดย p 1 , p 2 ∈ Z [ x ] {\displaystyle p_{1},p_{2}\in Z[x]}
  2. ขั้นตอนการกรอง ( sieving ) : สร้างสัมพันธ์ (Lattice or Line Sieves) เส้นตะแกรง ( Line Sieves ) สำหรับการกรองตัวเลขในขอบเขตแบบธรรมดา เส้นจะมีความยาวมาก เราสามารถจัดการได้โดยการตั้งเวลา แต่การตั้งเวลานั้น จะใช้เวลาค่อนข้างนานสำหรับตัวเลขที่มีขนาดใหญ่มากๆ
  3. การลบสำเนาและการตัดแต่ง ( Remove copies and Pruning) เมื่อเราได้ค่าของ ( a , b ) {\displaystyle (a,b)} มากพอแล้ว ก็จะนำค่าที่ได้ทั้งหมดมาใส่เป็นเมทริกซ์เพื่อที่จะทำการแก้ระบบสมการเชิงเส้นที่มีขนาดใหญ่กว่า F 2 {\displaystyle F2} แต่ก่อนที่เราจะเริ่มทำในแบบที่ได้กล่าวมาข้างต้นได้เราจะต้องทำ
    1. ลบสำเนา เนื่องจากขั้นตอนการสร้างสัมพันธ์เป็นการรวมกันของเส้นและเส้นตะแกรงเข้าด้วยกันหรือจากการผิดพลาดของผู้คำนวณทำให้มีค่า ( a , b ) {\displaystyle (a,b)} มากเกินไปการลบสำเนาสามารถทำได้โดยใช้ตารางแฮชเข้ามาช่วยและเรายังสามารถช่วยลดขนาดของตารางแฮชได้โดยใช้ฟังก์ชันแฮช
    2. การตัดแต่ง (Pruning) เราสามารถทำได้โดยการลดขนาดของเมทริกซ์ ได้โดย กำหนดค่าตจำนวนเฉพาะที่แตกต่างกันในแถวของ เมทริกซ์ ซึ่งเรียกว่า A {\displaystyle A} ดังนั้น

เราสามารถบอกได้ว่า A v = 0 {\displaystyle Av=0} ซึ่งอ้างอิงจาก พีชคณิตเชิงเส้น ตามขั้นตอนดังนี้

  1. ย้าย 0
  2. ถ้าในแถว i {\displaystyle i} ใน ( i , j ) {\displaystyle (i,j)} เราสามารถย้าย I {\displaystyle I} ในแถวนั้นๆ โดย ให้ j = 0 {\displaystyle j=0}
  3. การกรอง เพื่อเป็นการลดขนาดของเมทริกซ์ และลดจำนวนของหลักลง เราสามารถใช้ทฤษฎีของกราฟในการหาค่าการดำเนินงานของเมทริกซ์ที่ใช้เวลาน้อยที่สุด
  4. การแก้สมการเชิงเส้น

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

  1. ขั้นตอนวิธีของ Lonczos (อังกฤษ: Lonczos Algorithm)
  2. ขั้นตอนวิธีของ Lonczos แบบปิดกั้น (อังกฤษ: Block-Lonzos Algorithm)
  3. ขั้นตอนวิธีของ Wiedemann (อังกฤษ: Wiedemann Algorithm)
  4. ขั้นตอนวิธีของ Wiedemann แบบปิดกั้น (อังกฤษ: Block-Wiedemann Algorithm)
  5. การคำนวณหารากที่สอง

ขั้นตอนวิธีดังที่กล่าวมาในข้างต้นนั้นถูกกล่าวถึงโดย Daniel Loebenberger ซึ่งการคำนวณค่ากำลังสองของ Z {\displaystyle Z} นั้น ไม่พบปัญหาใดๆ มีวิธีการคำนวณ ค่ากำลังสองมามากหลายวิธีในแต่ละขั้นตอนวิธีและวิธีใหม่ล่าสุดคือวิธี Montgomery นั่นเอง

ใกล้เคียง

การกราดยิงหมู่ การกรีธาทัพขึ้นเหนือ การกระทำอันเป็นโจรสลัดในโซมาเลีย การกระจายรายได้ การกระตุ้น การกระจัด (เวกเตอร์) การกระตุกหัวใจด้วยไฟฟ้า การกรองตัวเลขในขอบเขตแบบธรรมดา การกระจายอย่างเป็นธรรม การกระเจิงแบบเรย์ลี