Fermat's factorization method

페르마(Fermat)의 인수분해(factorization) 방법은, 피에르 드 페르마(Pierre de Fermat)의 이름을 따서 지어졌으며, 홀수(odd) 정수(integer)를 두 제곱의 차이(difference of two squares)로 표현하는 것을 기초로 합니다:

N=a^{2}-b^{2}.

해당 차이는 대수(algebra)적으로 $(a+b)(a-b)$ 로 인수화-가능입니다; 만약 인수가 일과 같지 않으면, 그것은 N의 적절한 인수분해입니다.

각 홀수는 그러한 표현을 가집니다. 사실, 만약 $N=cd$ 가 N의 인수분해이면, 다음입니다:

N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{2}

N이 홀수이므로, c와 d는 역시 홀수이므로, 그것들의 절반은 정수입니다. (넷의 배수는 역시 제곱의 차이입니다: c와 d를 짝수로 놓습니다.)

그것의 가장-간단한 형식에서, 페르마의 방법은 시도 나눗셈 (최악의 경우)보다 더 느릴 수 있습니다. 그럼에도 불구하고, 시도 나눗셈과 페르마의 것의 조합이 어느 쪽보다 더 효율적입니다.

Basic method

우리는 $a^{2}-N=b^{2}$ , 제곱을 기대하면서 a의 다양한 값을 시도합니다.

FermatFactor(N): // N은 홀수여야 합니다
    a ← ceiling(sqrt(N))
    b2 ← a*a - N
    repeat until b2 is a square:
        a ← a + 1
        b2 ← a*a - N 
     // equivalently: 
     // b2 ← b2 + 2*a + 1 
     // a ← a + 1
    return a - sqrt(b2) // 또는 a + sqrt(b2)

예를 들어, $N=5959$ 를 인수분해하기 위해, a에 대해 첫 번째 시도는 다음 정수인 $78$ 로 반올림된 $5959$ 의 제곱근입니다. 그런-다음, $b^{2}=78^{2}-5959=125$ 입니다. 125는 제곱이 아니므로, 두 번째 시도는 a의 값을 1씩 증가시킴으로써 만들어집니다. 두 번째 시도도 역시 실패하는데, 왜냐하면 282는 다시 제곱이 아니기 때문입니다.

시도:	1	2	3
a	78	79	80
b²	125	282	441
b	11.18	16.79	21

세 번째 시도는 441의 완전 제곱을 생산하니다. 따라서, $a=80$ , $b=21$ 이고, $5959$ 의 인수는 $a-b=59$ 와 $a+b=101$ 입니다.

N이 두 소수 인수보다 많은 것을 가진다고 가정합니다. 해당 절차는 먼저 a와 b의 가장 작은 값을 갖는 인수분해를 찾습니다. 즉, $a+b$ 는 가장-작은 인수 ≥ N의 제곱-근이고, 따라서 $a-b=N/(a+b)$ 는 가장-큰 인수 ≤ 근-N입니다. 만약 절차가 $N=1\cdot N$ 가 찾으면, 그것은 N이 소수임을 보여줍니다.

$N=cd$ 에 대해, c를 가장-큰 부분-근 인수로 놓습니다. $a=(c+d)/2$ 이고, 따라서 단계의 숫자는 대략적으로 $(c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c$ 입니다.

만약 N이 ( $d=1$ 이도록) 소수이면, 우리는 $O(N)$ 단계가 필요합니다. 이것은 소수성을 입증하기 위해 나쁜 방법입니다. 그러나 만약 N이 그것의 제곱근에 가까운 인수를 가지면, 그 방법은 빠르게 작동합니다. 보다 정확하게, 만약 c가 ${\sqrt {N}}$ 로부터 ${\left(4N\right)}^{1/4}$ 보다 작게 다르면, 그 방법은 오직 하나의 단계를 요구합니다; 이것은 N의 크기에 독립적입니다.^{[citation needed]}

Fermat's and trial division

소수 N = 2345678917을 인수분해하려고 시도하고, 지속적으로 역시 b와 a − b를 계산하려고 시도한다고 생각해 보십시오. ${\sqrt {N}}$ 에서 올라가면서, 우리는 테이블을 만들 수 있습니다:

a	48,433	48,434	48,435	48,436
b²	76,572	173,439	270,308	367,179
b	276.7	416.5	519.9	605.9
a − b	48,156.3	48,017.5	47,915.1	47,830.1

실제에서, 우리는 b가 정수가 될 때까지 해당 마지막 행에 신경쓰지 않을 것입니다. 그러나, N이 $a-b=47830.1$ 위의 부분근 인수를 가졌으면 페르마의 방법은 이미 그것을 찾았을 것임을 관찰하십시오.

시도 나눗셈은 통상적으로 48,432까지 시도합니다; 그러나 오직 넷의 페르마 단계 후에, 우리는 인수를 찾거나 소수성을 입증하기 위해, 오직 47830까지 나눌 필요가 있습니다.

이것 모두는 조합된 인수화 방법을 제안합니다. 어떤 경계 $c>{\sqrt {N}}$ 를 선택하십시오; ${\sqrt {N}}$ 와 $c$ 사이의 인수에 대해 페르마의 방법을 사용하십시오. 이것은 $c-{\sqrt {c^{2}-N}}$ 인 시도 나눗셈에 대해 하나의 경계를 제공합니다. 위의 예제에서, $c=48436$ 와 함께 시도 나눗셈에 대해 경계가 47830입니다. 합리적인 선택은 28937의 경계를 제공하는 $c=55000$ 일 것입니다.

이와 관련하여, 페르마의 방법은 감소하는 반환을 제공합니다. 우리는 이 시점 전에 반드시 멈출 것입니다:

a	60,001	60,002
b²	1,254,441,084	1,254,561,087
b	35,418.1	35,419.8
a − b	24,582.9	24,582.2

Sieve improvement

$N=2345678917$ 에 대해 테이블을 고려할 때, 우리는 빠르게 $b^{2}$ 의 어떤 값도 제곱이 아님을 말할 수 있습니다:

a	48,433	48,434	48,435	48,436
b²	76,572	173,439	270,308	367,179
b	276.7	416.5	519.9	605.9

$a^{2}-N$ 의 모든 제곱근을 계산할 필요가 없고, 심지어 $a$ 에 대한 모든 값을 검사할 필요도 없습니다. 제곱은 항상 0, 1, 4, 5, 9, 16 모듈로(modulo) 20에 일치합니다. 값은 $a$ 가 10씩 증가할 때마다 반복합니다. 이 예제에서, N은 17 모드 20이므로, 17 모드 20을 빼는 것은 (또는 3을 더하는 것은), $a^{2}-N$ 이 이들 값에 대해 3, 4, 7, 8, 12, 및 19 모듈로 20을 생성합니다. 이 목록에서 오직 4개가 제곱이 될 수 있음이 분명합니다. 따라서, $a^{2}$ 는 1 모드 20이어야 하며, 이것은 $a$ 가 1, 9, 11 또는 19 모드 20임을 의미합니다; 4 모드 20으로 끝나는 $b^{2}$ 를 생성할 것이고, 만약 제곱이면, $b$ 는 2 또는 8 모드 10으로 끝날 것입니다.

이것은 임의의 모듈러스로 수행될 수 있습니다. 같은 $N=2345678917$ 을 사용하여,

모듈로 16:	제곱은 다음입니다	0, 1, 4, or 9
	N 모드 16은 다음입니다	5
	따라서 $a^{2}$ 은 오직 다음일 수 있습니다	9
	그리고 $a$ 는 다음이어야 합니다	3 또는 5 또는 11 또는 13 모듈로 16
모듈로 9:	제곱은 다음입니다	0, 1, 4, or 7
	N 모드 9는 다음입니다	7
	따라서 $a^{2}$ 은 오직 다음일 수 있습니다	7
	그리고 $a$ 는 다음이어야 합니다	4 또는 5 모듈로 9

우리는 일반적으로 각 모듈러스에 대해 다른 소수의 거듭제곱을 선택합니다.

a-제곱 (start, end, and step)의 수열과 모듈러스가 주어지면, 우리는 따라서 다음을 진행할 수 있습니다:

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

그러나 재귀(recursion)는 a-값이 거의 남아있지 않을 때 중지됩니다; 즉, (aend-astart)/astep가 작을 때 중지됩니다. 역시, a의 단계-크기가 상수이기 때문에, 우리는 덧셈과 함께 연속적인 b2의 것을 계산할 수 있습니다.

더 나아가서 모듈러 개선은 나눗셈 알고리듬을 아핀 변환, 즉, 임의의 정수 링에 걸쳐 $X=\beta x+a$ , $Y=\beta y+b$ , $N=\beta z+r$ 을 적용함으로써 만들어질 수 있으며, 여기서 $\beta <X$ 입니다. 작은 양의 대수 후에, 우리는 $\lfloor N/\beta ^{2}\rfloor -s=xy$ 및 $\lfloor ab/\beta \rfloor =t$ 임을 결론 지을 수 있으며, 여기서 s와 t는 기본 $\beta$ 에 걸쳐 제수를 곱하는 것에서 올림수를 결정하는 것과 동일합니다.^{[citation needed]}

Multiplier improvement

페르마의 방법은 N의 제곱근 근처에 인수가 있을 때 가장 잘 작동합니다.

만약 두 인수의 근사 비율 ( $d/c$ )이 알려져 있으면, 유리수(rational number) $v/u$ 는 해당 값 근처에서 선택될 수 있습니다. 예를 들어, 만약 $Y/X\approx q$ 이면, $X\approx {\sqrt {N/q}}$ 가 더 작은 제수 쌍에 대해 좋은 근사입니다. $Nuv=cv\cdot du$ 이고, 인수가 대략 같습니다: 페르마의 것은, Nuv에 적용되며, 그것들을 빠르게 찾을 것입니다. 그런-다음 $\gcd(N,cv)=c$ 이고 $\gcd(N,du)=d$ 입니다 (만약 c가 d를 나누지 않거나 d가 v를 나누지 않으면.) 이 접근법의 그 이상의 일반화는 $Y^{n}/X^{m}\approx q$ 임을 가정하며, $X\approx N^{m/(m+n)}/q^{1/(m+n)}$ 임을 의미합니다.

일반적으로, 만약 그 비율이 알려져 있지 않으면, 다양한 $u/v$ 값이 시도될 수 있고, Nuv를 초래하는 각각을 인수로 시도할 수 있습니다. R. Lehman은 페르마의 것 더하기 시도 나눗셈이 $O(N^{1/3})$ 시간에서 N을 인수분해할 수 있도록 이것을 행하기 위한 시스템적인 방법을 고안했습니다.^[1]

Other improvements

페르마의 인수분해 방법의 기본 아이디어는 "최악의 경우"인 큰 반-소수(semiprimes)를 인수화하는 가장-잘-알려진 알고리듬, 이차 체(quadratic sieve) 및 일반적인 숫자 필드 체(general number field sieve)의 기초입니다. 이차 체가 페르마의 인수분해 방법에 걸쳐 만들어진 주요 개선은 단순히 $a^{2}-n$ 의 수열에서 제곱을 찾는 대신에, 그것의 곱이 제곱인 이 수열의 원소의 부부집합을 찾는 것이고, 매우 효율적인 방식으로 이것을 수행하는 것입니다. 최종 결과는 같습니다: 만약 비-자명한 것이면, n을 인수분해하기 위해 사용될 수 있는 제곱 모드 n의 차이입니다.

Notes

^ Lehman, R. Sherman (1974). "Factoring Large Integers" (PDF). Mathematics of Computation. 28 (126): 637–646. doi:10.2307/2005940.

References

Fermat (1894), Oeuvres de Fermat, vol. 2, p. 256
McKee, J (1999). "Speeding Fermat's factoring method". Mathematics of Computation (68): 1729–1737.

External links

Fermat's factorization running time, at blogspot.in
Fermat's Factorization Online Calculator, at windowspros.ru

[1] Lehman, R. Sherman (1974). "Factoring Large Integers" (PDF). Mathematics of Computation. 28 (126): 637–646. doi:10.2307/2005940.

[1]