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

ปัญหาคอนกรูเอนซ์ของจำนวนเต็มยกกำลังสองมอดุลโลเอ็น  ในเรื่องทฤษฎีจำนวนนั้นได้ถูกนำมาใช้บ่อยครั้งในปัญหาที่เกี่ยวข้องกับการแยกตัวประกอบของจำนวนเต็ม โดยเริ่มต้นจากปัญหาที่ว่า "จงหาจำนวนเต็ม x, y ที่ทำให้สมการดังกล่าวเป็นจริง เมื่อกำหนดจำนวนเต็ม n" โดย
<math>x^2 - y^2 = n\,\!</math> 
ซึ่งการใช้ขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มของแฟร์มาต์  โดยการพยายามแยกตัวประกอบของ n ในรูปแบบ "n" = "x"2 − "y"2 = ("x" + "y") ("x" − "y") นั้น ต้องใช้เวลาที่ยาวนานมากในการค้นหาคำตอบ เพราะต้องค้นหาคำตอบที่เป็นไปได้เป็นจำนวนมาก และมีตัวเลขที่อาจเป็นคำตอบได้จริงน้อยมาก ในทางปฏิบัติจึงไม่นิยมใช้ แต่จะอาศัยการแยกตัวประกอบจากปัญหาที่ง่ายกว่า ซึ่งคือ ปัญหาคอนกรูเอนซ์ของจำนวนเต็มยกกำลังสองมอดุลโลเอ็น ซึ่งสามารถเขียนเป็นสมการได้ดังนี้ 
<math>x^2 \equiv y^2 \pmod{n} </math> 
และเพิ่มข้อกำหนดว่า <math> x \not\equiv \pm y \pmod{n}</math> เพื่อจำกัดปริมาณชุดคำตอบที่ได้ให้อยู่ในขอบเขตที่ต้องการ
ขั้นตอนวิธีการแก้ปัญหา.
จากสมการ <math>x^2 \equiv y^2 \pmod{n} </math> จะได้ว่าเราสามารถเปลี่ยนรูปของปัญหาดังนี้ 
<math>x^2 - y^2 \equiv 0 \pmod{n} </math> 
<math> (x + y)(x - y) \equiv 0 \pmod{n}</math> 
ซึ่งหมายความว่า <math>(x+y)(x-y)</math> สามารถหาร <math>n</math> ลงตัว แต่ด้วยข้อกำหนดที่ว่า <math> x \not\equiv \pm y \pmod{n}</math> จึงจะได้ว่า <math>(x+y)</math>หรือ <math>(x-y)</math> ไม่สามารถหารด้วย n ลงตัวได้เพียงตัวใดตัวหนึ่ง โดยอาจใช้วิธีการแก้ปัญหา ดังนี้ 
1. ใช้วิธีการหาตัวหารร่วมมากโดยวิธีการของยูคลิด ซึ่งในที่นี้ <math>(a, b)</math> แทนตัวหารร่วมมากของ a และ b จากที่กล่าวไปดังข้างต้น จึงสามารถอธิบายได้ว่า <math>(x+y, n)</math> และ <math>(x-y, n)</math> ต้องมีตัวประกอบทุกตัวของ n หรือสามารถอธิบายได้ว่า <math>(x+y, n)\cdot (x-y, n) = kn </math> โดย k คือจำนวนเต็มบวกตัวหนึ่ง โดยเราจะพิจารณา <math>x</math> ที่เป็นจำนวนเต็มบวกมีค่าอยู่ระหว่าง <math>\left\lceil\sqrt{n} \right\rceil </math> ถึง <math>n</math> และทำการค้นหา y ที่เป็นจำนวนเต็มบวกทั้งหมดที่ทำให้ x+y เป็นตัวประกอบ และทำการตรวจสอบว่าค่าของ (x-y, n) ว่ามีค่าสอดคล้องตามที่ต้องการหรือไม่ โดยวิธีการหาตัวหารร่วมมากโดยขั้นตอนวิธีการของยูคลิด  ดังนี้
ในการหาตัวหารร่วมมากระหว่าง a และ b โดยกำหนด a > b จะมีวิธีการหาตัวหารร่วมมากดังนี้ โดยมีข้อกำหนดว่า ทุก ๆ ขั้นตอนที่ k ใด ๆ (k คือ 0 หรือ จำนวนเต็มบวกใด ๆ) "r""k"−2 = "q""k" "r""k"−1 + "r""k" ซึ่ง (0≤ "r""k", "q""k" <math>=</math> ± <math> \lfloor \frac{|a| }{|b| } \rfloor </math> โดย "q""k" จะมีเครื่องหมายเป็นลบเมื่อ a เป็นจำนวนเต็มบวก และ b เป็นจำนวนเต็มลบ หรือ a เป็นจำนวนเต็มลบ และ b เป็นจำนวนเต็มบวก) โดยจะมีขั้นตอนการดำเนินการดังนี้
 "a" = "q"0 "b" + "r"0 
 "b" = "q"1 "r"0 + "r"1
 "r"0 = "q"2 "r"1 + "r"2
 "r"1 = "q"3 "r"2 + "r"3
"r"n-2 = "q"n "r"n-1 
จากสมการข้างต้นจะได้ "q"n = <math>(a,b)</math> ซึ่งจะเห็นได้ว่า จะสามารถตรวจคำตอบได้อย่างรวดเร็วซึ่งใช้เวลาไม่เกิน O(h) โดย h เป็นจำนวนหลักของ b ที่เป็นจำนวนที่น้อยกว่า a จากข้อกำหนด ซึ่ง h = <math>\lfloor k \rfloor</math> + 1 (โดย k= log10(b))
2. ทำการค้นหา <math>x^2 \equiv z \pmod{n} </math> โดยค้นหา x ที่มีค่าระหว่าง <math> \lceil \sqrt{n} \rceil </math> ถึง n แล้วทำการตรวจสอบค่า z ที่ได้ว่า <math> \sqrt{z} </math> เป็นจำนวนเต็มหรือไม่ ถ้าเป็นจำนวนเต็มก็จะกำหนดให้ <math> \sqrt{z} = y </math> แล้วทำการตรวจสอบตัวหารร่วมมากระหว่าง (x-y) และ (x+y) ว่าตรงตามเงื่อนไขที่กำหนดหรือไม่ ตัวอย่างเช่น กำหนดให้ n = 35 จงหาจำนวนเต็มบวก x,y ที่ทำให้ <math>x^2 - y^2 \equiv 0 \pmod{n} </math> จะได้ว่าทำการค้นหาค่า x ตั้งแต่ 6 ถึง 35 แต่ได้พบว่าเมื่อ x = 6 จะได้ว่า
<math>\textstyle 6^2 = 36 \equiv 1 \equiv 1^2 \pmod{n}</math> เพราะฉะนั้นจะได้ว่า x = 6, y = 1 เป็นคำตอบหนึ่งของสมการ ซึ่งจากการตรวจสอบ (6-1, 35) = 5 และ (6+1, 35) = 7 ซึ่งจะพบว่าตรงตามเงื่อนไขที่ได้กำหนดไว้ จึงถือว่า x=6, y=1 เป็นคำตอบหนึ่งของสมการนี้
รหัสเทียมและประสิทธิภาพการทำงาน.
จากแนวคิดขั้นตอนวิธีการแก้ปัญหาข้างต้น จะพบว่า ถ้าจะทำการเขียนรหัสเทียม  เพื่อแสดงขั้นตอนการทำงานที่เกิดขึ้น หรือเป็นการแสดงขั้นตอนเบื้องต้นที่เกิดขึ้นในการใช้คอมพิวเตอร์ในการดำเนินการแก้ไขปัญหานั้น จะสามารถแสดงขั้นตอนต่าง ๆ เป็นรหัสเทียมได้ดังนี้
รหัสเทียมเพื่อการค้นหาตัวหารร่วมมาก
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 = <math>\lfloor k \rfloor</math> + 1 (โดย k= log10(b)) ตามที่ได้กล่าวไปแล้วข้างต้น ซึ่งเมื่อนำไปใช้ต่อไปในขั้นตอนการแก้ปัญหาต่อไปในรูปแบบที่นำเสนอไปดังข้างต้น ซึ่งอาจเขียนเป็นรหัสเทียมได้ดังนี้ 
สำหรับรหัสเทียมต่อไปนี้จะเป็นการนำไปใช้ต่อเพื่อหาผลลัพธ์ในรูปแบบที่ 1.
function csquare(n)
x = ceil(sqrt(n)) 
while x <= n
 begin
 y := 1 
 while y < x
 begin
 if (gcd(x+y,n) > 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= <math> \lceil \sqrt{n} \rceil </math> เพื่อจะได้ทำการค้นหาในช่วง <math> \lceil \sqrt{n} \rceil </math> ถึง n ตามต้องการ แล้วจึงทำการทดสอบค่า y ที่เป็นไปได้ทั้งหมดซึ่งเป็นจำนวนเต็มบวก (ตั้งแต่ 1 ถึง x) ซึ่งถ้าพบว่าตรงตามเงื่อนไขที่ต้องการก็จะแสดงคำตอบและหยุดการทำงานทันทีเมื่อพบคำตอบชุดหนึ่งแล้ว ซึ่งจะทำให้เสียเวลาการทำงานรวมทั้งสิ้นจากการทำวงวนภายนอก Θ (n) และกระบวนการทำงานภายในที่ต้องวิ่งแปรผันตามค่า x รวมทั้งสิ้น O(x) จึงเสียเวลา O(<math>n^2</math>) และเมื่อคำนึงถึงการเรียกใช้ function gcd ที่มีภาระเป็น O(log n) แล้ว จึงได้ว่ากระบวนการทำงานตามรหัสเทียมดังกล่าวจะใช้เวลาในการทำงานรวมทั้งสิ้น O(<math>n^2</math> log(n)) 
สำหรับรหัสเทียมต่อไปนี้จะเป็นการนำไปใช้ต่อเพื่อหาผลลัพธ์ในรูปแบบที่ 2.
function csquare(n)
x = ceil(sqrt(n)) 
while x <= n
begin
 z := (x*x) mod n 
 if (sqrt(z) is integer)
 begin
 y := sqrt(z)
 if (gcd(x-y,n) * gcd(x+y,n) mod n == 0) 
 begin 
 print(x) print(y) break
 end
 end
x := x+1
end
จากรหัสข้างต้น สามารถอธิบายได้ดังนี้ โดยเริ่มต้นนั้นกำหนดค่าให้ x= <math> \lceil \sqrt{n} \rceil </math> เพื่อจะได้ทำการค้นหาในช่วง <math> \lceil \sqrt{n} \rceil </math> ถึง n ตามต้องการ เช่นเดียวกับรูปแบบที่ 1. แล้วจึงทำการหาค่า z โดย <math>x^2 \equiv z \pmod{n} </math> โดยทำการทดสอบว่า <math> \sqrt{z} </math> เป็นจำนวนเต็มหรือไม่ โดยถ้าเป็นจำนวนเต็มจะกำหนดให้ y = <math> \sqrt{z}</math> แล้วจึงทำการตรวจคำตอบโดยการตรวจสอบตัวหารร่วมมากของ (x+y, n) และ (x-y, n) ว่าเป็นไปตามเงื่อนไขที่ได้กำหนดหรือไม่ ซึ่งถ้าพบว่าตรงตามเงื่อนไขที่ต้องการก็จะแสดงคำตอบและหยุดการทำงานทันทีเมื่อพบคำตอบชุดหนึ่งแล้ว ซึ่งจะทำให้เสียเวลาการทำงานรวมทั้งสิ้นจากการทำวงวน Θ (n) และเมื่อคำนึงถึงการเรียกใช้ function gcd ที่มีภาระเป็น O(log n) แล้ว จึงได้ว่ากระบวนการทำงานตามรหัสเทียมดังกล่าวจะใช้เวลาในการทำงานรวมทั้งสิ้น O(n log(n)) ซึ่งจะเห็นได้ว่าอาจทำงานเร็วกว่ารูปแบบที่ 1. แต่ก็จะใช้หน่วยความจำที่มากกว่าเพราะต้องคำนวณ <math> x^2 </math> mod n
ปัญหาที่เกี่ยวข้อง.
สำหรับ ปัญหาคอนกรูเอนซ์ของจำนวนเต็มยกกำลังสองมอดุลโลเอ็น นั้น โดยวิธีการแก้ปัญหาที่ได้นำเสนอนั้น เป็นวิธีการพื้นฐานเท่านั้น ซึ่งได้มีผู้พัฒนาวิธีการแก้ปัญหาดังกล่าวเพื่อให้มีประสิทธิภาพยิ่งขึ้นในทางปฏิบัติ เช่น 
วิธีการแยกตัวประกอบแบบดิกซ์ซัน  รวมถึงเป็นพื้นฐานในการแก้ไขปัญหาอื่น ๆ อีกมากที่เกี่ยวข้องกับทฤษฎีจำนวน เช่น ปัญหาตะแกรงกำลังสอง , ปัญหาตะแกรงของจำนวนเต็มใด ๆ  เป็นต้น
เพิ่มเติม.
สำหรับนิยามสัญกรณ์เชิงเวลาที่ได้ใช้เพื่อประเมินประสิทธิภาพเชิงเวลา เช่น สัญกรณ์โอใหญ่  รวมถึง ความรู้เกี่ยวกับสัญกรณ์เชิงเวลาในรูปแบบภาพยนตร์เพื่อการศึกษาภาษา ซึ่งสามารถค้นคว้าเพิ่มเติมได้ทั้งในรูปแบบของภาพยนตร์เพื่อการศึกษาและบทความเพื่อความเข้าใจ รวมถึงข้อมูลอื่น ๆ เพื่อประกอบการแก้ปัญหานั้น เช่น บทความทางด้านความรู้ต่าง ๆ เกี่ยวข้องกับทฤษฎีจำนวน เช่น ความรู้ที่เกี่ยวข้องกับเลขคณิตมอดุลาร์  รวมถึงความสัมพันธ์ในรูปแบบคอนกรูเอนซ์  และสัญลักษณ์ต่าง ๆ ที่ใช้ในการเขียนรหัสเทียม รวมถึงหลักภาษาในการเขียนรหัสเทียมเพื่อบรรยายขั้นตอนวิธีเพื่อการทำงานตามความต้องการ สามารถอ่านเพิ่มเติมได้ในบทความ How to write Pseudocode (ในรูปแบบ .doc) รวมถึง รวมถึงความรู้เพื่อประกอบความเข้าใจอื่น ๆ ซึ่งสามารถพบได้ในส่วนของอ้างอิง