從平方和談起
在歷史上，人們注意到，形如 4k+1 的自然數 N 若只有一個方法表示成兩互素 (Coprime) 之數的平方和，則 N 是一素數或素數的平方；如果 N 不能表示成平方和，則 N 是合數且含有偶數個形如 4n-1 的素因子，但不能肯定其中有否形如 4n+1 的素因子。
如果 N 可以有兩種或以上的方法表示成兩互素之數的平方和，則我們可以利用下法去分解數 N：
N = a2+b2 = c2+d2
即 N = (ad+bc)(ad-bc)/(a+c)(a-c) 或 N = (ad+bc)(ad-bc)/(d+b)(d-b)
原因很簡單：
N = a2+b2 則 d2N = a2d2+b2d2 ，以及
N = c2+d2 則 b2N = b2c2+b2d2 ，
兩式相加 (b2-d2)N = (a2d2-b2c2) ，把式兩邊除以 (b2-d2) 再分解便得上式。這便是我們所謂的歐拉分解法 (Euler's Factorization Method)。
讓我們看看一實際例子吧：分解 16000001。
設 N = 16000001，則 N = 40002+12 = 10492+38602，所以
N = (4000*1049+3860*1)(4000*1049-3860*1)/[(1049+1)(1049-1)] = 229*69869，其中 229 是素數。
而 69869 = 2622+152 = 2682+1152，則我們利用上述方法可得：69896 = 109*641，而這兩數皆為素數。
所以 16000001 = 109*229*641
我們不難知道這三個 16000001 的素因子皆是形如 4k+1 的。
後來有人把上法改進，推廣至 x2+ky2 的形式。如果某數可分柝為一個數的平方和另一數的平方的 k 倍之和，且有兩種或以上的分柝方法，則我們可把它分解：
事實上，如果 N = a2+kb2 = c2+kd2，則
即 N = (ad+bc)(ad-bc)/(a+c)(a-c) 或 N = (ad+bc)(ad-bc)/(d+b)(d-b)，証法和上式相類似，恕不加冗述。
例：分解 36661。此數肯定已不含較小的素因子如 2、3 、5 、7 、 11 、 13等。
設 N = 36661 = 1692+4*452 = 1192+4*752
應用上式，N = (167*75+45*119)(167*75+45*119)/[(169+119)(169-119)] = 61*601
此兩數皆是素數。因此分解便告完成。
在二次形式 x2+ky2 中，令 k 取一些特定數值，如 k=4或 2、-2時，我們來看看分解出來的產物是屬於什麼形式？顯然在 x2+4y2 將導致 8n+1 或 8n+5 的形式，而 x2+2y2 導致 8n+1 或 8n+3 的形式來，而 x2-2y2 則會導致 8n+1 或 8n+7 的形式出來。
另外我們把 n=45677 拿來看看如何減少測試的數：由於這是屬於 8n+5 的形式，故取 k = 4，即二次形 x2+4y2 。
由此令 y =[(45677-x2)/4]1/2 ，從而計出 y < 107。
再加上一些二次剩餘 (Quadratic Residue) 的知識，我們便可把搜索範圍縮小至 7、17、23、27、53、67 和 77 七數，一一試之。
得 45677 = 2112+4*172 的表達式，但只有一條，故 45677 是素數。
參考文獻及網址：
Weisstein, E. W. "Euler's Factorization Method." From MathWorld. http://mathworld.wolfram.com/EulersFactorizationMethod.html.
