วิธีการแยกตัวประกอบของออยเลอร์เป็นเทคนิคในการแยกตัวประกอบของจำนวนโดยการเขียนจำนวนนั้นให้อยู่ในรูปผลรวมของกำลังสองสองแบบที่แตกต่างกัน ตัวอย่างเช่น จำนวนนั้นสามารถเขียนได้เป็นหรือ เป็นและวิธีการของออยเลอร์จะให้การแยกตัวประกอบเป็น ${\displaystyle 1000009}$${\displaystyle 1000^{2}+3^{2}}$${\displaystyle 972^{2}+235^{2}}$${\displaystyle 1000009=293\cdot 3413}$

แนวคิดที่ว่าการแสดงจำนวนเต็มบวกคี่สองรูปแบบที่แตกต่างกันอาจนำไปสู่การแยกตัวประกอบนั้น ปรากฏว่าถูกเสนอขึ้นครั้งแรกโดยมาริน เมอร์เซนน์อย่างไรก็ตาม แนวคิดนี้ไม่ได้ถูกนำไปใช้อย่างแพร่หลายจนกระทั่งหนึ่งร้อยปีต่อมาโดยออยเลอร์ การใช้งานที่มีชื่อเสียงที่สุดของวิธีการที่ปัจจุบันใช้ชื่อของเขาเป็นชื่อเรียกก็คือ การแยกตัวประกอบของจำนวนซึ่งก่อนหน้านี้เคยคิดว่าเป็นจำนวนเฉพาะ แม้ว่ามันจะไม่ใช่จำนวนเฉพาะเทียมตามการทดสอบความเป็นจำนวนเฉพาะที่สำคัญใดๆ ก็ตาม ${\displaystyle 1000009}$

วิธีการแยกตัวประกอบของออยเลอร์มีประสิทธิภาพมากกว่าวิธีการของแฟร์มาต์สำหรับจำนวนเต็มที่มีตัวประกอบอยู่ห่างกัน และอาจมีประสิทธิภาพมากกว่าการหารแบบลองผิดลองถูกมาก หากสามารถหาการแสดงจำนวนในรูปผลรวมของกำลังสองได้ค่อนข้างง่าย วิธีการที่ใช้ในการหาการแสดงจำนวนในรูปผลรวมของกำลังสองนั้นโดยพื้นฐานแล้วเหมือนกับวิธีการหาผลต่างของกำลังสองในวิธีการแยกตัวประกอบของแฟร์มาต์

ข้อเสียเปรียบที่สำคัญของวิธีการแยกตัวประกอบของออยเลอร์คือ ไม่สามารถนำไปใช้กับการแยกตัวประกอบของจำนวนเต็มที่มีตัวประกอบเฉพาะในรูปแบบ 4k +  3 ที่มีกำลังคี่ในการแยกตัวประกอบเฉพาะได้ เนื่องจากจำนวนดังกล่าวไม่สามารถเป็นผลรวมของกำลังสองสองจำนวนได้ แม้แต่จำนวนประกอบคี่ในรูปแบบ 4k +  1 ก็มักจะเป็นผลคูณของจำนวนเฉพาะสองจำนวนในรูปแบบ 4k +  3 (เช่น 3053 = 43 × 71) และก็ไม่สามารถแยกตัวประกอบได้ด้วยวิธีของออยเลอร์เช่นกัน

ข้อจำกัดในการใช้งานนี้ทำให้วิธีการแยกตัวประกอบของออยเลอร์ไม่เป็นที่นิยมสำหรับอัลกอริ ธึม การแยกตัวประกอบ ใน คอมพิวเตอร์เนื่องจากผู้ใช้ที่พยายามแยกตัวประกอบจำนวนเต็มแบบสุ่มนั้นไม่น่าจะรู้ว่าวิธีการของออยเลอร์สามารถนำมาใช้กับจำนวนเต็มนั้นได้จริงหรือไม่ เพิ่งไม่นานมานี้เองที่มีความพยายามที่จะพัฒนาวิธีการของออยเลอร์ให้เป็นอัลกอริธึมคอมพิวเตอร์เพื่อใช้กับจำนวนเฉพาะที่ทราบว่าวิธีการของออยเลอร์สามารถนำมาใช้ได้

เอกลักษณ์บราห์มาคุปตะ-ฟิโบนาชชีกล่าวว่า ผลคูณของผลรวมของกำลังสองสองจำนวนก็คือผลรวมของกำลังสองสองจำนวนเช่นกัน วิธีของออยเลอร์อาศัยทฤษฎีบทนี้ แต่สามารถมองได้ว่าเป็นสิ่งที่ตรงกันข้าม เนื่องจากเราพบว่าผลคูณของผลรวมของกำลังสองสองจำนวนนั้นเหมือนกัน ${\displaystyle n=a^{2}+b^{2}=c^{2}+d^{2}}$${\displaystyle n}$

ขั้นแรกให้สรุปว่า

${\displaystyle a^{2}-c^{2}=d^{2}-b^{2}}$

และแยกตัวประกอบทั้งสองด้านเพื่อให้ได้

${\displaystyle (ac)(a+c)=(db)(d+b)}$(1)

ทีนี้ให้และเพื่อให้มีค่าคงที่บางค่าที่สอดคล้องกับ เงื่อนไขดังกล่าว${\displaystyle k=\operatorname {gcd} (ac,db)}$${\displaystyle h=\operatorname {gcd} (a+c,d+b)}$${\displaystyle l,m,l',m'}$

• ${\displaystyle (ac)=kl}$,
• ${\displaystyle (db)=km}$,

${\displaystyle \operatorname {gcd} (l,m)=1}$

• ${\displaystyle (a+c)=hm'}$,
• ${\displaystyle (d+b)=hl'}$,

${\displaystyle \operatorname {gcd} (l',m')=1}$

เมื่อแทนค่าเหล่านี้ลงในสมการ (1) จะได้

${\displaystyle klhm'=kmhl'}$

การตัดตัวประกอบร่วมออกจะได้ผลลัพธ์ดังนี้

${\displaystyle lm'=l'm}$

เมื่อใช้ข้อเท็จจริงที่ว่าและเป็นคู่ของจำนวนเฉพาะสัมพัทธ์ เราจะได้ว่า ${\displaystyle (l,m)}$${\displaystyle \left(l',m'\right)}$

• ${\displaystyle l=l'}$
• ${\displaystyle m=m'}$

ดังนั้น

• ${\displaystyle (ac)=kl}$
• ${\displaystyle (db)=km}$
• ${\displaystyle (a+c)=hm}$
• ${\displaystyle (d+b)=hl}$

ตอนนี้เราเห็นแล้วว่าและ${\displaystyle m=\operatorname {gcd} (a+c,db)}$${\displaystyle l=\operatorname {gcd} (ac,d+b)}$

เมื่อใช้เอกลักษณ์บราห์มาคุปตะ-ฟิโบนาชชีเราจะได้

${\displaystyle \left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=(kl+hm)^{2}+(km-hl)^{2}={\bigl (}(ac)+(a+c){\bigr )}^{2}+{\bigl (}(db)-(d+b){\bigr )}^{2}=(2a)^{2}+(2b)^{2}=4n.}$

เนื่องจากตัวประกอบแต่ละตัวเป็นผลรวมของกำลังสองสองตัว ดังนั้นตัวประกอบตัวใดตัวหนึ่งในนั้นจะต้องมีจำนวนคู่ทั้งสองตัว คือหรือโดยไม่เสียความเป็นทั่วไป สมมติว่าคู่เป็นจำนวนคู่ การแยกตัวประกอบจึงกลายเป็น ${\displaystyle (k,h)}$${\displaystyle (l,m)}$${\displaystyle (k,h)}$

${\displaystyle n=\left(\left({\tfrac {k}{2}}\right)^{2}+\left({\tfrac {h}{2}}\right)^{2}\right)\left(l^{2}+m^{2}\right).\,}$

เนื่องจาก:${\displaystyle \ 1000009=1000^{2}+3^{2}=972^{2}+235^{2}}$

จากสูตรข้างต้น เราจะได้ว่า:

ดังนั้น,

${\displaystyle 1000009=\left[\left({\frac {4}{2}}\right)^{2}+\left({\frac {34}{2}}\right)^{2}\right]\cdot \left[\left({\frac {14}{2}}\right)^{2}+\left({\frac {116}{2}}\right)^{2}\right]\,}$

${\displaystyle =\left(2^{2}+17^{2}\right)\cdot \left(7^{2}+58^{2}\right)\,}$

${\displaystyle =(4+289)\cdot (49+3364)\,}$

${\displaystyle =293\cdot 3413\,}$

ฟังก์ชัน Euler_factorize(int n) -> รายการ[int] ถ้า n เป็นจำนวนเฉพาะแล้ว print("ตัวเลขนี้ไม่สามารถแยกตัวประกอบได้") ฟังก์ชันออก ลูป for จาก a=1 ถึง a=ceiling(sqrt(n)) b2 = n - a*a b = floor(sqrt(b2)) ถ้า b*b==b2 หยุดลูปโดยรักษาค่า a,b ไว้ ถ้า a*a+b*b!=n แล้ว print("ไม่พบนิพจน์ใด ๆ สำหรับ n ในรูปผลรวมของกำลังสอง") ฟังก์ชันออก ลูป for จาก c=a+1 ถึง c=ceiling(sqrt(n)) d2 = n - c*c d = floor(sqrt(d2)) ถ้า d*d==d2 แล้ว ทำลายลูปที่รักษา c,d ไว้ ถ้า c*c+d*d!=n แล้ว print("ไม่พบนิพจน์ที่สองสำหรับ n ในรูปผลรวมของกำลังสอง") ฟังก์ชันออก A = ca, B = c+a C = bd, D = b+d k = GCD(A,C)//2, h = GCD(B,D)//2 l = GCD(A,D)//2, m = GCD(B,C)//2 แฟกเตอร์1 = k*k + h*h factor2 = l*l + m*m ส่งคืนลิสต์[แฟกเตอร์1, แฟกเตอร์2]