การกรองตัวเลขในขอบเขตแบบธรรมดา

ในทฤษฎีจำนวนนั้น การกรองตัวเลขในขอบเขตแบบธรรมดา (อังกฤษ: General number field sieve: GNFS) เป็น วิธีการในการแยกตัวประกอบจำนวนเต็มที่มีขนาดใหญ่ (มีตัวประกอบ 100 ตัวขึ้นไป) ได้เร็วที่สุด มักจะใช้กับเลขที่มีจำนวนมากกว่า 110 บิท โดยนำไปใช้ในการเข้ารหัสลับแบบกุญแจอสมมาตร (Public-key cryptography) ซึ่งเป็นขั้นตอนวิธีที่เหมาะสำหรับลายเซ็นดิจิตอลรวมทั้งการเข้ารหัสที่มีความปลอดภัย

การกรองตัวเลขในขอบเขตแบบธรรมดา นั้นมีเป้าหมายเพื่ออธิบายความสัมพันธ์ของที่มา, ข้อมูล และทฤษฎี ให้ผู้อ่านที่มีความเข้าใจในด้านต่างๆ เข้าใจและได้ข้อสรุปตรงกันและร่วมกันยกระดับพื้นฐานของวิธีการนี้ให้มีประสิทธิภาพมากขึ้นอีกด้วย

จะเห็นได้ว่า การกรองตัวเลขในขอบเขตแบบธรรมดานั้นมีความสำคัญอย่างมากในการรับส่งข้อความที่เป็นความลับ จึงเป็นสิ่งที่นักวิชาการให้ความสนใจ ไม่ว่าจะเป็นตัวขั้นตอนการทำงาน ผลลัพธ์จากหลากหลายขอบเขตของคณิตศาสตร์และวิทยาการคอมพิวเตอร์, ทฤษฎีเลขพีชคณิต, สมการเชิงเส้น, ค่าจำนวนจริง และการวิเคราะห์เชิงซ้อน

ตั้งแต่ได้มีการเปิดตัว elliptic curve factorization method (ECM) ในปี ค.ศ. 1985 แล้วก็ไม่มีทฤษฎีใดที่จะกล่าวถึงขั้นตอนวิธีการแยกตัวประกอบอีกเลย นอกจากขั้นตอนวิธีที่มีอยู่เดิม ซึ่งได้แก่ Multiple Polynomial Quadratic Sieve (MPQS) และวิธีนี้นับเป็นวิธีที่เร็วที่สุด ณ ขณะนั้น แต่ก็ไม่ได้เป็นที่ยอมรับแต่อย่างใด ต่อมาได้มีการพูดถึง การกรองตัวเลขในขอบเขต (Number Field Sieve) (NFS) กันมากขึ้น ว่าเป็นวิธีการแยกตัวประกอบที่ดีและเร็วกว่าขั้นตอนวิธีใดๆที่เคยมีมา ขั้นตอนวิธีประเภทนี้ สามารถแยกตัวประกอบเลขจำนวนหนึ่งโดยใช้เวลาเพียงแค่ไม่กี่สัปดาห์ เมื่อเทียบกับ Multiple Polynomial Quadratic Sieve (MPQS) ซึ่งใช้เวลานับปี แต่จากการบอกเล่าของ Joe Buhler และ Carl Pomerance ที่กล่าวไว้ว่า ทฤษฎีการกรองตัวเลขในขอบเขตนั้นสามารถนำไปใช้ได้ดีกับเลขจำนวนเต็มทั่วๆ ไป

จากผลการวิจัยพบว่า รูปแบบของสมการที่เหมาะสม อยู่ในรูป n=re?s{\displaystyle n=r^{e}\pm s} โดยกำหนดให้ r{\displaystyle r} และ s{\displaystyle s} เป็นจำนวนที่น้อยมากๆ และ e{\displaystyle e} เป็นจำนวนที่มีขนาดใหญ่มาก

วิธีนี้จะขึ้นอยู่กับจำนวนเต็ม n{\displaystyle n} ด้วย โดยทั่วไปวิธีนี้จะได้ผลที่ใกล้เคียงกับ Multiple polynomial quadratic sieve (MPQS) หรืออาจจะดีกว่าเพียงเล็กน้อยเท่านั้น

ดังนั้น จะพบว่า ทุกๆ ri{\displaystyle r_{i}} ที่เป็นสมาชิกของ U{\displaystyle U} จะอยู่เหนือ F{\displaystyle F} และ ?rif(ri)=y2{\displaystyle \Pi _{r_{i}}f({r_{i}})=y^{2}} สำหรับ Y{\displaystyle Y} บางตัวที่เป็นสมาชิกของ Z{\displaystyle Z} เนื่องจากรูปแบบสมการพหุนามพิเศษ คือ

ขั้นตอนการกรองตัวเลขในขอบเขตแบบธรรมดาพัฒนามาจากพหุนามกำลังสองซึ่งมีความสามารถในการหาคำตอบสำหรับตัวเลขที่มี เลขชี้กำลัง จำนวนมากๆ

วิธีการกรองตัวเลขในขอบเขตแบบธรรมดา เคยถูกใช้ในการหาตัวประกอบที่มีจำนวน 193 หลัก RSA??? ขนาดใหญ่ ในเดือนพฤศจิกายน ปี ค.ศ. 2005 โดย F. Bahr, M. BOEHM, J. FRANKE,T. KLEINJUNG ซึ่งจะได้ว่า

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

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