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

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

ขั้นตอนวิธีดังกล่าวมีแนวความคิดมาจากขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มของแฟร์มาต์ (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ᵐ ⁺ ⁿ = aᵐaⁿ
จากดังกล่าวชัดเจนว่าเมื่อตัวเลขในเวกเตอร์ชี้กำลังของจำนวนๆหนึ่งนั้นเป็นจำนวนเต็มคู่ทั้งหมดนั่นคือจะได้ว่าจำนวนดังกล่าวสามารถเขียนได้อยู่ในรูปของกำลังสมบูรณ์ของจำนวนเต็ม ยกตัวอย่างเช่นเมื่อเรานำเวกเตอร์ (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 นั่นเอง) ซึ่งจะพิจารณากันต่อไป

ตัวอย่าง

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

รหัสเทียม

จากดังกล่าวจะพิจารณาอ้างอิงถึงรหัสเทียมที่จำเป็นต้องใช้ในการแก้ปัญหาตะแกรงกำลังสองดังต่อไปนี้ ซึ่งง่ายต่อการเข้าใจและอยากให้ผู้อ่านไปศึกษาเพิ่มเติมด้วยตัวเอง
ขั้นตอนวิธีที่ 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 หรือไม่ โดยพิจารณาให้ PB เป็นเซ็ตของจำนวนเฉพาะที่น้อยกว่า 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 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] ← x² - N
 end for
 for p ∈ F do
  หาค่า s ซึ่งทำให้ s2= N mod p
  x ← \lceila/p\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 และเนื่องด้วยการลดปัญหาโดยใช้วิธีดังกล่าวทำให้เราสามารถแบ่งการแยกตัวประกอบผ่านเครือข่ายขนาดใหญ่ของคอมพิวเตอร์โดยใช้สมการพหุนามแค่สมการเดียว