본문 바로가기
영문 위키피디아 번역

(번역) Fermat's factorization method

by 다움위키 2024. 2. 10.

 

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

\(\quad\displaystyle N = a^2 - b^2.\)

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

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

\(\quad\displaystyle 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^2\) 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의 크기에 독립적입니다.

Fermat's and trial division

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

\(a\) 48,433 48,434 48,435 48,436
\(b^2\) 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^2\) 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^2\) 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\)에 걸쳐 제수를 곱하는 것에서 올림수를 결정하는 것과 동일합니다.

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을 인수분해할 수 있도록 이것을 행하기 위한 시스템적인 방법을 고안했습니다.

Other improvements

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

See also

References

External links

 

 

관련글

티스토리툴바