Euler's factorization method

오일러(Euler)의 인수분해 방법은 숫자를 두 가지 다른 방법으로 두 제곱의 합으로 씀으로써 그것을 인수화(factoring)하는 기법입니다. 예를 들어, 숫자 $1000009$ 는 $1000^{2}+3^{2}$ 으로 또는 $972^{2}+235^{2}$ 으로 쓸 수 있고 오일러의 방법은 인수분해 $1000009=293\cdot 3413$ 를 제공합니다.

홀수 양의 정수의 두 가지 별개의 표현이 인수분해로 이어질 수 있다는 아이디어는 마랭 메르센(Marin Mersenne)에 의해 처음 제안된 것으로 보입니다. 어쨌든, 그것은 오일러에 의해 100년 후까지 광범위하게 사용되지 않았습니다. 현재 그의 이름을 지니는 그 방법의 그의 가장 유명한 사용은 숫자 $1000009$ 를 인수분해하는 것이었으며, 심지어 그것이 임의의 주요 소수성 테스트에서 유사소수(pseudoprime)가 아닐지라도, 이전에는 소수라고 생각했던 것 같습니다.

오일러의 인수분해 방법은 그것의 인수가 함께 가깝지 않은 정수에 대해 페르마의 방법보다 더 효과적이고 만약 우리가 두 제곱의 합으로 숫자 표현을 합리적으로 쉽게 찾을 수 있으면 시도 나눗셈보다 잠재적으로 훨씬 더 효율적입니다. 오일러의 개발은 궁극적으로 훨씬 더 효율적인 숫자의 인수화를 가능하게 했고, 1910년대까지, 약 천만에 이르는 큰 인수 테이블의 개발을 가능하게 했습니다.^{[citation needed]} 두 제곱의 합으로 숫자 표현을 찾기 위해 사용되는 방법은 페르마의 인수분해 방법(Fermat's factorization method)에서 제곱의 차이를 찾는 것과 본질적으로 같습니다.

오일러 인수분해 방법의 가장 큰 단점은 형식 4k + 3의 임의의 소수 인수가 그것의 소수 인수분해에서 홀수 거듭제곱으로 발생하는 정수를 인수화하는 것에 적용될 수 없다는 것인데, 왜냐하면 그러한 숫자는 결코 두 제곱의 합이 될 수 없기 때문입니다. 심지어 형식 4k + 1의 홀수 합성수(composite number)도 종종 형식 4k + 3의 두 소수의 곱 (예를 들어, 3053 = 43 × 71)이고 다시-한번 결코 오일러의 방법에 의해 인수화될 수 없습니다.

이러한 제한된 적용-가능성은 컴퓨터(computer) 인수화 알고리듬(algorithm)에 대해 오일러의 인수분해 방법을 선호되지 않게 만들어 왔는데, 왜냐하면 어떤 정수를 인수분해하랴고 시도하는 임의의 사용자는 오일러의 방법이 질문에서 그 정수에 실제로 적용될 수 있는지 여부를 알 가능성이 거의 없기 때문입니다. 오일러의 방법이 적용될 수 있는 것으로 알려진 특수한 숫자의 사용에 대해 오일러의 방법을 컴퓨터 알고리듬으로 개발하려는 시도는 오직 비교적 최근에 이루어졌습니다.

Theoretical basis

브라마굽터–피보나치 항등식(Brahmagupta–Fibonacci identity)은 두 제곱의 두 합의 곱이 두 제곱의 합이라는 것을 말합니다. 오일러의 방법은 이 정리에 의존하지만, 그것이 전환, $n=a^{2}+b^{2}=c^{2}+d^{2}$ 가 주어지면, 우리가 $n$ 을 두 제곱의 합의 곱으로 찾는 것으로 보일 수 있습니다.

먼저 다음임을 추론합니다:

a^{2}-c^{2}=d^{2}-b^{2}

그리고 양쪽 변을 인수화해서 다음을 얻습니다:

(a-c)(a+c)=(d-b)(d+b)

(1)

이제 다음을 만족시키는 어떤 상수 $l,m,l',m'$ 이 존재하도록 $k=\operatorname {gcd} (a-c,d-b)$ 과 $h=\operatorname {gcd} (a+c,d+b)$ 이라고 놓습니다:

$(a-c)=kl$ ,
$(d-b)=km$ ,

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

$(a+c)=hm'$ ,
$(d+b)=hl'$ ,

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

이것들을 방정식 (1)으로 대체하면 다음을 제공합니다:

klhm'=kmhl'

공통 인수를 제거하면 다음을 산출합니다:

lm'=l'm

이제 $(l,m)$ 와 $\left(l',m'\right)$ 가 상대적으로 소수의 쌍이라는 사실을 사용하여, 우리는 다음임을 찾습니다:

$l=l'$
$m=m'$

따라서

$(a-c)=kl$
$(d-b)=km$
$(a+c)=hm$
$(d+b)=hl$

우리는 이제 $m=\operatorname {gcd} (a+c,d-b)$ 과 $l=\operatorname {gcd} (a-c,d+b)$ 임을 압니다.

브라마굽터–피보나치 항등식(Brahmagupta–Fibonacci identity)을 적용하면, 우리는 다음을 얻습니다:

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

각 인수가 두 제곱의 합이므로, 이들 중 하나는 둘 다 짝수: $(k,h)$ 또는 $(l,m)$ 를 포함해야 합니다. 일반성의 손실 없이, 쌍 $(k,h)$ 가 짝수임을 가정합니다. 인수분해는 그런-다음 다음이 됩니다:

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

Worked example

다음이므로: $\ 1000009=1000^{2}+3^{2}=972^{2}+235^{2}$

우리는 위의 공식으로부터 다음을 가집니다:

a = 1000	(A) a − c = 28	k = gcd[A,C] = 4
b = 3	(B) a + c = 1972	h = gcd[B,D] = 34
c = 972	(C) d − b = 232	l = gcd[A,D] = 14
d = 235	(D) d + b = 238	m = gcd[B,C] = 116

따라서,

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]\,

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

=(4+289)\cdot (49+3364)\,

=293\cdot 3413\,

References

Ore, Oystein (1988). "Euler's Factorization Method". Number Theory and Its History. pp. 59–64. ISBN 978-0-486-65620-5.
McKee, James (1996). "Turning Euler's Factoring Method into a Factoring Algorithm". Bulletin of the London Mathematical Society. 4 (28): 351–355. doi:10.1112/blms/28.4.351.