ปัญหาคอนกรูเอนซ์ของจำนวนเต็มยกกำลังสองมอดุโลเอ็น

ปัญหาคอนกรูเอนซ์ของจำนวนเต็มยกกำลังสองมอดุลโลเอ็น  (Congruence of squares (mod n)) ในเรื่องทฤษฎีจำนวนนั้นได้ถูกนำมาใช้บ่อยครั้งในปัญหาที่เกี่ยวข้องกับการแยกตัวประกอบของจำนวนเต็ม  โดยเริ่มต้นจากปัญหาที่ว่า " จงหาจำนวนเต็ม x,y ที่ทำให้สมการดังกล่าวเป็นจริง เมื่อกำหนดจำนวนเต็ม n " โดย
x^2 - y^2 = n\,\!
ซึ่งการใช้ขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มของแฟร์มาต์ (Fermat's factorization method)  โดยการพยายามแยกตัวประกอบของ n ในรูปแบบ n&nbsp;=&nbsp;x2&nbsp;−&nbsp;y2&nbsp;=&nbsp;(x&nbsp;+&nbsp;y)&nbsp;(x&nbsp;−&nbsp;y). นั้น ต้องใช้เวลาที่ยาวนานมากในการค้นหาคำตอบ เพราะต้องค้นหาคำตอบที่เป็นไปได้เป็นจำนวนมาก และมีตัวเลขที่อาจเป็นคำตอบได้จริงน้อยมาก ในทางปฏิบัติจึงไม่นิยมใช้ แต่จะอาศัยการแยกตัวประกอบจากปัญหาที่ง่ายกว่า ซึ่งคือ ปัญหาคอนกรูเอนซ์ของจำนวนเต็มยกกำลังสองมอดุลโลเอ็น  ซึ่งสามารถเขียนเป็นสมการได้ดังนี้
x^2 \equiv y^2 \pmod{n}       และเพิ่มข้อกำหนดว่า   x \not\equiv \pm y \pmod{n} เพื่อจำกัดปริมาณชุดคำตอบที่ได้ให้อยู่ในขอบเขตที่ต้องการ
== ขั้นตอนวิธีการแก้ปัญหา ==
จากสมการ x^2 \equiv y^2 \pmod{n}   จะได้ว่าเราสามารถเปลี่ยนรูปของปัญหาดังนี้
:x^2 - y^2 \equiv 0 \pmod{n} 
: (x + y)(x - y) \equiv 0 \pmod{n}
ซึ่งหมายความว่า (x+y)(x-y)  สามารถหาร n ลงตัว แต่ด้วยข้อกำหนดที่ว่า    x \not\equiv \pm y \pmod{n} จึงจะได้ว่า (x+y)หรือ (x-y) ไม่สามารถหารด้วย n ลงตัวได้เพียงตัวใดตัวหนึ่ง โดยอาจใช้วิธีการแก้ปัญหาดังนี้
1.) ใช้วิธีการหาตัวหารร่วมมากโดยวิธีการของยูคลิด ซึ่งในที่นี้ (a,b) แทนตัวหารร่วมมากของ a และ b จากที่กล่าวไปดังข้างต้น จึงสามารถอธิบายได้ว่า  (x+y,n) และ (x-y,n) ต้องมีตัวประกอบทุกตัวของ n หรือสามารถอธิบายได้ว่า (x+y,n)\cdot (x-y,n) = kn  โดย k คือจำนวนเต็มบวกตัวหนึ่ง โดยเราจะพิจารณา x ที่เป็นจำนวนเต็มบวกมีค่าอยู่ระหว่าง \left\lceil\sqrt{n} \right\rceil   ถึง n และทำการค้นหา y ที่เป็นจำนวนเต็มบวกทั้งหมดที่ทำให้ x+y เป็นตัวประกอบ และทำการตรวจสอบว่าค่าของ (x-y,n) ว่ามีค่าสอดคล้องตามที่ต้องการหรือไม่ โดยวิธีการหาตัวหารร่วมมากโดยขั้นตอนวิธีการของยูคลิด(Euclidean algorithm) ดังนี้
ในการหาตัวหารร่วมมากระหว่าง a และ b โดยกำหนด a > b จะมีวิธีการหาตัวหารร่วมมากดังนี้ โดยมีข้อกำหนดว่า ทุกๆขั้นตอนที่ k ใดๆ ( k คือ 0 หรือ จำนวนเต็มบวกใดๆ)    rk−2 = qk rk−1 + rk    ซึ่ง   ( 0≤ rk   ,         qk = ±  \lfloor \frac{|a| }{|b| } \rfloor   โดย qkจะมีเครื่องหมายเป็นลบเมื่อ a เป็นจำนวนเต็มบวก และ b เป็นจำนวนเต็มลบ หรือ a เป็นจำนวนเต็มลบ และ b เป็นจำนวนเต็มบวก)   โดยจะมีขั้นตอนการดำเนินการดังนี้
a = q0 b + r0
b = q1 r0 + r1
r0 = q2 r1 + r2
r1 = q3 r2 + r3
…
rn-2 = qn rn-1
จากสมการข้างต้นจะได้ qn = (a,b) ซึ่งจะเห็นได้ว่า จะสามารถตรวจคำตอบได้อย่างรวดเร็วซึ่งใช้เวลาไม่เกิน O(h) โดย h เป็นจำนวนหลักของ b ที่เป็นจำนวนที่น้อยกว่า a จากข้อกำหนด ซึ่ง h = \lfloor k \rfloor + 1  ( โดย k= log10(b) )
2.)ทำการค้นหา x^2 \equiv z \pmod{n}   โดยค้นหา x ที่มีค่าระหว่าง  \lceil \sqrt{n} \rceil  ถึง n แล้วทำการตรวจสอบค่า z ที่ได้ว่า  \sqrt{z}  เป็นจำนวนเต็มหรือไม่ ถ้าเป็นจำนวนเต็มก็จะกำหนดให้  \sqrt{z} = y  แล้วทำการตรวจสอบตัวหารร่วมมากระหว่าง (x-y) และ (x+y) ว่าตรงตามเงื่อนไขที่กำหนดหรือไม่    ตัวอย่าง เช่น  กำหนดให้ n = 35 จงหาจำนวนเต็มบวก x,y ที่ทำให้ x^2 - y^2 \equiv 0 \pmod{n}   จะได้ว่าทำการค้นหาค่า x ตั้งแต่ 6 ถึง 35 แต่ได้พบว่าเมื่อ x = 6 จะได้ว่า
\textstyle 6^2 = 36 \equiv 1 \equiv 1^2 \pmod{n} เพราะฉะนั้นจะได้ว่า x = 6 , y = 1 เป็นคำตอบหนึ่งของสมการ ซึ่งจากการตรวจสอบ (6-1,35) = 5 และ (6+1,35) =  7 ซึ่งจะพบว่าตรงตามเงื่อนไขที่ได้กำหนดไว้ จึงถือว่า x=6,y=1 เป็นคำตอบหนึ่งของสมการนี้
== รหัสเทียมและประสิทธิภาพการทำงาน ==
จากแนวคิดขั้นตอนวิธีการแก้ปัญหาข้างต้น จะพบว่า ถ้าจะทำการเขียนรหัสเทียม (Pseudocode)   เพื่อแสดงขั้นตอนการทำงานที่เกิดขึ้น หรือเป็นการแสดงขั้นตอนเบื้องต้นที่เกิดขึ้นในการใช้คอมพิวเตอร์ในการดำเนินการแก้ไขปัญหานั้น จะสามารถแสดงขั้นตอนต่างๆเป็นรหัสเทียมได้ดังนี้
:- รหัสเทียมเพื่อการค้นหาตัวหารร่วมมาก
function gcd(a, b)
:while b ≠ 0
:begin
::t := b
::b := a mod b
::a := t
:end
:return a
จากรหัสเทียมข้างต้น function gcd จะทำการหาค่าของตัวหารร่วมมากระหว่าง a และ b แล้วทำการคืนค่าตัวหารร่วมมากกลับมาจากการเรียกใช้ function โดยจะเสียเวลาทำงานไม่เกิน  O(h)  โดย h เป็นจำนวนหลักของ b ที่เป็นจำนวนที่น้อยกว่า a จากข้อกำหนด ซึ่ง h = \lfloor k \rfloor + 1  ( โดย k= log10(b) ) ตามที่ได้กล่าวไปแล้วข้างต้น  ซึ่งเมื่อนำไปใช้ต่อไปในขั้นตอนการแก้ปัญหาต่อไปในรูปแบบที่นำเสนอไปดังข้างต้น ซึ่งอาจเขียนเป็นรหัสเทียมได้ดังนี้
สำหรับรหัสเทียมต่อไปนี้จะเป็นการนำไปใช้ต่อเพื่อหาผลลัพธ์ในรูปแบบที่ 1.)
function csquare(n)
:x = ceil(sqrt(n))
::while x  1)
::::  begin
:::::  if (gcd(x-y,n) * gcd(x+y,n) mod n == 0)
:::::  begin
::::::  print(x)        print(y)  break
:::::  end
:::: end
:::: y:=y+1
:::  end
::x := x+1
:: end
จากรหัสข้างต้น สามารถอธิบายได้ดังนี้ โดยเริ่มต้นนั้นกำหนดค่าให้ x=  \lceil \sqrt{n} \rceil  เพื่อจะได้ทำการค้นหาในช่วง  \lceil \sqrt{n} \rceil  ถึง n  ตามต้องการ แล้วจึงทำการทดสอบค่า y ที่เป็นไปได้ทั้งหมดซึ่งเป็นจำนวนเต็มบวก (ตั้งแต่ 1 ถึง x) ซึ่งถ้าพบว่าตรงตามเงื่อนไขที่ต้องการก็จะแสดงคำตอบและหยุดการทำงานทันทีเมื่อพบคำตอบชุดหนึ่งแล้ว ซึ่งจะทำให้เสียเวลาการทำงานรวมทั้งสิ้นจากการทำวงวนภายนอก Θ (n) และกระบวนการทำงานภายในที่ต้องวิ่งแปรผันตามค่า x รวมทั้งสิ้น O(x) จึงเสียเวลา O(n^2) และเมื่อคำนึงถึงการเรียกใช้ function gcd ที่มีภาระเป็น O(log n) แล้ว จึงได้ว่ากระบวนการทำงานตามรหัสเทียมดังกล่าวจะใช้เวลาในการทำงานรวมทั้งสิ้น O(n^2 log(n))
สำหรับรหัสเทียมต่อไปนี้จะเป็นการนำไปใช้ต่อเพื่อหาผลลัพธ์ในรูปแบบที่ 2.)
function csquare(n)
:x = ceil(sqrt(n))
::while x  \lceil \sqrt{n} \rceil  เพื่อจะได้ทำการค้นหาในช่วง  \lceil \sqrt{n} \rceil  ถึง n  ตามต้องการ เช่นเดียวกับรูปแบบที่ 1.) แล้วจึงทำการหาค่า z โดย x^2 \equiv z \pmod{n}   โดยทำการทดสอบว่า  \sqrt{z}  เป็นจำนวนเต็มหรือไม่  โดยถ้าเป็นจำนวนเต็มจะกำหนดให้ y =  \sqrt{z} แล้วจึงทำการตรวจคำตอบโดยการตรวจสอบตัวหารร่วมมากของ (x+y,n) และ (x-y,n) ว่าเป็นไปตามเงื่อนไขที่ได้กำหนดหรือไม่ ซึ่งถ้าพบว่าตรงตามเงื่อนไขที่ต้องการก็จะแสดงคำตอบและหยุดการทำงานทันทีเมื่อพบคำตอบชุดหนึ่งแล้ว ซึ่งจะทำให้เสียเวลาการทำงานรวมทั้งสิ้นจากการทำวงวน Θ (n) และเมื่อคำนึงถึงการเรียกใช้ function gcd ที่มีภาระเป็น O(log n) แล้ว จึงได้ว่ากระบวนการทำงานตามรหัสเทียมดังกล่าวจะใช้เวลาในการทำงานรวมทั้งสิ้น O(n log(n)) ซึ่งจะเห็นได้ว่าอาจทำงานเร็วกว่ารูปแบบที่ 1.) แต่ก็จะใช้หน่วยความจำที่มากกว่าเพราะต้องคำนวณ  x^2  mod n
==ปัญหาที่เกี่ยวข้อง==
สำหรับปัญหาคอนกรูเอนซ์ของจำนวนเต็มยกกำลังสองมอดุลโลเอ็นนั้น โดยวิธีการแก้ปัญหาที่ได้นำเสนอนั้น เป็นวิธีการพื้นฐานเท่านั้น ซึ่งได้มีผู้พัฒนาวิธีการแก้ปัญหาดังกล่าวเพื่อให้มีประสิทธิภาพยิ่งขึ้นในทางปฏิบัติ เช่น
วิธีการแยกตัวประกอบแบบดิกซ์ซัน(Dixon's factorization method)  รวมถึงเป็นพื้นฐานในการแก้ไขปัญหาอื่นๆอีกมากที่เกี่ยวข้องกับทฤษฎีจำนวน เช่น ปัญหาตะแกรงกำลังสอง(Quadratic sieve) , ปัญหาตะแกรงของจำนวนเต็มใดๆ(General number field sieve) เป็นต้น
==เพิ่มเติม==
สำหรับนิยามสัญกรณ์เชิงเวลาที่ได้ใช้เพื่อประเมินประสิทธิภาพเชิงเวลา เช่น สัญกรณ์โอใหญ่ (Big O-notation)  รวมถึง ความรู้เกี่ยวกับสัญกรณ์เชิงเวลาในรูปแบบภาพยนตร์เพื่อการศึกษาภาษา  ซึ่งสามารถค้นคว้าเพิ่มเติมได้ทั้งในรูปแบบของภาพยนตร์เพื่อการศึกษาและบทความเพื่อความเข้าใจ รวมถึงข้อมูลอื่นๆเพื่อประกอบการแก้ปัญหานั้น เช่น บทความทางด้านความรู้ต่างๆเกี่ยวข้องกับทฤษฎีจำนวน เช่น ความรู้ที่เกี่ยวข้องกับเลขคณิตมอดุลาร์(Modular arithmetic) รวมถึงความสัมพันธ์ในรูปแบบคอนกรูเอนซ์(Congruence relation) และสัญลักษณ์ต่างๆที่ใช้ในการเขียนรหัสเทียม รวมถึงหลักภาษาในการเขียนรหัสเทียมเพื่อบรรยายขั้นตอนวิธีเพื่อการทำงานตามความต้องการ สามารถอ่านเพิ่มเติมได้ในบทความ  How to write Pseudocode  (ในรูปแบบ.doc) รวมถึง  รวมถึงความรู้เพื่อประกอบความเข้าใจอื่นๆซึ่งสามารถพบได้ในส่วนของอ้างอิง
== อ้างอิง ==
หนังสือประกอบการอ้างอิง
.
.
ขั้นตอนวิธีการแยกตัวประกอบจำนวนเต็ม
เลขคณิตมอดุลาร์