페르마의 인자화법

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Fermat의 인자화 방법" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2022년 2월) (이 템플릿 메시지 삭제 방법과 시기 학습)

피에르 드 페르마의 이름을 딴 페르마의 인자화 방법은 홀수 정수를 다음과 같은 두 제곱의 차이로 표현한 것에 기초한다.

${\displaystyle N=a^{2}-b^{2}.}$

그 차이는 대수적으로 ${\displaystyle (+b}$)${\displaystyle }$(${\displaystyle }$- ${\displaystyle b}$) ${\displaystyle (a+b)(a-b)}$로서 인수할 수 있다$.$ 두 요인이 1과 동일하지 않으면 N의 적절한 인수화다.

각각의 홀수에는 그러한 표현이 있다.실제로 $N{\displaystyle }$= c ${\displaystyle d}$ ${\displaystyle N=cd}$이(가) N의 인수인자인 경우$$

${\displaystyle N=\left({\frac {c+d}{2)}}}\오른쪽)^{2}}-\왼쪽 \frac {c-d}{2}}\오른쪽)^{2}}:$

N은 홀수이므로, c와 d도 홀수이므로, 그 반쪽은 정수다. (4의 배수도 제곱의 차이다: c와 d는 짝수다.)

가장 간단한 형태에서 페르마의 방법은 재판 분할(최악의 경우)보다 더 느릴 수 있다.그럼에도 불구하고 둘 중 어느 쪽보다 시험 구획과 페르마의 조합이 더 효과적이다.

기본법

${\displaystyle {2\mathrm{}}^{}}$- ${\displaystyle N}$= b ${\displaystyle {2\mathrm{}}^{}}$ ${\$ 제곱을 바라면서 a의 다양한 값을 시도한다.

FermatFactor(N): // N should be odd     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) // or a + sqrt(b2)

예를 들어, $N{\displaystyle }$= ${\displaystyle 5959}$ ${\displaystyle N=5959}$을(를) 인자화하기 위해$,$ a에 대한 첫 번째 시도는 다음 정수까지 반올림한 5959의 제곱근으로, 78이다.그런 $다음{\displaystyle {}^{}}$ ${\displaystyle {b\mathrm{}}^{}}$2 = ${\displaystyle {78\mathrm{}}^{}}$2 - ${\displaystyle 5959}$ ${\displaystyle =}$ ${\displaystyle 125}${\$displaystyle$ b$^{2}=78^{2$}-$559=125$ 125는 정사각형이 아니기 때문에 a 값을 1씩 높여 재시도한다.282는 다시 정사각형이 아니기 때문에 두 번째 시도 역시 실패한다.

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

세 번째 시도는 441의 완벽한 정사각형을 만들어낸다.따라서 $a{\displaystyle }$= ${\displaystyle 80}$ ${\displaystyle a=80$ b${\displaystyle }$= ${\displaystyle 21}$ ${\displaystyle b=21$ 5959의 요인은${\displaystyle }$- ${\displaystyle b}$= ${\displaystyle 59}$ ${\displaystyle a-b=59},$ +${\displaystyle }$b${\displaystyle }$= ${\displaystyle 101}$ ${\displaysty a+b=101}$이다$.$

N에 두 가지 이상의 주요 요인이 있다고 가정합시다.이 절차는 먼저 a와 b의 최소값을 갖는 인자화를 찾는다.즉${\displaystyle ,}$ + ${\displaystyle b}$ ${\displaystyle a+$${\displaystyle b}$$}$이(가) N의 제곱근인 ≥ 가장 작은 요인이고, ${\displaystyle \mathrm{따라서}}$- ${\displaystyle b}$= N${\displaystyle }$/${\displaystyle }$(${\displaystyle }$+ ${\displaystyle b}$)$${\$displaystyle a-b=N/(a$+b$)}$이(가) 가장 큰 요인 ≤ root-N이다.$절차$에서${\displaystyle }$N = ${\displaystyle 1}$ ${\displaystyle \cdot }$N {\$displaystyle N=1\cdot$ N$\}$을$($를) 발견하면 N이 prime임을 나타낸다.

$N{\displaystyle }$= ${\displaystyle d}$ ${\displaystyle N=cd}$의 경우 c를 가장 큰 하위 루트 계수가 되도록 한다$.$${\displaystyle a=(c+d)/2}$, so the number of steps is approximately ${\displaystyle (c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c}$.

N이 primary인 경우${\displaystyle (\mathrm{c}}$ =$$1 {\$displaystyle c=1})$ $O{\displaystyle (N}$) ${\displaystyle O(N)}$ 단계가$$ 필요하다.$$이것은 원시성을 증명하는 나쁜 방법이다.그러나 N이 제곱근에 가까운 인자를 가지고 있다면 그 방법은 빠르게 작용한다.보다 정확히 말하면$,$ c가 $({\displaystyle {4\mathrm{}}^{}}$ ${\displaystyle N^{}}$) ${\displaystyle 1^{\mathrm{}}}$/ ${\displaystyle {4\mathrm{}}^{}}$ ${\$에서 $N{\displaystyle \sqrt{}}$ {\$displaystyle {\sqrt{N}}}$보다 작을 경우$,$ 방법은 한 단계만 필요하며, 이는 N의 크기와는 무관하다.^{[citation needed]}

페르마의 재판부

소수점 N = 2345678917을 고려하되, 전체에서 b와 a - b도 계산해 보십시오.$N{\displaystyle \sqrt{}}$ ${\$에서 위로 올라가면 다음 표로 만들 수 있다$.$

a	48,433	48,434	48,435	48,436
b2	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{\displaystyle }$- ${\displaystyle b}$= ${\displaystyle 47830.1}$ ${\displaystyle a-b=47830.1}$보다 높은 하위 루트 인수를 가지고 있었다면 페르마의 방법은 이미 그것을 발견했을 것이라는 점을 관찰하라$.$

재판부에서는 보통 48,432까지 시도할 것이다; 그러나 단지 네 번의 페르마 단계 후에, 우리는 요소를 찾거나 원시성을 증명하기 위해 47830까지 나누기만 하면 된다.

이 모든 것은 복합적인 팩토링 방법을 시사한다.일부 바운드 > ${\$$sqrt{N$$}}$을 선택하고 $N{\displaystyle \sqrt{}}$ ${\displaystyle$ {$N$$}$과($와{\displaystyle }$) ${\displaystyc}$ 사이의 요인에 Fermat의 방법을 사용하십시오$.$$이렇게{\displaystyle }$ 하면 c${\displaystyle }$- ${\displaystyle c\sqrt{{}^{}}}$ ${\displaystyle \sqrt{{2\mathrm{}}^{}}}$- ${\displaystyle \sqrt{N}}$ ${\$인 시험 구분에 대한 바운드가 주어진다$.$ $위$의 예에서${\displaystyle }$c = ${\displaystyle 48436}$ ${\displaysty$c=$48436}$을(를) 사용하여$$ 시험 구분에 대한 바운드는 47830이다.합리적인 선택은 $c{\displaystyle }$= ${\displaystyle 55000}$ ${\displaystyle c=55000}$이(가) 28937의 한계일 수 있다.

이런 점에서 페르마의 방법은 수익이 줄어든다.이 시점 이전에 반드시 멈출 것이다.

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

체 개선

$N{\displaystyle }$= ${\displaystyle 2345678917}$ ${\displaystyle N=2345678917$에 대한 표를 고려할 때 b ${\displaystyle {2\mathrm{}}^{}}$ ${\$의 값 중 어느 것도 제곱이$$ 아님을 금방 알 수 있다.

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

${\displaystyle {2\mathrm{}}^{}}$ -${\displaystyle {}^{}N}$ ${\displaystyle$ a$^{2}-N$의 제곱근을 모두 계산하거나 a에 대한 모든 값을 검사할 필요는 없다. 제곱은 항상 0, 1, 4, 5, 9, 16 modulo 20에 일치한다.이 값은 a가 10씩 증가할 때마다 반복된다.이 예제에서 N은 17모드 20이므로 17모드 20(또는 추가 3)을 빼면 ${\displaystyle {2\mathrm{}}^{}}$ -${\displaystyle {}^{}N}$ ${\displaystyle$ a$^{2}-N}$은 $이러한{\displaystyle {}^{}}$ 값에 대해 3, 4, 7, 8, 12, 19모듈로 20을 생성한다$$.이 목록의 4개만 정사각형이 될 수 있다는 것은 명백하다.따라서 ${\displaystyle {2\mathrm{}}^{}}$ ${\$은 1모드 20이어야 하며$$, 이는 a가 1, 9, 11 또는 19모드 20이라는 것을 의미하며, 4모드 20으로 $끝나는$ b ${\displaystyle {2\mathrm{}}^{}}${\$displaystyle b^{2$}}을 생성하며, 사각형인 경우 b는 2 또는 8모드 10으로 끝난다.

이것은 어떤 계량으로도 수행할 수 있다.동일한 $N{\displaystyle }$= ${\displaystyle 2345678917}$ ${\displaystyle N=2345678917}$ 사용$,$

모듈로 16:	정사각형은	0, 1, 4, 9
	N mod 16은	5
	${\displaystyle {그래서\mathrm{}}^{}}$ 2 ${\$개만이 될 수 있다$$.	9
	그리고 a는 반드시	3 또는 5 또는 11 또는 13 모듈로 16
모듈로9:	정사각형은	0, 1, 4, 7
	N mod 9는	7
	${\displaystyle {그래서\mathrm{}}^{}}$ 2 ${\$개만이 될 수 있다$$.	7
	그리고 a는 반드시	4~5모듈로9번길

사람은 일반적으로 각 계수에 대해 다른 전성기의 힘을 선택한다.

a-값(시작, 종료, 스텝)과 계수의 순서를 지정하면 다음과 같이 진행할 수 있다.

FermatSieve(N, ostart, aend, astep, modulus) ← 아스타트 do modulus 시간: b2 2 a*a - N(b2가 정사각형인 경우 modulo modulus:FermatSieve(N, a, aend, ostep * modulus, NextModulus) end if a + ostep enddo

그러나 a-값이 거의 남아 있지 않을 때, 즉 (종료)/아스텝이 작을 때 재귀가 정지된다.또한 a의 스텝 사이즈는 일정하기 때문에 덧셈으로 연속 b2를 계산할 수 있다.

승수개선

페르마의 방법은 N의 제곱근 근처에 인자가 있을 때 가장 잘 듣는다.

두 요인(${\displaystyle }$/ ${\displaystyle c}$ ${\displaystyle d/c$의 대략적인 비율이 알려진 경우 해당 값 근처에서 합리적인 숫자 $v{\displaystyle /u}$ ${\displaystyle v/u}$을(를) 선택할 수 있다$$.${\displaystyle N}$ ${\displaystyle u}$ v${\displaystyle }$= ${\displaystyle c}$ ${\displaystyle v}$ ${\displaystyle \cdot }$ ${\displaystyle d}$ ${\displaystyle u}$ ${\displaystyle Nuv=cv\cdot du$ 그리고 Nuv에 적용된 Fermat의 방법은 c $v{\displaystyle }$ ${\displaystyle v}$ ${\displaysty cv}$ 및 $d$ ${\displaystyle u}$ ${\displaystydu}$ 인자를$$ 빠르게 찾을 것이다.그런 다음 ${\displaystyle gcd(N}$, ${\displaystyle c}$ ${\displaystyle v}$)${\displaystyle }$= ${\displaystyle c}$ ${\displaystyle \gcd(N,cv)=c}$ 및$$ ${\displaystyle gcd(N,}$ ${\displaystyle \mathrm{du}}$)${\displaystyle }$= ${\displaystyle d}$ ${\displaystyle \gcd(N,$du$)=d}$. (c가 u를 나누지 않는 한)

일반적으로 비율을 알 수 없는 경우, 다양한 $u{\displaystyle /v}${\$displaystyle u/v}$ 값을$$ 시도할 수 있으며, 그 결과 Nuv. R. 리먼은 이를 위해 체계적인 방법을 고안하여 Fermat의 플러스 시험 $분할$이${\displaystyle {}^{}}$ ${\displaystyle {in\mathrm{}}^{}}$O (${\displaystyle {N\mathrm{}}^{}}$ 1${\displaystyle {}^{}}$/$$3 ){\$displaysty O(N^{$1/$3}})$ 시간을 고려할$$ 수 있다.^[1]

기타 개선사항

페르마의 인자화 방법의 근본 사상은 2차 체와 일반수 필드 체의 기초로서, 큰 반수를 인수하기 위한 가장 잘 알려진 알고리즘으로 '최악의 경우'이다.2차 체가 페르마의 인자화 방법보다 1차적으로 개선한 것은 ${\displaystyle \mathrm{단순히}}$ 2 -${\displaystyle {}^{}}$n ${\displaystyle$ a$^{2}-n}$의 순서로 정사각형을 찾는 대신$,$ 제품이 정사각형인 이 시퀀스의 원소의 하위 집합을 찾아내고, 매우 효율적인 방법으로 이를 수행하는 것이다.최종 결과는 같다:비교적일 경우 n을 인자화하기 위해 사용할 수 있는 제곱 모드의 차이.

직사각형을 사용한 인자화

상수 c: ${\displaystyle (+c}$) ${\displaystyle \times }$ ${\displaystyle a}$-${\displaystyle }$(${\displaystyle b}$ ${\displaystyle +c}$ ) ${\displaystyle \times b}$= ( - ${\displaystyle b}$)${\displaystyle \times }$ ( - b ) × (${\displaystyle }$+ ${\displaystyle b}$) ×${\displaystyle }$( + ${\displaystyle b}$ )$$× ( + b + c${\displaystyle )}$ {\$displaystyle (a+c)\time b=(a-b)\$times (a+b+$c)\$time ($a+c)}$을 추가하여 사각형($a+c$)을 사용하도록 방법을 수정할 수 있다.

큐브를 사용한 인자화

${\displaystyle a^{3}-b^{3}=(a-b)\message ((a+b)\message a+b\message b)}$

큐보이드로 인자화

${\displaystyle (a+c)\b^{2}-(b+c)\b^{2}=(a-b)\cape(a+b+c)\cape a+(b+c)\b)}$

참고 항목

• 정사각형 완성
• 다항식의 인자화
• 인자 정리
• FLE 규칙
• 모노이드 인자화
• 파스칼 삼각형
• 프라임인자
• 인자화
• 오일러의 인자화법
• 정수 인자화
• 프로그램 합성
• 가우스 정수 인자 표
• 고유 인자화

메모들

참조

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

외부 링크

• 블로그스팟에서 페르마의 인자화 실행 시간.에
• 페르마의 인자화 온라인 계산기, windowspros.ru