ขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มของแฟร์มาต์

วิธีแยกตัวประกอบของแฟร์มาต์  ตั้งชื่อตามผู้คิดค้นคือ ปิแยร์ เดอ แฟร์มาต์ (Pierre de Fermat) โดยเป็นผลงานหนึ่งที่เกี่ยวกับทฤษฎีจำนวน ที่ใช้ในการแยกตัวประกอบโดยมีหลักการที่ว่า จำนวนเต็มคี่ใด ๆ สามารถแทนได้ด้วยผลต่างของเลขกำลังสองได้ดังนี้
 <math>N=x^2-y^2 \,</math>
จากการสังเกตนี้ ทำให้สามารถนำไปประยุกต์ใน ตะแกรงกำลังสอง (quadratic sieve) และ วิธีแยกตัวประกอบของดิกสัน (Dixon's Factorization Method)
จากสมบัติดังกล่าวสามารถมองได้ว่า
 <math>N= a b=(x+y)(x-y)\ </math>
โดยที่ <math>(a > b) </math> ถ้า a หรือ b ไม่เท่ากับ 1 แสดงว่า a กับ b เป็นตัว ประกอบแท้ของ N สามารถเขียนแยกได้
 <math> a = x+y\ </math>
 <math> b = x-y\ </math>
หรือ
 <math> a+b=2x\ </math>
 <math> a-b=2y\ </math>
ดังนั้น
 <math> N= a b = x^2-y^2=1/4 ((a+b)^2 - (a-b)^2)) =((a+b)/2)^2- ((a-b)/2)^2 \ </math>
เนื่องจาก N เป็นจำนวนเต็มคี่ แล้ว a และ b เป็นจำนวนคี่ด้วย ดังนั้นจะได้ทั้งสองส่วนของสมการเป็นจำนวนเต็มและยังเขียนได้ว่า
 <math> x^2 \equiv y^2(mod N) </math>
จากสมบัติเหล่านี้จะนำมาใช้แยกตัวประกอบจำนวนเต็ม เมื่อเทียบกับ การหารเชิงทดลอง (trial division) แล้ววิธีนี้อาจจะมีประสิทธิภาพน้อยกว่า แต่เมื่อนำทั้ง วิธีการแยกตัวประกอบของแฟร์มาต์ กับการหารเชิงทดลอง มารวมกันแล้วจะทำให้ได้ประสิทธิภาพที่มากกว่าการใช้วิธีใดวิธีหนึ่ง
วิธีการเบื้องต้น.
จากทฤษฎีข้างต้นหาค่า a ที่ทำให้ <math> b2=a^2-N </math> สามารถยกกำลังสองเป็นจำนวนเต็มได้วิธีการดังกล่าวสามารถเขียนรหัสเทียมได้ ดังนี้
หลักการเบื้องต้น.
หลักการคือต้องการแยกตัวประกอบของ N ซึ่ง N ควรเป็นจำนวนคี่ถ้าหากเป็นจำนวนคู่สามารถแยกตัวประกอบ 2 ออกไปก่อน จากนั้นหาตัวประกอบโดยหาค่า a และ b ที่เป็นจำนวนเต็มน้อยที่สุดที่ <math>a-b \leq \sqrt{N} \leq a+b </math> โดยที่ <math>a-b=N/(a+b)\ </math> และถ้าแยกตัวประกอบได้ N=N*1 จะได้ว่า N เป็นจำนวนเฉพาะ โดยทดสอบทีละเงื่อนไขและบวกค่า a เพิ่มขึ้นเรื่อย ๆ จนพบคำตอบที่ได้ตัวประกอบลู่เข้ารากของ N มากที่สุด ตัวอย่างเช่น N=5959
ประสิทธิภาพ.
เมื่อให้ <math>N=cd</math> จะได้ว่าจำนวนครั้งในการวนลูปคือ <math> (c+d)/2 - \sqrt N = (\sqrt d - \sqrt c)^2 / 2 = (\sqrt N - c)^2 / 2c</math> ของกรณีที่แย่ที่สุดคือเมื่อ N เป็นจำนวนเฉพาะ ซึ่งจะได้ประสิทธิภาพการทำงานเป็น <math>O(N)</math> แต่ถ้ากรณีที่ c ต่างกับ รากของ N น้อยกว่า <math>{\left(4N\right)}^{1/4}</math> ถ้าใช้จำนวนการทำงานแค่ครั้งเดียว หรือถ้าคำตอบจริงยิ่งเข้าไป รากของ N มากเท่าไหร่ประสิทธิภาพในทางปฏิบัติก็จะดีขึ้น ซึ่งจากทั้งหมดแสดงให้เห็นว่าประสิทธิภาพของวิธีแยกตัวประกอบของแฟร์มาต์จะขึ้นอยู่กับค่าของ N
การประยุกต์วิธีของแฟร์มาต์กับการหารเชิงทดลอง.
จากวิธีของแฟร์มาต์จะเห็นว่าได้ประสิทธิภาพคือ <math> O(N) </math> เมื่อเทียบกับ วิธีการหารเชิงทดลองที่ได้ประสิทธิภาพที่ดีกว่าคือ O(√n / log n) ซึ่งจะเห็น ดังนั้น เราสามารถเพิ่มประสิทธิภาพให้กับ วิธีการหาตัวประกอบทั้งสองให้ดีขึ้นได้โดยนำทั้งสองวิธีมารวมกันโดยใช้วิธีการหาตัวประกอบของแฟร์มาต์เป็นหลัก และใช้วิธีการหารเชิงทดลองตัดกรณีที่ใช้พิจารณามาก ๆ ได้ จาก
ทฤษฏีการหารเชิงทดลอง ตัวประกอบที่เป็นจำนวนเฉพาะของจำนวนเต็มใด ๆ จะมีค่าน้อยกว่าหรือเท่ากับรากที่สองของจำนวนเต็มนั้น
จากตัวอย่างให้ N=123456789123 ใช้วิธีการแยกตัวประกอบของแฟร์มาต์ ได้ดังนี้
 <math>\lceil\sqrt{N} \rceil = 351365 </math>
 <math> 351365^2-N=574102 ; \sqrt{574102}=757.7</math>
 <math> 351366^2-N=1276833 ; \sqrt{1276833}=1129.97 </math>
 <math> 351367^2-N=1979566 ; \sqrt{1979566}=1406.97 </math>
 <math> 351368^2-N=2682301 ; \sqrt{2682301}=1637.77 </math>
จริง ๆ แล้วจะเห็นว่าเราทำมาได้ 4 ขั้นตอนแล้วแต่ยังไม่ได้ตัวประกอบเพราะว่า b2=1637.77 ไม่ใช่จำนวนเต็มแต่เมื่อเราคำนวณ a-b2 จะได้ว่า 357368-1638=349730 ถ้าอาศัยทฤษฎีของการหารเชิงทดลองจะได้ว่าการที่จะหาตัวประกอบเฉพาะของ N ทำได้จากการทดลองหาจาก 0 ถึง 351365 (จาก การหารเชิงทดลอง) แต่กรณีนี้หลังจากที่เราทำการแยกตัวประกอบของแฟร์มาต์ยังไม่เสร็จแต่เราจะได้ว่า เราทำหาการหารเชิงทดลองโดยหาแค่จาก 0 ถึง 349730 พอซึ่งสามารถลดจากเดิมได้เป็นพันรอบโดยแค่ทำการหาตัวประกอบแบบแฟร์มาต์แค่ 4 รอบก่อน ซึ่งจากตัวอย่างด้านบนจะเห็นว่าสามารถหาค่าแล้วได้ b2 ออกมาเรื่อย ๆ ทำให้ยิ่งเข้าใกล้ค่าตัวประกอบจริงมากขึ้นและยิ่งทำให้เมื่อนำไปหาการหารเชิงทดลองต่อมีแนวโน้มที่จะได้ประสิทธิภาพที่ดีขึ้น
ดังนั้น จึงสามารถเขียนในรูปของความสัมพันธ์ทั่วไป ถ้าเราให้ <math> d> \sqrt{N} </math> จะได้ว่าถ้าเราใช้ การแยกตัวประกอบของแฟร์มาต์ในช่วงระหว่าง <math> \sqrt{N} </math> กับ <math> d\ </math> จะทำให้ได้ขอบเขตของการหาในวิธีการหารเชิงทดลองคือ <math> d-\sqrt{d^2-N}</math> ตัวอย่างเช่นถ้า N=2345678917 โดยให้ d=48436 จะได้ขอบเขตของการหารเชิงทดลองคือ 47830 และถ้ากำหนดให้ d=55000 จะได้ขอบเขตคือ 28937
การปรับปรุงกับตะแกรง.
บ้างครั้งเราไม่มีความจำเป็นที่จะต้องหา รากที่สองของ <math> a^2-N </math> หรือแม้แต่ค่าของ a ทุกค่าเราสามารถพิจารณาได้จากค่า มอดุโล ของมันเช่นจากตัวอย่าง
<table>
<tr><td>a:</td> <td>48433</td><td>48434</td> <td>48435</td> <td>48436</td> </tr>
<tr><td>b2:</td> <td>76572</td><td>173439</td><td>270308</td><td>367179</td></tr>
<tr><td>b:</td> <td>276.7</td><td>416.5</td> <td>519.9</td> <td>605.9</td> </tr>
</table>
กรณีดังกล่าวจะเห็นได้ว่าไม่มีค่า b หรือรากที่สองของ b2 เป็นจำนวนเต็ม จากสมการ <math> a^2-N </math> เมื่อพิจารณาค่า <math>a^2</math>เมื่อ a เป็นจำนวนเต็ม จากตัวอย่างดังนี้
<table>
<tr><td>n</td> <td>1</td> <td>2</td> <td>3</td> <td>4</td> <td>5</td> <td>6</td> <td>7</td> <td>8</td> <td>9</td> <td>10</td> <td>11</td> <td>12</td> <td>13</td> <td>14</td> <td>15</td> <td>16</td> <td>17</td> <td>18</td> <td>19</td> <td>20</td> </tr>
<tr><td><math>n^2</math></td> <td>1</td> <td>4</td> <td>9</td> <td>16</td> <td>25</td> <td>36</td> <td>49</td> <td>64</td> <td>81</td> <td>100</td> <td>121</td> <td>144</td> <td>169</td> <td>196</td> <td>225</td> <td>256</td> <td>289</td> <td>324</td> <td>361</td> <td>400</td> </tr>
</table>
จะเห็นได้ว่ากำลังสองของเลขจำนวนเต็มมักจะลงท้ายด้วย 0, 1, 4, 5, 9, 16 modulo 20 จากตารางด้านบนจะพบว่าค่าที่ a mod 10 มีค่าเดียวกันยกจำลังสองแล้วจะได้เลขลงท้ายค่าเดียวกันเท่ากันด้วย หรือจะเรียกได้ว่าจะซ้ำรอบเดิมเมื่อ a ถูกเพิ่มเป็น 10 จากตัวอย่างดังกล่าวจะได้ว่าถ้าเราเพิ่ม -17 mod 20 (3), <math>a^2-N</math> จะได้เลขลงท้ายดังกล่าวออกมาเป็น 3, 4, 7, 8, 12, 19 modulo 20 จะเห็นว่ามี 4 จากรายการนี้ที่สามารถเป็นกำลังสองได้ (เทียบอันดับกันของ <math>a^2</math> และ <math>a^2-N</math>) ดังนั้น <math> a^2 </math> ต้องเป็น 1 mod 20 หรือหมายถึง a คือ 1, 9 mod 10 ซึ่งจะทำให้ b2 ลง ท้ายด้วย 4 mod 20 และ ถ้าเป็นกำลังสองอีก b จะลงท้ายด้วย 2, 8 mod 10
ตัวอย่างของการใช้ มอดุลัส ค่าต่าง ของ N=2345678917
<table>
<tr><td>มอดุโล 16:</td><td>กำลังสองคือ</td> <td>0, 1, 4, or 9</td> </tr>
<tr><td></td> <td>N mod 16 is</td><td>5</td></tr>
<tr><td></td> <td>ดังนั้น <math>a^2</math> สามารถเป็นได้คือ </td><td>9</td></tr>
<tr><td></td> <td>และ <math>a</math> ต้องเป็น </td><td>3 , 5 modulo 16</td></tr>
<tr><td>มอดุโล 9:</td> <td>กำลังสองคือ</td> <td>0, 1, 4, or 7</td> </tr>
<tr><td></td> <td>N mod 9 is</td><td>7</td></tr>
<tr><td></td> <td>ดังนั้น <math>a^2</math>สามารถเป็นได้คือ</td><td>7</td></tr>
<tr><td></td> <td>และ <math>a</math> ต้องเป็น</td><td>4 , 5 modulo 9</td></tr>
</table>
โดยทั่วไปจะเลือกค่าที่เป็นกำลังของจำนวนเฉพาะที่แตกต่างกันสำหรับ มอดุลัส
เมื่อให้ลำดับของ a-value(start,end,and step) และค่าค่า modulus ซึ่งจะมีกระบวนการได้ ดังนี้
การปรับปรุงตัวคูณ กับวิธีการของเลห์แมน.
วิธีการของแฟร์มาต์จะทำงานได้ดีเมื่อตัวประกอบนั้นอยู่ใกล้กับค่า รากที่สองของ N ซึ่งเราอาจจะจัดการให้สิ่งนั้นเกิดขึ้นได้ ถ้ารู้ค่าอัตราส่วนโดยประมาณของ d/c โดยกำหนดให้ N แยกตัวประกอบได้ N = cd แล้ว สามารถเลือกอัตราส่วนจำนวน v/u ที่ใกล้กับค่านั้น แล้วประมาณได้ว่า N*u*v = (c*v)*(d*u) ซึ่งทำให้ใช้เมื่อวิธีของแฟร์มาต์จทำให้สามารถหาในรูป N=N*u*v ได้เร็วกว่า จากนั้นหาตัวหารร่วมมาก ของ factor ที่ได้กับ N เดิม จะได้ gcd(N,vc)= c และ gcd(N,du)=d (เว้น c หาร u หรือ d หาร v ลงตัว)
โดยปกติเราไม่สามารถรู้ค่าอัตราส่วนนั้นได้แต่ถ้าเลือกหนึ่งคือพยายามลอง u/v หลาย ๆ ค่า และพยายาแยกตัวประกอบกับ Nuv ดังกล่าวซึ่งได้มีนักคณิตศาสตร์ท่าหนึ่ง อาร์ เลห์แมน (R. Lehman)ได้คิดค้นระเบียบวิธีการที่เป็นระบบไว้สำหรับแก้ปัญหาด้วยแนวคิดนี้ ซึ่งสามารถเพิ่มประสิทธิภาพให้ การแปลงแบบแฟร์มาต์ที่เพิ่มวิธีการหารเชิงทดลอง ให้สามารถแยกตัวประกอบของ N ได้ในเวลา O(N1 / 3) ในบทความชื่อว่า การแยกตัวประกอบจำนวนเต็มขนาดใหญ่ (R. Lehman, "Factoring Large Integers", Mathematics of Computation)
วิธีการดูเหมือนกับการแยกตัวประกอบของแฟร์มาต์ โดยให้ <math> k\geq1 </math> และ <math> x=\lceil 2\sqrt{kN}\rceil </math> ตรวจสอบว่า <math> (x+m)^2-4kN \ </math>คือกำลังสองสำหรับ <math> m\geq 0 </math> จากนั้นเราแค่จำเป็นต้องตรวจสอบ <math>k\leq N^{1/3}</math> และ m สำหรับแต่ละ <math> m^2k\leq N^{1/3}</math> เพื่อหาตัวประกอบที่ <math> > N^{1/3} \ </math> จะเห็นว่าวิธีนี้ใช้เวลาเป็น <math> O(N^{1 / 3})\ </math> เราสามารถพิสูจน์ขั้นตอนเหล่านี้ได้โดยใช้วิธีการทั่วไปของ การประมาณปกติ(normal approximation)
รหัสเทียม.
ประสิทธิภาพของรหัสเทียมดังกล่าวคือ <math> O(N^{1 / 3})\ </math>
สรุปและการประยุกต์อื่น ๆ.
การแยกตัวประกอบของแฟร์มาต์เป็นวิธีหนึ่งที่ใช้ในการแยกตัวประกอบของจำนวนเต็มโดยใช้สมบัติของผลต่างกำลังสองที่เป็นจำนวนเต็มวิธีพื้นฐานปกติจะมีประสิทธิภาพที่ไม่ดีนักไม่ต่างกับการค้นหาจำนวนเต็มทุกตัวจาก 1 ถึง N (<math> O(n)\ </math>) แต่จะมีประสิทธิภาพสูงถ้าคำตอบเข้าใกล้รากที่สองของ N และสามารถนำคุณสมบัติทางคณิตศาสตร์นี้ไปประยุกต์หรือปรับปรุงกับวิธีอื่น เช่น การหารเชิงทดลอง ทำให้เห็นว่าได้ประสิทธิภาพที่ดีกว่าการใช้ตัวใดตัวหนึ่งโดยอาศัยการแยกตัวประกอบของแฟร์มาต์มาใช้ลดช่วงของการค้น หรือประยุกต์กับวิธีของเลห์แมน ดังที่ได้กล่าวไปที่ทำให้ได้ประสิทธิภาพเป็น <math> O(N^{1 / 3})\ </math> โดยอาศัยสมบัติการความมีประสิทธิภาพสูงเมื่อเข้าใกล้รากที่สองของ N นอกจากนั้นยังเป็นรากฐานของเรื่อง ตะแกรงกำลังสอง (quadratic sieve) และ การกรองตัวเลขในขอบเขตแบบธรรมดา (general number field sieve) ซึ่งเป็นระเบียบวิธีการที่รู้จักดีสำหรับการแยกตัวประกอบ "กรณีที่แย่ที่สุด" จำนวนกึ่งเฉพาะขนาดใหญ่ ในขั้นตอน วิธีการของตะแกรงกำลังสอง ที่แตกต่างกับการแยกตัวประกอบของแฟร์มาต์ คือ แทนที่จะหาว่า <math>a^2 - n</math> เป็นกำลังสองหรือไม่เป็นลำดับ แต่จะหาเซตย่อยของส่วนประกอบของลำดับดังกล่าวที่คูณกันที่เป็นกำลังสอง ซึ่งสุดท้ายจะได้ผลที่เหมือนกับผลต่างกำลังสอง mod n ถ้าค่าดังกล่าวเป็นผลไม่ชัด (nontrivial) สามารถนำไปใช้แยกตัวประกอบของ N ต่อได้ นอกจากนี้ยังมีการนำไปใช้อีกมากมายที่ยังไม่ได้กล่าวถึงเช่น วิธีแยกตัวประกอบของดิกสัน เป็นต้น