ตะแกรงกำลังสอง

**ขั้นตอนวิธีตะแกรงกำลังสอง** () เป็นหนึ่งในขั้นตอนวิธีในการแยกตัวประกอบของจำนวนเต็มให้อยู่ในรูปของผลคูณของเลขยกกำลังของจำนวนเฉพาะซึ่งยังเป็นสิ่งที่น่าสนใจเนื่องจากมีการนำไปใช้ในการเข้ารหัส (โดยถ้าใช้บางขั้นตอนวิธีอาจจะต้องใช้เวลามากกว่าอายุของจักรวาลเสียอีก) Carl Pomerance เป็นผู้ค้นพบขั้นตอนวิธีนี้ในปี ค.ศ. 1981 จากการปรับขั้นตอนวิธีตะแกรงเชิงเส้นของชโรโพล (Schroeppel's linear sieve) ซึ่งใช้ในการแก้ปัญหาเดียวกัน โดยเป็นขั้นตอนวิธีที่สามารถแยกตัวประกอบได้เร็วที่สุดสำหรับจำนวนเต็มที่มีจำนวนหลักน้อยกว่าเท่ากับ 100 หลัก แต่ในกรณีถัวเฉลี่ยของจำนวนเต็มใด ๆ นั้นจะพบว่า ขั้นตอนวิธีดังกล่าวเป็นขั้นตอนวิธีที่สามารถแยกตัวประกอบได้เร็วเป็นอันดับสองรองจากตะแกรงของเขตข้อมูลจำนวนเต็มทั่วไป (general number field sieve) ซึ่งจะพบว่าขั้นตอนวิธีแบบตะแกรงกำลังสองนั้นสามารถเข้าใจได้ง่าย เวลาที่ใช้ในการคำนวณนั้นขึ้นอยู่กับขนาดของจำนวนเต็มที่จะนำมาแยกตัวประกอบ โดยไม่ขึ้นกับโครงสร้างและคุณสมบัติของตัวเลขมากนัก

## จุดประสงค์

จากดังกล่าวจะพบว่าขั้นตอนวิธีตะแกรงกำลังสองนั้นเป็นขั้นตอนวิธีที่พยายามใช้พื้นฐานของขั้นตอนวิธีในการแก้ปัญหาคอนกรูเอนซ์ของจำนวนเต็มยกกำลังสองมอดุลโลเอ็น (congruence of squares mod *n*) ซึ่งขั้นตอนวิธีดังกล่าวได้ถูกนำไปในใช้ในการแก้ปัญหาการแยกตัวประกอบของจำนวนเต็มหลากหลายขั้นตอนวิธี รวมถึงขั้นตอนวิธีตะแกรงกำลังสองเอง โดยเราจะพิจารณาแบ่งขั้นตอนวิธีนี้ออกเป็นสองส่วนคือ การเก็บสะสมข้อมูล (*data collection*) ซึ่งจะเก็บข้อมูลที่มีโอกาสทำให้เกิดการคอนกรูเอ็นกำลังสองเพื่อเตรียมไปประมวลผล หลังจากนั้นพิจารณาทำให้ส่วนที่สองที่เป็นการนำข้อมูลมาประมวลผล (*data processing*) ซึ่งจะนำข้อมูลที่เก็บมาใส่เมทริกซ์แล้วพิจารณาคำนวณค่าเพื่อหาคำตอบ จนกระทั่งพบการเกิดคอนกรูเอ็นกำลังสองจริง ๆ ในส่วนแรกนั้นเราสามารถทำได้โดยใช้ระบบคู่ขนานของระบบประมวลผลของคอมพิวเตอร์ แต่ในส่วนที่สองนั้นจะต้องไปยุ่งเกี่ยวกับหน่วยความจำเนื่องจากต้องจองพื้นที่สำหรับการสร้างเมทริกซ์ ซึ่งอาจจะต้องใช้ ขั้นตอนวิธีกล่องวีดด์แมนน์ (block Wiedemann algorithm) เข้าช่วยในการทำให้การทำงานส่วนที่สองมีประสิทธิภาพมากยิ่งขึ้นในการระบบสามารถที่จะเก็บเมทริกซ์ได้

จะพบว่าขั้นตอนวิธีตะแกรงแบบยกกำลังสองนั้นมีการดัดแปลงมาจากขั้นตอนวิธีการแยกตัวประกอบของดิกสัน
โดยเวลาในการรันสำหรับขั้นตอนวิธีตะแกรงกำลังสองสำหรับการแยกตัวประกอบจำนวนเต็ม *n* ใด คือ
:e^{(1 + o (1)) \sqrt{\log n \log\log n}} =L_n\left[1/2,1\right]
ในสัญลักษณ์ของ L (L-notation) 
โดย *e* คือค่าที่นิยมใช้เป็นฐานของลอการิทึม

## แนวความคิดหลัก

ขั้นตอนวิธีดังกล่าวมีแนวความคิดมาจากขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มของแฟร์มาต์ (Fermat's factorization method) โดยพิจารณาจาก ทฤษฎีบทที่ว่าถ้าพิจารณาให้ *n* เป็นจำนวนคี่แล้วจะได้ว่ามี *a* *b* ที่เป็นจำนวนเต็มที่ทำให้ :*N* = *a*2 - *b*2 ซึ่งเมื่อพิจารณาให้ *x* mod *y* คือ เศษที่ได้จากการหาร *x* ด้วย *y* นั่นคือเราเพียงพอที่จะหา *a* ที่ทำให้ *a*2 mod *n* ให้มีค่าเป็น *b*2 เพื่อที่จะแยกตัวประกอบของ  *n* โดยอาศัยค่าที่ได้จาก *a*, *b*และ *n* ที่ได้มาจากดังกล่าว แต่เนื่องจากการหาค่า *a* นั้นเป็นเรื่องที่ยากมากโดยเฉพาะสำหรับในกรณีที่จำนวนเต็มที่ต้องการแยกตัวประกอบมีขนาดใหญ่มาก ซึ่งขั้นตอนวิธีตะแกรงกำลังสองจะพิจารณาปรับปรุงในส่วนดังกล่าว โดยจะพิจารณาจากการคำนวณ ในหลาย ๆ ค่าของ *a* จากนั้นจะพิจารณาเลือกกลุ่มของ *a* ที่ทำให้ผลคูณของในแต่ละ *a* สามารถอยู่ในรูปกำลังสองของจำนวนเต็มนั่นเอง

ยกตัวอย่างเช่น 412 mod 1649 = 32, 422 mod 1649 = 115, และ 432 mod 1649 คือ 200 ซึ่งจะพบว่าการหาเศษที่ได้ทั้ง 4 ค่าของ *a* นั้นไม่อยู่ในรูปกำลังของจำนวนเต็ม แต่เมื่อพิจารณาจากผลคูณของ (32) (200) = 6400 = 802, and mod 1649,  (32) (200) = (412) (432) = ((41) (43)) 2 จะพบว่าอยู่ในรูปกำลังสองของจำนวนเต็มนั่นเอง นั่นคือจะได้ว่า 1142 ≡ 802 (mod 1649) ซึ่งเมื่อจะพิจารณาขั้นตอนการแยกตัวประกอบของ *n* จากค่า *a*, *b* ที่ได้นั้นสามารถทำได้โดยอาศัยทฤษฎีบทที่ว่า ถ้ามี *a*, *b* ที่เป็นจำนวนมีซึ่ง *a* และ *a*2=*b*2 mod *n* นั่นคือจะได้ว่า GCD (*a*+*b*, *n*) และ GCD (*a*-*b*,*n*) เป็นตัวประกอบของ ซึ่งสามารถศึกษาเพิ่มเติมได้ในเรื่องของ คอนกรูเอนซ์ของจำนวนเต็มยกกำลังสองมอดุลโลเอ็น (congruence of squares mod *n*)

ซึ่งจากดังกล่าวก็มาถึงปัญหาที่ว่าถ้าให้ set ของจำนวนเต็มมาหนึ่งจำนวน จะทราบได้อย่างไรว่าผลคูณของตัวเลขใน set เหล่านั้น จะมีบางกลุ่มที่สามารถเขียนอยู่ในรูปกำลังสองของจำนวนเต็มได้ ซึ่งจากดังกล่าวจะอาศัยการเขียนอยู่ในรูปแบบของ เวกเตอร์หรือที่เรียกกันว่าเวกเตอร์ชี้กำลัง exponent vector ยกตัวอย่างเช่น ในการแยกตัวประกอบของจำรวนเต็มที่ทำให้อยู่ในรูปยกกำลังของจำนวนเฉพาะของ 504 คือ 23325071 นั่นคือสามารถเขียนได้อยู่ในรูปของเวกเตอร์ชี้กำลัง (exponent vector) (3,2,0,1) ซึ่งเป็นค่าของเลขชี้กำลังของ 2, 3, 5, 7 ตามลำดับ ในกรณีของ 490 ก็สามารถเขียนได้ในทำนองเดียวกันโดยสามารถเขียนเป็นเวกเตอร์ชี้กำลังได้เป็น (1,0,1,2) โดยเมื่อพิจารณาการคูณกันของ (504) (490) ก็เปรียบเสมือนการนำค่าในเวกเตอร์ชี้กำลังมาบวกกันในแต่ละสมาชิกที่มีดัชนีตรงกัน ซึ่งจะบวกได้เป็น (4,2,1,3) ทั้งนี้มาจากทฤษฎีบทที่ว่า *a**m + n* = *a*m*a*n

จากดังกล่าวชัดเจนว่าเมื่อตัวเลขในเวกเตอร์ชี้กำลังของจำนวนๆหนึ่งนั้นเป็นจำนวนเต็มคู่ทั้งหมดนั่นคือจะได้ว่าจำนวนดังกล่าวสามารถเขียนได้อยู่ในรูปของกำลังสมบูรณ์ของจำนวนเต็ม ยกตัวอย่างเช่นเมื่อเรานำเวกเตอร์ (3,0,0,1) มาบวกกับเวกเตอร์ (1,2,0,1) ได้เป็นเวกเตอร์ (4,2,0,2) ซึ่งมีสมาชิกเป็นจำนวนเต็มคู่ทั้งหมด โดยจะมีค่าเป็น (56) (126) ซึ่งเป็นค่ายกกำลังสองของจำนวนเต็ม นั่นคือการที่จะพิจารณาว่าผลคูณของจำนวนเต็มสองจำนวนอยู่ในรูปกำลังสองของจำนวนเต็มรึเปล่านั้นสามารถพิจารณาได้ง่ายจากการพิจารณาความเป็นคู่/คี่ของเวกเตอร์ชี้กำลัง ซึ่งเราสามารถนำสมาชิกในแต่ละตัวของเวกเตอร์ชี้กำลังมาหารด้วยสองแล้วเปลี่ยนค่าสมาชิกก่อนที่จะนำเวกเตอร์ดังกล่าวมาบวก ซึ่งเมื่อพิจารณาจากผลลัพธ์ของการบวกเวกเตอร์ ในรูปแบบดังกล่าว แล้วนำเวกเตอร์ผลลัพธ์มาทำในทำนองเดียวกันจะพบว่าจะอยู่ในรูปกำลังสองสัมบูรณ์เมื่อเป็นเวกเตอร์ศูนย์นั่นเองตัวอย่างเช่นจากตัวอย่างที่แล้วเราสามารถทำได้ในรูปแบบดังกล่าวและบวกกันได้เป็น (1,0,0,1) + (1,0,0,1) = (0,0,0,0) ซึ่งในการบวก vector นั้นเราเพียงพอที่จะทำได้ง่ายโดยการนำมาทำการ XOR กันแบบบิตต่อบิตที่ดัชนีตรงกัน

จากดังกล่าวจะเห็นได้ชัดว่าปัญหาได้เล็กลง โดยพิจารณาปัญหาที่ว่าให้เซ็ตของเวกเตอร์ชี้กำลังที่อยู่ในรูป 0/1 เราจะหาเซ็ตย่อยที่สามารถบวกกันได้เป็นเวกเตอร์ศูนย์ได้อย่างไร จากดังกล่าวเราจะพิจารณาใช้ทฤษฎีบทเกี่ยวกับพีชคณิตเชิงเส้นนั่นคือการพิจารณาจาก ความเป็นอิสระเชิงเส้นของเวกเตอร์นั่นเอง กล่าวคือจะนำเวกเตอร์ดังกล่าวมาใส่ในแต่ละแถวของเมทริกซ์จากนั้นใช้วิธีการกำจัดแบบเกาส์ (Gaussian elimination) ซึ่งจะสามารถทำได้ง่ายยิ่งขึ้นเนื่องจากเป็นเวกเตอร์ที่ถูกนำมาสมาชิกหารด้วยสองแล้วพิจารณาเพียงแค่เศษ ซึ่งจะพิจารณาได้เซตย่อยที่เป็นคำตอบในกรณีที่เวกเตอร์ภายในเซตย่อยเป็นอิสระเชิงเส้นต่อกัน

อย่างไรก็ตาม จะพบว่าเลขสุ่มบางเลขเมื่อพิจารณาเศษที่ได้จากการหารด้วย *n* ตามขั้นตอนก่อนหน้านี้ จะพบว่าอาจจะมีขนาดใหญ่มากและส่งผลให้เมื่อแยกตัวประกอบดังกล่าวประกอบด้วยจำนวนเฉพาะเป็นจำนวนมากซึ่งส่งผลโดยตรงทำให้เวกเตอร์ที่ได้มีขนาดยาวและเมทริกซ์ที่จะใช้ในการหาความเป็นอิสระเชิงเส้นนั้นมีขนาดใหญ่ ซึ่งการแก้ปัญหาดังกล่าวคือ ต้องหาค่า *a* ที่ทำให้ *a*2 mod *n* สามารถแยกตัวประกอบแล้วได้จำนวนเฉพาะเป็นจำนวนน้อย ซึ่งภายหลังจะเรียกว่าจำนวนนุ่มนวล (Smooth Numbers) ซึ่งจะทำให้เวกเตอร์ชี้กำลังและเมทริกซ์มีขนาดเล็กลงแม้จะยากในการหาจำนวนดังกล่าวก็ตาม ซึ่งจากดังกล่าวเราจะหาจำนวนนุ่มนวลดังกล่าวโดยใช้เทคนิคที่เรียกว่าการร่อนตะแกรง (sieving นั่นเอง) ซึ่งจะพิจารณากันต่อไป

## ขั้นตอนวิธี

จากที่ได้กล่าวไปแล้วในก่อนหน้านี้เราจะสรุปได้เป็นขั้นตอนดังต่อไปนี้
# เลือกค่าที่นุ่มนวลที่สุด *B* (เกี่ยวข้องกับจำนวนนุ่มนวล Smooth Numbers) เพื่อพิจารณานำมาเป็นขอบเขต โดย π (*B*) หมายถึงจำนวนของจำนวนเฉพาะ (ที่ได้จากการแยกตัวประกอบของจำนวนเต็ม) มีค่าน้อยกว่า *B* ซึ่งจำนวนดังกล่าวจะส่งผลโดยตรงต่อขนาดและจำนวนของเวกเตอร์ชี้กำลัง
# จากนั้นทำการร่อนตะแกรงเพื่อหา *a<sub>i</sub>* จำนวนทั้งหมด π (*B*) &nbsp;+&nbsp;1 ตัวเลขซึ่ง *b<sub>i</sub>*= (*a<sub>i</sub>*2 mod *n* เป็นจำนวนนุ่มนวลขนาด *B* (*B*-smooth)
# พิจารณาแยกตัวประกอบสำหรับแต่ละ *b<sub>i</sub>* แล้วนำมาทำเป็นเวกเตอร์ชี้กำลัง mod 2
# นำพีชคณิตเชิงเส้นมาใช้ในการพิจารณาเกี่ยวกับเซตย่อยของเวกเตอร์ที่ได้มาจากจำนวนที่มาจากการ่อนตะแกรง ว่าเมื่อนำเวกเตอร์เหล่านั้นมาบวกกันแล้วจะเป็นเวกเตอร์ศูนย์หรือไม่ตามที่ได้กล่าวไว้แล้วในก่อนหน้านี้  จากนั้นเมื่อพบเซตย่อยที่ทำให้ได้รับคำตอบในส่วนดังกล่าวก็จะนำ *a<sub>i</sub>* มาพิจารณาคูณกันทั้งหมดแล้วนำมาพิจารณาหาค่าเศษที่ได้จากการหารด้วย *n* โดยให้ค่าดังกล่าวเป็น *a* และพิจารณาในทำนองเดียวกับ *b<sub>i</sub>* ซึ่งจะพบว่าผลคูณยังคงอยู่ในรูปของจำนวนนุ่มนวลขนาด *B*
# จากก่อนหน้านี้เราจะพบว่าเราจะได้สมการคอนกรูเอนซ์ *a*2=*b*2 mod *n* จากนั้นเราจะพิจาณาหาค่าของ *a*, *b* 
# จากสมการคอนกรูเอนซ์ก่อนหน้านี้เราสามารถที่จะแปลงสมการดังกล่าวได้เป็น  (a+b) (a-b) =0 \pmod n นั่นคือเราจะพิจารณาคำนวณค่า หรม. ของผลต่างหรือผลรวมของ *a*, *b* กับ *n* ซึ่งค่า หรม. ดังกล่าวจะเป็นตัวประกอบหนึ่งของ *n* นั่นเอง ซึ่งอาจจะเกิดปัญหาในกรณีที่ หรม. ที่หามาได้นั้นมีค่าเป็น *n* หรือ 1 ซึ่งก็จะต้องพิจารณาหาเลือกเซตย่อยเพื่อหาค่า *a* ค่าอื่นแทน 

ซึ่งในส่วนที่เหลือของบทความดังกล่าวจะกล่าวถึงรายละเอียดปลีกย่อยเพิ่มเติมจากขั้นตอนวิธีดังกล่าวก่อนหน้านี้

## การใช้ขั้นตอนวิธีตะแกรงกำลังสองในการแก้ปัญหาคอนกรูเอนซ์
ในขั้นตอนวิธีตะแกรงแบบยกกำลังนั้นจะอาศัยการหาคู่ตัวเลขของจำนวนเต็มระหว่าง *x* และ *y (x) * ซึ่ง *y (x) * คือฟังก์ชันของ *x* โดยจะเลือกเซตของจำนวนเฉพาะที่เรียกว่า ฐานตัวประกอบ (factor base) ซึ่งจะหาค่า *x* ซึ่งคือเศษของน้อยสุดและเป็นบวกที่ทำให้ *y (x) * = *x*2 mod *n* มีตัวประกอบทั้งหมดมาจากฐานตัวประกอบ ซึ่งจะเรียก x ตัวนั้นว่า นุ่มนวล (smooth) กับ ฐานตัวประกอบเหล่านั้น
โดยจากดังกล่าวขั้นตอนวิธีตะแกรงกำลังสองได้เพิ่มความเร็วโดยอาศัยหลักการที่จะหาความสัมพันธ์โดยการพิจารณาทำให้ *x* ที่มีค่าเข้าใกล้รากที่สองของ *n* ซึ่งทำให้มั่นใจได้มากขึ้นว่า *y (x) * จะมีค่าเล็กขึ้น และเพิ่มโอกาสที่จะทำให้นุ่มนวลมากขึ้นด้วย

:y (x) =\left (\left\lceil\sqrt{n}\right\rceil+x\right) ^2-n\hbox{ (where }x\hbox{ is a small integer)}
:y (x) \approx 2x\left\lceil\sqrt{n}\right\rceil

จากดังกล่าวจะเห็นว่าค่า *y* ว่ามีค่าประมาณ 2*x*[√*n*] อย่างไรก็ตามก็แดงให้เห็นว่าอัตราการเติบโตของ *y* นั้นเป็นเชิงเส้นกับ *x* เท่าของรากที่สองของ *n*
นอกจากนี้ยังจะพบว่ายังมีวิธีอื่นที่จะเพิ่มความนุ่มนวลเช่นกัน ซึ่งทำได้ง่ายโดยการเพิ่มขนาดของฐานตัวประกอบนั่นเองแต่ถึงอย่างไรนั้น ก็ยังเป็นสิ่งจำเป็นที่จะต้องหาความสัมพันธ์ที่นุ่มนวลอย่างน้อยมากกว่าจำนวนฐานของตัวประกอบอยู่ดีเพื่อให้มั่นใจได้ว่ายังมีโอกาสที่จะเกิดอิสระเชิงเส้นของเวกเตอร์ชี้กำลัง

### ความสัมพันธ์เมื่อทำไปแล้วเพียงบางส่วน (Partial relation) และวงวน (Cycles)
จากดังกล่าวเราจะพบว่าบางครั้ง *y (x) * นั้นอาจจะไม่นุ่มนวลแต่ก็สามารถจะรวมความสัมพันธ์ที่เป็นส่วนย่อย (*partial relations*) เหล่านั้นเข้าด้วยกัน เช่น ถ้า y สองค่าเป็นผลคูณของจำนวนเฉพาะสองจำนวนที่เหมือนกันที่อยู่นอกเหนือจากฐานตัวประกอบ (แต่เท่ากับ ฐานตัวประกอบเมื่อถูกขยายแล้ว) ยกตัวอย่างเช่นมี ฐานตัวประกอบเป็น {2, 3, 5, 7} และ *n* = 91 เราจะได้ความสัมพันธ์ในส่วนย่อยดังนี้

:{21^2\equiv7^1\cdot11\pmod{91}}
:{29^2\equiv2^1\cdot11\pmod{91}}

โดยเมื่อพิจารณาการคูณกันจะได้ดังต่อไปนี้

:{(21\cdot 29) ^2\equiv2^1\cdot7^1\cdot11^2\pmod{91}}

จากนั้นพิจารณาการคูณทั้งสองข้างด้วย (11−1) 2 modulo 91และจาก 11−1 modulo 91 มีค่าเป็น 58 ดังนั้น

: (58\cdot 21\cdot 29) ^2\equiv 2^1\cdot7^1\pmod{91}
:14^2\equiv 2^1\cdot7^1\pmod{91}

โดยในการสร้างความสัมพันธ์แบบเต็มรูปแบบในแต่ความสัมพันธ์ที่เต็มรูปแบบจะถูกเรียกว่าวงวน (*cycle*)

### การร่อนตะแกรง
พิจารณากระบวนการต่อไปนี้

:y(x)=x^2-n
:y(x+kp)=(x+kp)^2-n
:y(x+kp)=x^2+2xkp+(kp)^2-n
:y(x+kp)=y(x)+2xkp+(kp)^2\equiv y(x)\pmod{p}

ซึ่งจะเห็นได้ว่าได้ว่าเมื่อ *y(x)* ≡ 0 (mod *p*) สำหรับ *x* ใด ๆ ที่ได้คำตอบจะพบว่า *y* ที่สอดคล้องกับค่าดังกล่าวนั้นจะหารด้วย *p* ลงตัวและจากดังกล่าวปัญหาที่เราทำคือการหารากที่สองของการมอดุลโลจำนวนเฉพาะ ซึ่งจะพบว่ามีขั้นตอนวิธีที่มีประสิทธิภาพในการกระทำดังกล่าว เช่น ขั้นตอนวิธีของแชงค์และโทเนลลี่ (Shanks&ndash; Tonelli algorithm) เป็นต้น
โดยในการร่อนตะแกรงนั้นจะเริ่มด้วยการให้ทุก ๆ สมาชิกในอาเรย์ *A*[] เป็นค่า 0 และสำหรับในแต่ละ *p* ของฐานตัวประกอบก็จะถูกนำมาแก้สมการกำลังสองมอดุลโล *p* ซึ่งจะให้คำตอบสองค่าคือ *α* และ *β* จากนั้นก็จะให้ค่าประมาณ log(p) ให้กับสมาชิกที่มี *y*(*x*) = 0 mod *p* ซึ่งก็จะอยู่ในรูปแบบ *A*[*kp*&nbsp;+&nbsp;*α*] และ *A*[*kp*&nbsp;+&nbsp;*β*] นั่นเอง

## ตัวอย่าง
จากดังกล่าวเราจะอธิบายตัวอย่างพื้นฐานของการประยุกต์ใช้ขั้นตอนวิธีตะแกรงกำลังสอง ในการแยกตัวประกอบของจำนวนเต็ม ซึ่งเรายกตัวอย่างตัวเลขที่มีขนาดเล็กก่อนกล่าวคือสามารถแก้ปัญหาได้โดยไม่จำเป็นต้องใช้การลดรูปด้วยการลดรูปแบบลอการึทึมหรืออื่น ๆ (logarithm optimization or prime powers) โดยตัวเลขจะนำมาแยกตัวประกอบคือ *N* = 15347 ซึ่งจะพบว่าค่าจำนวนเต็มที่มากกว่าหรือเท่ากับรากที่สองของจำนวนดังกล่าวคือ 124 และเนื่องจาก *N* มีค่าเล็กมาก จึงเพียงพอที่ใช้พหุนามในการหาคำตอบ ซึ่งจะใช้สมการกำลังสองดังกล่าวคือ *y*(*x*) = (*x* + 124)2 &minus; 15347
### การนำข้อมูลมาประมวลผล (Data processing)
เนื่องจาก *N* มีขนาดเล็กจึงเพียงพอที่จะใช้จำนวนเฉพาะเพียงแค่ 4 ตัวเพื่อเป็นฐานตัวประกอบ โดยจำนวนเฉพาะ 4 ตัวแรกที่ \sqrt{15347} \pmod{p} ยังคงหาค่าได้คือ ซึ่งจำนวน 2, 17, 23, 29 เฉพาะดังกล่าวจะใช้ในการร่อนตะแกรงเพื่อหาตัวประกอบนั่นเอง
เริ่มต้นด้วยการสร้างตะแกรงชื่อว่า V_X ของ
Y(X) = (X + \lceil\sqrt{N}\rceil)^2 - N = (X+124)^2-15347
โดยเริ่มการร่อนตะแกรงสำหรับแต่ละจำนวนเฉพาะทั้ง 4 ตัวที่ได้มา โดยเลือกที่จะร่อนตะแกรงตัวเลข 0 ≤ X 
\begin{align}V &= \begin{bmatrix} Y(0) & Y(1) & Y(2) & Y(3) & Y(4) & Y(5) & \cdots & Y(99) \end{bmatrix} \\
 & =\begin{bmatrix} 29 & 278 & 529 & 782 & 1037 & 1294 & \cdots & 34382 \end{bmatrix}\end{align}

ขั้นตอนถัดไปเราจะพิจารณาปรับเปลี่ยนตะแกรงของเราโดยจะพิจารณาจำนวนเฉพาะ p ในฐานตัวประกอบของเราได้แก่ \lbrace 2, 17, 23, 29\rbrace ในการแก้สมการ

:Y(X) \equiv (X + \lceil\sqrt{N}\rceil)^2 - N \equiv  0 \pmod{p} 

เพื่อที่จะหาสมาชิกในตาราง *V* ว่ามีค่าใดบ้างที่หารด้วย *p* ลงตัว
โดยเริ่มต้นพิจารณาสำหรับ *p* = 2 นั่นคือ (X + 124)^2 - 15347 \equiv  0 \pmod{2} ซึ่งจะได้คำตอบเป็น
X \equiv \sqrt{15347}-124  \equiv 1 \pmod{2}
ดังนั้น เมื่อพิจารณา X=1 และเพิ่มค่าทีละ 2 จะพบว่าค่าของสมาชิกที่ดัชนีดังกล่าวจะสามารถหารด้วย 2 ลงตัว
นั่นคือจะพิจารณาหารที่ดัชนีนั้น ๆ ด้วย 2 ซึ่งจะได้ผลลัพธ์ดังนี้ 

: V = \begin{bmatrix} 29 & 139 & 529 & 391 & 1037 & 647 & \cdots & 17191 \end{bmatrix}

ในทำนองเดียวกันกับจำนวนเฉพาะที่เราจะนำไปพิจารณาต่อที่เหลือคือ \lbrace 17, 23, 29\rbrace
ซึ่งเมื่อทำในทำนองเดียวกันจะได้เป็น

: \begin{align}
  X & \equiv \sqrt{15347} - 124 & \equiv 8 - 124 & \equiv 3\pmod{17} \\
    &                           & \equiv 9 - 124 & \equiv 4\pmod{17} \\
  X & \equiv \sqrt{15347} - 124 & \equiv 11 - 124 & \equiv 2\pmod{23} \\
    &                           & \equiv 12 - 124 & \equiv 3\pmod{23} \\
  X & \equiv \sqrt{15347} - 124 & \equiv 8  - 124 & \equiv 0\pmod{29} \\
    &                           & \equiv 21 - 124 & \equiv 13\pmod{29} \\
\end{align}


โดยจะสังเกตเห็นได้ว่าเมื่อ *p* > 2 จะได้ค่าของคำตอบเชิงเส้นจำนวน 2 คำตอบ ซึ่งสอดคล้องกับการใช้รากที่ 2 นั่นเอง
ในแต่ละสมการ X \equiv a \pmod{p} คำตอบใน V_x จะหารด้วย *p* ลงตัวเมื่อ *x* = *a* สำหรับแต่ละพหุคูณของ *p* นั่นคือเมื่อเราพิจาณาหารค่าสมาชิกใน *V* ที่ตำแหน่ง *a*, *a*+*p*, *a*+2*p*, *a*+3*p*,... สำหรับแต่ละจำนวนเฉพาะที่เป็นฐานตัวประกอบเพื่อค้นหาจำนวนนุ่มนวลในคุณสมบัติที่ว่ามันต้องพบแต่ละจำนวนเฉพาะดังกล่าวไม่เกิน 1 ครั้งเท่านั้น

: V = \begin{bmatrix} 1 & 139 & 23 & 1 & 61 & 647 & \cdots & 17191 \end{bmatrix}

ซึ่งจากดังกล่าวดังนั้นเราจะพิจารณาเลือกสมาชิกใน *V*  ที่มีค่าเท่ากับ 1 ซึ่งสอดคล้องกับการเป็นจำนวนนุ่มนวล จากตัวอย่างจะพบสามค่าบางส่วนที่มีคุณสมบัติดังกล่าว ได้แก่ V_0, V_3, and V_{71} ซึ่งมีค่าเป็น 1 ซึ่งจะสามารถทำเป็นตารางอธิบายได้ดังนี้   

### การนำข้อมูลมาประมวลผลผ่านเมทริกซ์ (Matrix processing)
เนื่องจากคุณสมบัติของ Smooth Number จึงสามารแก้ไขปัญหาได้ด้วยการใช้คุณสมบัติที่ว่า Y \equiv Z^2 \pmod{N}
โดยเริ่มต้นในส่วนนี้เราจะเขียนค่าในเซตย่อยที่เราเลือกมาจากขั้นตอนที่แล้วมาเขียนรูปผลคูณของจำนวนเฉพาะที่เราพิจารณาใช้เป็นฐานตัวประกอบ ซึ่งจะได้ดังต่อไปนี้

: \begin{align}
29 &= 2^0 \cdot 17^0 \cdot 23^0 \cdot 29^1 \\
782 &= 2^1 \cdot 17^1 \cdot 23^1 \cdot 29^0 \\ 
22678 &= 2^1 \cdot 17^1 \cdot 23^1 \cdot 29^1 \\
\end{align}


จากนั้นพิจาณาเขียนในรูปเวกเตอร์ชี้กำลังตามที่ได้กล่าวไปก่อนหน้านี้เพื่อที่จะนำมาใส่เมทริกซ์เพื่อพิจารณาแก้ปัญหาดังต่อไปนี้

: 
S \cdot \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix} \equiv \begin{bmatrix} 0 & 0 & 0 & 0 \end{bmatrix} \pmod{2}

ซึ่งจะพบว่าเราจะได้เมทริกซ์ S ดังกล่าวเป็น

:  S = \begin{bmatrix}1 & 1 & 1 \end{bmatrix} 

นั่นคือจะได้ว่าผลคูณของค่าสามค่าในเซตย่อยดังกล่าวสามารถเขียนอยู่ในรูปกำลังสอง (mod N) ได้ กล่าวคือ

: 29 \cdot 782 \cdot 22678 = 22678^2
และ
: 124^2 \cdot 127^2 \cdot 195^2 = 3070860^2 

ซึ่งจากดังกล่าวเมื่อพิจารณาคูณทั้งสองข้างของสมการคอนกรูเอนซ์จะได้ว่า

: 22678^2 \equiv 3070860^2 \pmod{15347} 

ซึ่งจะได้ว่า GCD(3070860 - 22678, 15347) = 103 เป็นตัวประกอบหนึ่งของ 15347 และจะได้ตัวประกอบที่เหลือของ 15347 คือ 149

## รหัสเทียม
จากดังกล่าวจะพิจารณาอ้างอิงถึงรหัสเทียมที่จำเป็นต้องใช้ในการแก้ปัญหาตะแกรงกำลังสองดังต่อไปนี้
ซึ่งง่ายต่อการเข้าใจและอยากให้ผู้อ่านไปศึกษาเพิ่มเติมด้วยตัวเอง

**ขั้นตอนวิธีที่ 1** วิธีการของตะแกรงของเอราโตสเทเนส (The Sieve of Eratosthenes)
 for i∈[2,B] do
  a[i] is unmarked
 end for
 for i ∈ [2,p] do
  if i is unmarked then
   for each multiple j of i ∈ [i + 1,√B]
    Mark a[j]
   end for
  end if
 end for
 return All unmarked a[i]
**ขั้นตอนวิธีที่ 2** การตรวจสอบว่า *N* เป็นจำนวนนุ่มนวลขนาด *B* หรือไม่ โดยพิจารณาให้ *P**B* เป็นเซ็ตของจำนวนเฉพาะที่น้อยกว่า *B*
 for i∈PB do
  while N mod i = 0 do
   N ← N mod i
  end while
 end for
 if N = 1 then
  return Is Smooth
 else
  return Not Smooth
 end if
**ขั้นตอนวิธีที่ 3** เป็นการลบค่าของ *p* ซึ่งเป็นจำนวนเฉพาะทั้งหมดออกจาก *N*
 //FactorOut(N,p)
 while N mod p = 0 do
  N ← N mod p
 end while
 return N
**ขั้นตอนที่ 4** การร่อนตะแกรง
 B ← \lceilL(n)½\rceil 
 pB ← SieveOfEratosthenes(B)
 for p ∈ pB do
  z ← N(p-1)/2 mod p
  if z = 1 then
   F ← F ∪ {p}
  end if
 end for
 ให้ I ประกอบไปด้วยช่วง [a, b] ขนาดใหญ่ หนึ่งช่วงสำหรับแต่ละระบบประมวลผล 
 for [a, b] ∈ I do
  for x ∈ [a, b] do
   R[x - a] ← x2 - N
  end for
  for p ∈ F do
   หาค่า s ซึ่งทำให้ s2= N mod p
   x ← \lceila/p\rceil p
   while x - s ≤ b do
    if a 2 - *N*  แทน *x*2 - *N* และเนื่องด้วยการลดปัญหาโดยใช้วิธีดังกล่าวทำให้เราสามารถแบ่งการแยกตัวประกอบผ่านเครือข่ายขนาดใหญ่ของคอมพิวเตอร์โดยใช้สมการพหุนามแค่สมการเดียว

## การใช้งาน
* C Quadratic Sieve – การใช้งานในสาธารณสมบัติของอัลกอริทึมตะแกรงกำลังสองที่เขียนด้วยภาษา C เผยแพร่ในปี 2022 รองรับการแยกตัวประกอบแบบกลุ่มของตัวเลขสูงสุด 330 บิต และสามารถส่งออกผลลัพธ์ในรูปแบบ JSON หรือ CSV

## อ้างอิง

*  Section 6.1: The quadratic sieve factorization method, pp.&nbsp;227-244.

## แหล่งข้อมูลอื่น
* Reference paper  มหาวิทยาลัยอิลลินอยส์ เออร์แบนา-แชมเปญจน์

หมวดหมู่:ขั้นตอนวิธีการแยกตัวประกอบจำนวนเต็ม