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

วิธีแยกตัวประกอบของแฟร์มาต์ (อังกฤษ: Fermat's factorization method) ตั้งชื่อตามผู้คิดค้นคือ ปิแยร์ เดอ แฟร์มาต์ (Pierre de Fermat) โดยเป็นผลงานหนึ่งที่เกี่ยวกับทฤษฎีจำนวน ที่ใช้ในการแยกตัวประกอบโดยมีหลักการที่ว่า จำนวนเต็มคี่ใดๆ สามารถแทนได้ด้วยผลต่างของเลขกำลังสองได้ดังนี้

${\displaystyle N=x^{2}-y^{2}\,}$

จากการสังเกตนี้ ทำให้สามารถนำไปประยุกต์ใน ตะแกรงกำลังสอง (quadratic sieve) และ วิธีแยกตัวประกอบของดิกสัน (Dixon's Factorization Method) จากสมบัติดังกล่าวสามารถมองได้ว่า

${\displaystyle N=ab=(x+y)(x-y)\ }$

โดยที่ ${\displaystyle (a>b)}$ ถ้า a หรือ b ไม่เท่ากับ 1 แสดงว่า a กับ b เป็นตัว ประกอบแท้ของ N สามารถเขียนแยกได้

${\displaystyle a=x+y\ }$

${\displaystyle b=x-y\ }$

หรือ

${\displaystyle a+b=2x\ }$

${\displaystyle a-b=2y\ }$

ดังนั้น

${\displaystyle N=ab=x^{2}-y^{2}=1/4((a+b)^{2}-(a-b)^{2}))=((a+b)/2)^{2}-((a-b)/2)^{2}\ }$

เนื่องจาก N เป็นจำนวนเต็มคี่ แล้ว a และ b เป็นจำนวนคี่ด้วย ดังนั้นจะได้ทั้งสองส่วนของสมการเป็นจำนวนเต็มและยังเขียนได้ว่า

${\displaystyle x^{2}\equiv y^{2}(modN).\ }$

จากสมบัติเหล่านี้จะนำมาใช้แยกตัวประกอบจำนวนเต็ม เมื่อเทียบกับ การหารเชิงทดลอง (trial division) แล้ววิธีนี้อาจจะมีประสิทธิภาพน้อยกว่า แต่เมื่อนำทั้ง วิธีการแยกตัวประกอบของแฟร์มาต์ กับการหารเชิงทดลอง มารวมกันแล้วจะทำให้ได้ประสิทธิภาพที่มากกว่าการใช้วิธีใดวิธีหนึ่ง

วิธีการเบื้องต้น

จากทฤษฎีข้างต้นหาค่า a ที่ทำให้ ${\displaystyle b2=a^{2}-N}$  สามารถยกกำลังสองเป็นจำนวนเต็มได้วิธีการดังกล่าวสามารถเขียนรหัสเทียมได้ดังนี้

รหัส

FermatFactor(N): // N ควรจะเป็นจำนวนคี่ a ← ceil(sqrt(N)) b2 ← a*a - N while b2 isn't a square: a ← a + 1 // สมมูลกับ b2 ← b2 + 2*a + 1 b2 ← a*a - N //  a ← a + 1 endwhile return a - sqrt(b2) // หรือ a + sqrt(b2) 

ตัวอย่างรหัสที่สร้างโดยภาษา C++

int FermatFactor(int N){ int a=ceil(sqrt(N)); int b2=a*a-N; while(sqrt(b2)-(int)sqrt(b2)>0){ //วิธีการตรวจสอบรากที่สองว่าเป็นจำนวนเต็มหรือไม่ อาจจะยังไม่ดีเท่าไหร่แต่ก็พอใช้ได้ a++; b2=a*a-N; } return a-sqrt(b2); } 

หลักการเบื้องต้น

หลักการคือต้องการแยกตัวประกอบของ N ซึ่ง N ควรเป็นจำนวนคี่ถ้าหากเป็นจำนวนคู่สามารถแยกตัวประกอบ 2 ออกไปก่อน จากนั้นหาตัวประกอบโดยหาค่า a และ b ที่เป็นจำนวนเต็มน้อยที่สุดที่ ${\displaystyle a-b\leq {\sqrt {N}}\leq a+b}$  โดยที่ ${\displaystyle a-b=N/(a+b)\ }$  และถ้าแยกตัวประกอบได้ N=N*1 จะได้ว่า N เป็นจำนวนเฉพาะ โดยทดสอบทีละเงื่อนไขและบวกค่า a เพิ่มขึ้นเลื่อยๆจนพบคำตอบที่ได้ตัวประกอบลู่เข้ารากของ N มากที่สุด ตัวอย่างเช่น N=5959

a:	78	79	80
b2:	125	282	441

ขั้นตอนตัวอย่าง

1. เริ่มต้นโดยหา ${\displaystyle a=\lceil {\sqrt {5959}}\rceil =78}$  จะได้ b2 = 125

2. ตรวจสอบ b2 ว่าสามารถหารากได้เป็นจำนวนเต็มหรือไม่ เนื่องจาก b2 = 125 หารากได้ประมาณ 11.18 ไม่ใช่จำนวนเต็มจึงเพิ่มค่า a เป็น 79 แล้วหาต่อได้ ${\displaystyle b2=79^{2}-5959=282}$  แล้วทำซ้ำขั้นตอนที่ 2 อีกรอบจนกว่าจะสามารถหารากได้เป็นจำนวนเต็มให้ไปทำขั้นตอนที่ 3

3. เมื่อทำมา 3 ครั้งจะได้ a=80 และ b2 = 441 ซึ่งสามารถหารากได้ 21 ดังนั้นจะได้ว่า ${\displaystyle a-b=59}$ , and ${\displaystyle a+b=101}$ . ซึ่ง ได้ 59 และ 101 เป็นตัวประกอบของ 5959

ประสิทธิภาพ

เมื่อให้ ${\displaystyle N=cd}$  จะได้ว่าจำนวนครั้งในการวนลูปคือ ${\displaystyle (c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c}$  ของกรณีที่แย่ที่สุดคือเมื่อ N เป็นจำนวนเฉพาะ ซึ่งจะได้ประสิทธิภาพการทำงานเป็น ${\displaystyle O(N)}$  แต่ถ้ากรณีที่ c ต่างกับ รากของ N น้อยกว่า ${\displaystyle {\left(4N\right)}^{1/4}}$  ถ้าใช้จำนวนการทำงานแค่ครั้งเดียว หรือถ้าคำตอบจริงยิ่งเข้าไป รากของ N มากเท่าไหร่ประสิทธิภาพในทางปฏิบัติก็จะดีขึ้น ซึ่งจากทั้งหมดแสดงให้เห็นว่าประสิทธิภาพของวิธีแยกตัวประกอบของแฟร์มาต์จะขึ้นอยู่กับค่าของ N

การประยุกต์วิธีของแฟร์มาต์กับการหารเชิงทดลอง

จากวิธีของแฟร์มาต์จะเห็นว่าได้ประสิทธิภาพคือ ${\displaystyle O(N)}$  เมื่อเทียบกับ วิธีการหารเชิงทดลองที่ได้ประสิทธิภาพที่ดีกว่าคือ O(√n / log n) ซึ่งจะเห็น ดังนั้นเราสามารถเพิ่มประสิทธิภาพให้กับ วิธีการหาตัวประกอบทั้งสองให้ดีขึ้นได้โดยนำทั้งสองวิธีมารวมกันโดยใช้วิธีการหาตัวประกอบของแฟร์มาต์เป็นหลัก และใช้วิธีการหารเชิงทดลองตัดกรณีที่ใช้พิจารณามากๆได้ จาก ทฤษฏีการหารเชิงทดลอง ตัวประกอบที่เป็นจำนวนเฉพาะของจำนวนเต็มใดๆ จะมีค่าน้อยกว่าหรือเท่ากับรากที่สองของจำนวนเต็มนั้น จากตัวอย่างให้ N=123456789123 ใช้วิธีการแยกตัวประกอบของแฟร์มาต์ ได้ดังนี้

${\displaystyle \lceil {\sqrt {N}}\rceil =351365}$ 

${\displaystyle 351365^{2}-N=574102;{\sqrt {574102}}=757.7}$ 

${\displaystyle 351366^{2}-N=1276833;{\sqrt {1276833}}=1129.97}$ 

${\displaystyle 351367^{2}-N=1979566;{\sqrt {1979566}}=1406.97}$ 

${\displaystyle 351368^{2}-N=2682301;{\sqrt {2682301}}=1637.77}$ 

จริงๆแล้วจะเห็นว่าเราทำมาได้ 4 ขั้นตอนแล้วแต่ยังไม่ได้ตัวประกอบเพราะว่า b2=1637.77 ไม่ใช่จำนวนเต็มแต่เมื่อเราคำนวณ a-b2 จะได้ว่า 357368-1638=349730 ถ้าอาศัยทฤษฎีของการหารเชิงทดลองจะได้ว่าการที่จะหาตัวประกอบเฉพาะของ N ทำได้จากการทดลองหาจาก 0 ถึง 351365 (จาก การหารเชิงทดลอง) แต่กรณีนี้หลังจากที่เราทำการแยกตัวประกอบของแฟร์มาต์ยังไม่เสร็จแต่เราจะได้ว่า เราทำหาการหารเชิงทดลองโดยหาแค่จาก 0 ถึง 349730 พอซึ่งสามารถลดจากเดิมได้เป็นพันรอบโดยแค่ทำการหาตัวประกอบแบบแฟร์มาต์แค่ 4 รอบก่อน ซึ่งจากตัวอย่างด้านบนจะเห็นว่าสามารถหาค่าแล้วได้ b2 ออกมาเลื่อยๆทำให้ยิ่งเข้าใกล้ค่าตัวประกอบจริงมากขึ้นและยิ่งทำให้เมื่อนำไปหาการหารเชิงทดลองต่อมีแนวโน้มที่จะได้ประสิทธิภาพที่ดีขึ้น

ดังนั้นจึงสามารถเขียนในรูปของความสัมพันธ์ทั่วไป ถ้าเราให้ ${\displaystyle d>{\sqrt {N}}}$  จะได้ว่าถ้าเราใช้ การแยกตัวประกอบของแฟร์มาต์ในช่วงระหว่าง ${\displaystyle {\sqrt {N}}}$  กับ ${\displaystyle d\ }$  จะทำให้ได้ขอบเขตของการหาในวิธีการหารเชิงทดลองคือ ${\displaystyle d-{\sqrt {d^{2}-N}}}$  ตัวอย่างเช่นถ้า N=2345678917 โดยให้ d=48436 จะได้ขอบเขตของการหารเชิงทดลองคือ 47830 และถ้ากำหนดให้ d=55000 จะได้ขอบเขตคือ 28937

การปรับปรุงกับตะแกรง

บ้างครั้งเราไม่มีความจำเป็นที่จะต้องหา รากที่สองของ ${\displaystyle a^{2}-N}$  หรือแม้แต่ค่าของ a ทุกค่าเราสามารถพิจารณาได้จากค่า มอดุโล ของมันเช่นจากตัวอย่าง

a:	48433	48434	48435	48436
b2:	76572	173439	270308	367179
b:	276.7	416.5	519.9	605.9

กรณีดังกล่าวจะเห็นได้ว่าไม่มีค่า b หรือรากที่สองของ b2 เป็นจำนวนเต็ม. จากสมการ ${\displaystyle a^{2}-N}$  เมื่อพิจารณาค่า ${\displaystyle a^{2}}$ เมื่อ a เป็นจำนวนเต็ม จากตัวอย่างดังนี้

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
${\displaystyle n^{2}}$	1	4	9	16	25	36	49	64	81	100	121	144	169	196	225	256	289	324	361	400

จะเห็นได้ว่ากำลังสองของเลขจำนวนเต็มมักจะลงท้ายด้วย 0,1,4,5,9,16 modulo 20. จากตารางด้านบนจะพบว่าค่าที่ a mod 10 มีค่าเดียวกันยกจำลังสองแล้วจะได้เลขลงท้ายค่าเดียวกันเท่ากันด้วย หรือจะเรียกได้ว่าจะซ้ำรอบเดิมเมื่อ a ถูกเพิ่มเป็น 10 จากตัวอย่างดังกล่าวจะได้ว่าถ้าเราเพิ่ม -17 mod 20 (3), ${\displaystyle a^{2}-N}$  จะได้เลขลงท้ายดังกล่าวออกมาเป็น 3,4,7,8,12,19 modulo 20 จะเห็นว่ามี 4 จากรายการนี้ที่สามารถเป็นกำลังสองได้ (เทียบอันดับกันของ ${\displaystyle a^{2}}$  และ ${\displaystyle a^{2}-N}$ ) ดังนั้น ${\displaystyle a^{2}}$  ต้องเป็น 1 mod 20 หรือหมายถึง a คือ 1,9 mod 10 ซึ่งจะทำให้ b2 ลง ท้ายด้วย 4 mod 20 และ ถ้าเป็นกำลังสองอีก b จะลงท้ายด้วย 2,8 mod 10

ตัวอย่างของการใช้ มอดุลัส ค่าต่าง ของ N=2345678917

มอดุโล 16:	กำลังสองคือ	0, 1, 4, or 9
	N mod 16 is	5
	ดังนั้น ${\displaystyle a^{2}}$  สามารถเป็นได้คือ	9
	และ ${\displaystyle a}$  ต้องเป็น	3 , 5 modulo 16
มอดุโล 9:	กำลังสองคือ	0, 1, 4, or 7
	N mod 9 is	7
	ดังนั้น ${\displaystyle a^{2}}$ สามารถเป็นได้คือ	7
	และ ${\displaystyle a}$  ต้องเป็น	4 , 5 modulo 9

โดยทั่วไปจะเลือกค่าที่เป็นกำลังของจำนวนเฉพาะที่แตกต่างกันสำหรับ มอดุลัส เมื่อให้ลำดับของ a-value(start,end,and step) และค่าค่า modulus ซึ่งจะมีกระบวนการได้ดังนี้

รหัสเทียม

FermatSieve(N, astart, aend, astep, modulus) a ← astart do modulus times: b2 ← a*a - N if b2 is a square, modulo modulus: FermatSieve(N, a, aend, astep * modulus, NextModulus) endif a ← a + astep enddo 

การปรับปรุงตัวคูณ กับวิธีการของเลห์แมน

วิธีการของแฟร์มาต์จะทำงานได้ดีเมื่อตัวประกอบนั้นอยู่ใกล้กับค่า รากที่สองของ 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)

วิธีการดูเหมือนกับการแยกตัวประกอบของแฟร์มาต์ โดยให้ ${\displaystyle k\geq 1}$  และ ${\displaystyle x=\lceil 2{\sqrt {kN}}\rceil }$  ตรวจสอบว่า ${\displaystyle (x+m)^{2}-4kN\ }$ คือกำลังสองสำหรับ ${\displaystyle m\geq 0}$  จากนั้นเราแค่จำเป็นต้องตรวจสอบ ${\displaystyle k\leq N^{1/3}}$  และ m สำหรับแต่ละ ${\displaystyle m^{2}k\leq N^{1/3}}$  เพื่อหาตัวประกอบที่ ${\displaystyle >N^{1/3}\ }$  จะเห็นว่าวิธีนี้ใช้เวลาเป็น ${\displaystyle O(N^{1/3})\ }$  เราสามารถพิสูจน์ขั้นตอนเหล่านี้ได้โดยใช้วิธีการทั่วไปของ การประมาณปกติ(normal approximation)

รหัสเทียม

 Check that N has no divisors <= N^(1/3). //ตรวจสอบว่าไม่มีตัวหารตามเงื่อนไข For 1 <= t <= N^(1/3): Let k = ceil (sqrt (4tN)) For 0 <= m <= sqrt (N^(1/3) / t) Check whether (k+m)^2 - 4tN is a square. //ตรวจสอบว่าเป็นกำลังสอง If it is a square -> calculate two factors. //ถ้าเป็นให้คำนวณตัวประกอบ 2 ตัว 

ประสิทธิภาพของรหัสเทียมดังกล่าวคือ ${\displaystyle O(N^{1/3})\ }$ 

สรุปและการประยุกต์อื่นๆ

การแยกตัวประกอบของแฟร์มาต์เป็นวิธีหนึ่งที่ใช้ในการแยกตัวประกอบของจำนวนเต็มโดยใช้สมบัติของผลต่างกำลังสองที่เป็นจำนวนเต็มวิธีพื้นฐานปกติจะมีประสิทธิภาพที่ไม่ดีนักไม่ต่างกับการค้นหาจำนวนเต็มทุกตัวจาก 1 ถึง N ( ${\displaystyle O(n)\ }$  ) แต่จะมีประสิทธิภาพสูงถ้าคำตอบเข้าใกล้รากที่สองของ N และสามารถนำคุณสมบัติทางคณิตศาสตร์นี้ไปประยุกต์หรือปรับปรุงกับวิธีอื่นเช่น การหารเชิงทดลอง ทำให้เห็นว่าได้ประสิทธิภาพที่ดีกว่าการใช้ตัวใดตัวหนึ่งโดยอาศัยการแยกตัวประกอบของแฟร์มาต์มาใช้ลดช่วงของการค้น หรือประยุกต์กับวิธีของเลห์แมน ดังที่ได้กล่าวไปที่ทำให้ได้ประสิทธิภาพเป็น ${\displaystyle O(N^{1/3})\ }$  โดยอาศัยสมบัติการความมีประสิทธิภาพสูงเมื่อเข้าใกล้รากที่สองของ N นอกจากนั้นยังเป็นรากฐานของเรื่อง ตะแกรงกำลังสอง(quadratic sieve) และ การกรองตัวเลขในขอบเขตแบบธรรมดา(general number field sieve)ซึ่งเป็นระเบียบวิธีการที่รู้จักดีสำหรับการแยกตัวประกอบ "กรณีที่แย่ที่สุด" จำนวนกึ่งเฉพาะขนาดใหญ่ ในขั้นตอน วิธีการของตะแกรงกำลังสอง ที่แตกต่างกับการแยกตัวประกอบของแฟร์มาต์คือ แทนที่จะหา ว่า${\displaystyle a^{2}-n}$  เป็นกำลังสองหรือไม่เป็นลำดับ แต่จะหาเซตย่อยของส่วนประกอบของลำดับดังกล่าวที่คูณกัน ที่เป็นกำลังสอง ซึ่งสุดท้ายจะได้ผลที่เหมือนกับผลต่างกำลังสอง mod n ถ้าค่าดังกล่าวเป็นผลไม่ชัด(nontrivial) สามารถนำไปใช้แยกตัวประกอบของ N ต่อได้ นอกจากนี้ยังมีการนำไปใช้อีกมากมายที่ยังไม่ได้กล่าวถึงเช่น วิธีแยกตัวประกอบของดิกสัน เป็นต้น

อ้างอิง

• Fermat's Factorization Method in MathWorld von Wolfram Research.
• J. McKee, "Speeding Fermat's factoring method", Mathematics of Computation, 68:1729-1737 (1999).
• Generalized Trial Division Murat S¸AHÿIN Int. J. Contemp. Math. Sciences, Vol. 6, 2011, no. 2, 59 - 64
• R. Lehman, "Factoring Large Integers", Mathematics of Computation

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

• Java Implementation Of Fermat's method and trial division