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

ในทฤษฎีจำนวนนั้น การกรองตัวเลขในขอบเขตแบบธรรมดา (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 = r^{e} \pm s โดยกำหนดให้ r และ s เป็นจำนวนที่น้อยมากๆ และ e เป็นจำนวนที่มีขนาดใหญ่มาก
e (c +o (1)) (log n) ^{\frac{1}{3}} (log log n) ^{\frac{2}{3}}
โดยที่ c = 2 (\frac{2}{3}) ^{\frac{2}{3}} ประมาณ 1.526 (เป็นเลขคงที่ ไม่ว่า n จะเป็นเลขจำนวนเต็มใดๆ)
วิธีนี้เป็นวิธีที่ดีกว่า Multiple polynomial quadratic sieve (MPQS) เป็นอย่างมาก
e ((1+o (1)) (log n) ^{\frac{1}{2}} (log log n) ^{\frac{1}{2}}
วิธีนี้จะขึ้นอยู่กับจำนวนเต็ม n ด้วย โดยทั่วไปวิธีนี้จะได้ผลที่ใกล้เคียงกับ Multiple polynomial quadratic sieve (MPQS) หรืออาจจะดีกว่าเพียงเล็กน้อยเท่านั้น
== ขั้นตอนการกรองตัวเลขในขอบเขตแบบธรรมดา ==
กำหนดให้ F คือ ตัวประกอบ ที่ถูกเลือก U คือ เซต ของจำนวนเต็ม
ดังนั้น จะพบว่า ทุกๆ r_{i} ที่เป็นสมาชิกของ U จะอยู่เหนือ F และ \Pi_{r_i} f ({r_i}) =y^2
สำหรับ Y บางตัวที่เป็นสมาชิกของ Z เนื่องจากรูปแบบสมการพหุนามพิเศษ คือ
\prod_{r_{i}} f ({r_{i}}) \equiv \prod_{r_{i}} ({r_{i}^2-n}) \equiv \prod_{r_{i}\in U} {r_{i}^2} \equiv (\prod_{r_{i}\in U} {r_{i}}) ^2 (\hbox{ mod }n) 
ขั้นตอนการกรองตัวเลขในขอบเขตแบบธรรมดาพัฒนามาจากพหุนามกำลังสองซึ่งมีความสามารถในการหาคำตอบสำหรับตัวเลขที่มี เลขชี้กำลัง จำนวนมากๆ
== ตัวอย่างการกรองตัวเลขในขอบเขตแบบธรรมดา ==
วิธีการกรองตัวเลขในขอบเขตแบบธรรมดา เคยถูกใช้ในการหาตัวประกอบที่มีจำนวน 193 หลัก RSA₆₄₀ ขนาดใหญ่ ในเดือนพฤศจิกายน ปี ค.ศ. 2005 โดย F. Bahr, M. BOEHM, J. FRANKE,T. KLEINJUNG ซึ่งจะได้ว่า
RSA640=3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609
=1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579·1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571
== โครงสร้างพื้นฐานของการกรองตัวเลขในขอบเขตแบบธรรมดา ==
เราสามารถทำการกรองตัวเลขในขอบเขตแบบธรรมดา ได้ในขั้นตอนต่อไปนี้
ทำการเลือกพหุนาม เวลาของขั้นตอนวิธีการนี้ต้องขึ้นอยู่กับคุณภาพของพหุนามที่เลือก ดังนั้นเราต้องเลือกอย่างระมัดระวังและเรากำหนดให้ค่าพหุนามที่เลือกเป็น  p_{1},p_{2} โดย  p_{1},p_{2} \in Z[x] 
ขั้นตอนการกรอง ( sieving ) : สร้างสัมพันธ์ (Lattice or Line Sieves)  เส้นตะแกรง ( Line Sieves ) สำหรับการกรองตัวเลขในขอบเขตแบบธรรมดา เส้นจะมีความยาวมาก เราสามารถจัดการได้โดยการตั้งเวลา แต่การตั้งเวลานั้น จะใช้เวลาค่อนข้างนานสำหรับตัวเลขที่มีขนาดใหญ่มากๆ
การลบสำเนาและการตัดแต่ง ( Remove copies and Pruning)  เมื่อเราได้ค่าของ  (a,b)  มากพอแล้ว ก็จะนำค่าที่ได้ทั้งหมดมาใส่เป็นเมทริกซ์เพื่อที่จะทำการแก้ระบบสมการเชิงเส้นที่มีขนาดใหญ่กว่า F2 แต่ก่อนที่เราจะเริ่มทำในแบบที่ได้กล่าวมาข้างต้นได้เราจะต้องทำ
# ลบสำเนา เนื่องจากขั้นตอนการสร้างสัมพันธ์เป็นการรวมกันของเส้นและเส้นตะแกรงเข้าด้วยกันหรือจากการผิดพลาดของผู้คำนวณทำให้มีค่า  (a,b)  มากเกินไปการลบสำเนาสามารถทำได้โดยใช้ตารางแฮชเข้ามาช่วยและเรายังสามารถช่วยลดขนาดของตารางแฮชได้โดยใช้ฟังก์ชันแฮช
# การตัดแต่ง (Pruning)  เราสามารถทำได้โดยการลดขนาดของเมทริกซ์ ได้โดย กำหนดค่าตจำนวนเฉพาะที่แตกต่างกันในแถวของ เมทริกซ์ ซึ่งเรียกว่า A ดังนั้น
เราสามารถบอกได้ว่า Av=0 ซึ่งอ้างอิงจาก พีชคณิตเชิงเส้น ตามขั้นตอนดังนี้
ย้าย 0
ถ้าในแถว i ใน  (i,j)  เราสามารถย้าย I ในแถวนั้นๆ โดย ให้ j=0
การกรอง เพื่อเป็นการลดขนาดของเมทริกซ์ และลดจำนวนของหลักลง เราสามารถใช้ทฤษฎีของกราฟในการหาค่าการดำเนินงานของเมทริกซ์ที่ใช้เวลาน้อยที่สุด
การแก้สมการเชิงเส้น
หลังจากการลดสมการแล้ว ก็มาถึงการแก้สมการเชิงเส้น ที่มีจำนวนมากๆ โดยทั่วไปแล้ว ขั้นตอนวิธีที่ดีที่สุดในการ random matrix ที่มีค่า 0 ที่แตกต่างกัน คือ การกำจัดเกาท์ร่วมกับการคูณ เมทริกซ์ อย่างรวดเร็ว แต่สำหรับกรณีที่เรามี ระบบสมการเชิงเส้นเบาบาง ดังนั้น เราจะมีขั้นตอนวิธีที่ดีกว่าคือ
ขั้นตอนวิธีของ Lonczos (Lonczos Algorithm)
ขั้นตอนวิธีของ Lonczos แบบปิดกั้น (Block-Lonzos Algorithm)
ขั้นตอนวิธีของ Wiedemann (Wiedemann Algorithm)
ขั้นตอนวิธีของ Wiedemann แบบปิดกั้น (Block-Wiedemann Algorithm)
การคำนวณหารากที่สอง
ขั้นตอนวิธีดังที่กล่าวมาในข้างต้นนั้นถูกกล่าวถึงโดย Daniel Loebenberger ซึ่งการคำนวณค่ากำลังสองของ Z นั้น ไม่พบปัญหาใดๆ มีวิธีการคำนวณ ค่ากำลังสองมามากหลายวิธีในแต่ละขั้นตอนวิธีและวิธีใหม่ล่าสุดคือวิธี Montgomery นั่นเอง
== อ้างอิง ==
การกรองตัวเลขในขอบเขตแบบธรรมดา
การกรองตัวเลขในขอบเขตแบบธรรมดา
การกรองตัวเลขในขอบเขตแบบธรรมดา
การกรองตัวเลขในขอบเขตแบบธรรมดา