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

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

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

e ( c + o ( 1 ) ) ( l o g n ) 1 3 ( l o g l o g n ) 2 3 {\displaystyle e(c+o(1))(logn)^{\frac {1}{3}}(loglogn)^{\frac {2}{3}}}

โดยที่ c = 2 ( 2 3 ) 2 3 {\displaystyle c=2({\frac {2}{3}})^{\frac {2}{3}}} ประมาณ 1.526 (เป็นเลขคงที่ ไม่ว่า n {\displaystyle n} จะเป็นเลขจำนวนเต็มใดๆ)

วิธีนี้เป็นวิธีที่ดีกว่า Multiple polynomial quadratic sieve (MPQS) เป็นอย่างมาก

e ( ( 1 + o ( 1 ) ) ( l o g n ) 1 2 ( l o g l o g n ) 1 2 {\displaystyle e((1+o(1))(logn)^{\frac {1}{2}}(loglogn)^{\frac {1}{2}}}

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

ใกล้เคียง

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