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

ขั้นตอนวิธีตะแกรงกำลังสอง (อังกฤษ: quadratic sieve algorithm: QS) เป็นหนึ่งในขั้นตอนวิธีในการแยกตัวประกอบของจำนวนเต็มให้อยู่ในรูปของผลคูณของเลขยกกำลังของจำนวนเฉพาะซึ่งยังเป็นสิ่งที่น่าสนใจเนื่องจากมีการนำไปใช้ในการเข้ารหัส (โดยถ้าใช้บางขั้นตอนวิธีอาจจะต้องใช้เวลามากกว่าอายุของจักรวาลเสียอีก) 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 ใด คือ

${\displaystyle 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² - b² ซึ่งเมื่อพิจารณาให้ x mod y คือ เศษที่ได้จากการหาร x ด้วย y นั่นคือเราเพียงพอที่จะหา a ที่ทำให้ a² mod n ให้มีค่าเป็น b² เพื่อที่จะแยกตัวประกอบของ n โดยอาศัยค่าที่ได้จาก a, bและ n ที่ได้มาจากดังกล่าว แต่เนื่องจากการหาค่า a นั้นเป็นเรื่องที่ยากมากโดยเฉพาะสำหรับในกรณีที่จำนวนเต็มที่ต้องการแยกตัวประกอบมีขนาดใหญ่มาก ซึ่งขั้นตอนวิธีตะแกรงกำลังสองจะพิจารณาปรับปรุงในส่วนดังกล่าว โดยจะพิจารณาจากการคำนวณ ในหลายๆ ค่าของ a จากนั้นจะพิจารณาเลือกกลุ่มของ a ที่ทำให้ผลคูณของในแต่ละ a สามารถอยู่ในรูปกำลังสองของจำนวนเต็มนั่นเอง

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

ซึ่งจากดังกล่าวก็มาถึงปัญหาที่ว่าถ้าให้ set ของจำนวนเต็มมาหนึ่งจำนวน จะทราบได้อย่างไรว่าผลคูณของตัวเลขใน set เหล่านั้น จะมีบางกลุ่มที่สามารถเขียนอยู่ในรูปกำลังสองของจำนวนเต็มได้ ซึ่งจากดังกล่าวจะอาศัยการเขียนอยู่ในรูปแบบของ เวกเตอร์หรือที่เรียกกันว่าเวกเตอร์ชี้กำลัง exponent vector ยกตัวอย่างเช่น ในการแยกตัวประกอบของจำรวนเต็มที่ทำให้อยู่ในรูปยกกำลังของจำนวนเฉพาะของ 504 คือ 2³3²5⁰7¹ นั่นคือสามารถเขียนได้อยู่ในรูปของเวกเตอร์ชี้กำลัง (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^maⁿ

จากดังกล่าวชัดเจนว่าเมื่อตัวเลขในเวกเตอร์ชี้กำลังของจำนวนๆหนึ่งนั้นเป็นจำนวนเต็มคู่ทั้งหมดนั่นคือจะได้ว่าจำนวนดังกล่าวสามารถเขียนได้อยู่ในรูปของกำลังสมบูรณ์ของจำนวนเต็ม ยกตัวอย่างเช่นเมื่อเรานำเวกเตอร์ (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² mod n สามารถแยกตัวประกอบแล้วได้จำนวนเฉพาะเป็นจำนวนน้อย ซึ่งภายหลังจะเรียกว่าจำนวนนุ่มนวล (Smooth Numbers) ซึ่งจะทำให้เวกเตอร์ชี้กำลังและเมทริกซ์มีขนาดเล็กลงแม้จะยากในการหาจำนวนดังกล่าวก็ตาม ซึ่งจากดังกล่าวเราจะหาจำนวนนุ่มนวลดังกล่าวโดยใช้เทคนิคที่เรียกว่าการร่อนตะแกรง (sieving นั่นเอง) ซึ่งจะพิจารณากันต่อไป

ขั้นตอนวิธี

จากที่ได้กล่าวไปแล้วในก่อนหน้านี้เราจะสรุปได้เป็นขั้นตอนดังต่อไปนี้

1. เลือกค่าที่นุ่มนวลที่สุด B (เกี่ยวข้องกับจำนวนนุ่มนวล Smooth Numbers) เพื่อพิจารณานำมาเป็นขอบเขต โดย π (B) หมายถึงจำนวนของจำนวนเฉพาะ (ที่ได้จากการแยกตัวประกอบของจำนวนเต็ม) มีค่าน้อยกว่า B ซึ่งจำนวนดังกล่าวจะส่งผลโดยตรงต่อขนาดและจำนวนของเวกเตอร์ชี้กำลัง
2. จากนั้นทำการร่อนตะแกรงเพื่อหา a_i จำนวนทั้งหมด π (B)  + 1 ตัวเลขซึ่ง b_i= (a_i² mod n เป็นจำนวนนุ่มนวลขนาด B (B-smooth)
3. พิจารณาแยกตัวประกอบสำหรับแต่ละ b_i แล้วนำมาทำเป็นเวกเตอร์ชี้กำลัง mod 2
4. นำพีชคณิตเชิงเส้นมาใช้ในการพิจารณาเกี่ยวกับเซตย่อยของเวกเตอร์ที่ได้มาจากจำนวนที่มาจากการ่อนตะแกรง ว่าเมื่อนำเวกเตอร์เหล่านั้นมาบวกกันแล้วจะเป็นเวกเตอร์ศูนย์หรือไม่ตามที่ได้กล่าวไว้แล้วในก่อนหน้านี้ จากนั้นเมื่อพบเซตย่อยที่ทำให้ได้รับคำตอบในส่วนดังกล่าวก็จะนำ a_i มาพิจารณาคูณกันทั้งหมดแล้วนำมาพิจารณาหาค่าเศษที่ได้จากการหารด้วย n โดยให้ค่าดังกล่าวเป็น a และพิจารณาในทำนองเดียวกับ b_i ซึ่งจะพบว่าผลคูณยังคงอยู่ในรูปของจำนวนนุ่มนวลขนาด B
5. จากก่อนหน้านี้เราจะพบว่าเราจะได้สมการคอนกรูเอนซ์ a²=b² mod n จากนั้นเราจะพิจาณาหาค่าของ a, b
6. จากสมการคอนกรูเอนซ์ก่อนหน้านี้เราสามารถที่จะแปลงสมการดังกล่าวได้เป็น ${\displaystyle (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² mod n มีตัวประกอบทั้งหมดมาจากฐานตัวประกอบ ซึ่งจะเรียก x ตัวนั้นว่า นุ่มนวล (smooth) กับ ฐานตัวประกอบเหล่านั้น โดยจากดังกล่าวขั้นตอนวิธีตะแกรงกำลังสองได้เพิ่มความเร็วโดยอาศัยหลักการที่จะหาความสัมพันธ์โดยการพิจารณาทำให้ x ที่มีค่าเข้าใกล้รากที่สองของ n ซึ่งทำให้มั่นใจได้มากขึ้นว่า y (x) จะมีค่าเล็กขึ้น และเพิ่มโอกาสที่จะทำให้นุ่มนวลมากขึ้นด้วย

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

${\displaystyle y(x)\approx 2x\left\lceil {\sqrt {n}}\right\rceil }$ 

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

ความสัมพันธ์เมื่อทำไปแล้วเพียงบางส่วน (Partial relation) และวงวน (Cycles)

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

${\displaystyle {21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}}}$ 

${\displaystyle {29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}}}$ 

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

${\displaystyle {(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11^{2}{\pmod {91}}}}$ 

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

${\displaystyle (58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}$ 

${\displaystyle 14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}$ 

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

การร่อนตะแกรง

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

${\displaystyle y(x)=x^{2}-n}$ 

${\displaystyle y(x+kp)=(x+kp)^{2}-n}$ 

${\displaystyle y(x+kp)=x^{2}+2xkp+(kp)^{2}-n}$ 

${\displaystyle y(x+kp)=y(x)+2xkp+(kp)^{2}\equiv y(x){\pmod {p}}}$ 

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

ตัวอย่าง

จากดังกล่าวเราจะอธิบายตัวอย่างพื้นฐานของการประยุกต์ใช้ขั้นตอนวิธีตะแกรงกำลังสอง ในการแยกตัวประกอบของจำนวนเต็ม ซึ่งเรายกตัวอย่างตัวเลขที่มีขนาดเล็กก่อนกล่าวคือสามารถแก้ปัญหาได้โดยไม่จำเป็นต้องใช้การลดรูปด้วยการลดรูปแบบลอการึทึมหรืออื่นๆ(logarithm optimization or prime powers)โดยตัวเลขจะนำมาแยกตัวประกอบคือ N = 15347 ซึ่งจะพบว่าค่าจำนวนเต็มที่มากกว่าหรือเท่ากับรากที่สองของจำนวนดังกล่าวคือ 124 และเนื่องจาก N มีค่าเล็กมาก จึงเพียงพอที่ใช้พหุนามในการหาคำตอบ ซึ่งจะใช้สมการกำลังสองดังกล่าวคือ y(x) = (x + 124)² − 15347

การนำข้อมูลมาประมวลผล (Data processing)

เนื่องจาก N มีขนาดเล็กจึงเพียงพอที่จะใช้จำนวนเฉพาะเพียงแค่ 4 ตัวเพื่อเป็นฐานตัวประกอบ โดยจำนวนเฉพาะ 4 ตัวแรกที่ ${\displaystyle {\sqrt {15347}}{\pmod {p}}}$  ยังคงหาค่าได้คือ ซึ่งจำนวน 2, 17, 23, 29 เฉพาะดังกล่าวจะใช้ในการร่อนตะแกรงเพื่อหาตัวประกอบนั่นเอง เริ่มต้นด้วยการสร้างตะแกรงชื่อว่า ${\displaystyle V_{X}}$  ของ ${\displaystyle Y(X)=(X+\lceil {\sqrt {N}}\rceil )^{2}-N=(X+124)^{2}-15347}$  โดยเริ่มการร่อนตะแกรงสำหรับแต่ละจำนวนเฉพาะทั้ง 4 ตัวที่ได้มา โดยเลือกที่จะร่อนตะแกรงตัวเลข 0 ≤ X < 100 ของ Y(X) ดังต่อไปนี้

${\displaystyle {\begin{aligned}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{aligned}}}$ 

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

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

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

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

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

${\displaystyle {\begin{aligned}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{aligned}}}$ 

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

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

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

X + 124	Y	ตัวประกอบ
124	29	2^0 • 17^0 • 23^0 • 29^1
127	782	2^1 • 17^1 • 23^1 • 29^0
195	22678	2^1 • 17^1 • 23^1 • 29^1

การนำข้อมูลมาประมวลผลผ่านเมทริกซ์ (Matrix processing)

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

${\displaystyle {\begin{aligned}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{aligned}}}$ 

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

${\displaystyle 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 ดังกล่าวเป็น

${\displaystyle S={\begin{bmatrix}1&1&1\end{bmatrix}}}$ 

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

${\displaystyle 29\cdot 782\cdot 22678=22678^{2}}$ 

และ

${\displaystyle 124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2}}$ 

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

${\displaystyle 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 ← ${\displaystyle \lceil }$ L(n)½${\displaystyle \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 ← ${\displaystyle \lceil }$ a/p${\displaystyle \rceil }$ p while x - s ≤ b do if a < x - s < b then R[x - a] ← FactorOut(x - s, p) end if if a < x + s < b then R[x + a] ← FactorOut(x + s, p) end if x ← x + p end while end for for x ∈ [a, b] do if R[x] = 1 then L ← L ∪ {x} end if end for end for รวมทุกๆลีสต์ L จากทุกระบบประมวลผล 

สรุป

จากดังกล่าวเราจะพบว่าขั้นตอนวิธีตะแกรงแบบยกกำลังสองนั้นเป็นหนึ่งในขั้นตอนวิธีสำหรับการแยกตัวประกอบของตัวเลขที่มีขนาดใหญ่ โดยสำหรับตัวเลขที่มี 40 หลักถึง 100 หลักจะพบว่าเป็นขั้นตอนวิธีที่มีความเร็วในการแยกตัวประกอบมากที่สุด แต่ยังเป็นอันดับสองในกรณีทีจำนวนเต็มที่ต้องการแยกตัวประกอบมีมากกว่า 100 หลัก นอกจากนี้เรายังได้เห็นการลดรูปในหลายขั้นตอนเช่นการร่อนตะแกรงผ่าน (ax + b)² - N แทน x² - N และเนื่องด้วยการลดปัญหาโดยใช้วิธีดังกล่าวทำให้เราสามารถแบ่งการแยกตัวประกอบผ่านเครือข่ายขนาดใหญ่ของคอมพิวเตอร์โดยใช้สมการพหุนามแค่สมการเดียว

อ้างอิง

1. Carl Pomerance, Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, pp 89-139.
2. Pomerance, Carl (December 1996). "A Tale of Two Sieves" (PDF). Notices of the AMS. 43 (12). pp. 1473–1485.
3. Reference paper from University of Minnesota Morris

• Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective (1st ed.). Springer. ISBN 0-387-94777-9. Section 6.1: The quadratic sieve factorization method, pp. 227-244.

แหล่งข้อมูลอื่น

• Reference paper 2009-08-23 ที่ เวย์แบ็กแมชชีน มหาวิทยาลัยอิลลินอยส์ เออร์แบนา-แชมเปญจน์