페핀 시험

수학에서, 페핀의 테스트는 원시성 테스트로, 페르마 숫자가 프라임인지 여부를 결정하는 데 사용될 수 있다.그것은 프로스의 시험의 변형이다.이 시험은 프랑스의 수학자 테오필 페핀의 이름을 따서 명명되었다.

테스트 설명

$F{\displaystyle {}_{}}$ ${\displaystyle n_{}}$= ${\displaystyle {{2n}^{}}^{}}$+ ${\displaystyle 1}$ ${\displaystyle F_{n}=2^{2^{n}+1$}을$($를) n번째 페르마트가 되도록$$ 한다.Pépin의 테스트에 의하면 n > 0에 대해서는,

${\displaystyle F_{}}$ ${\displaystyle n_{}}$ ${\displaystyle {{}_{}}^{}}$$displaystyle F_{n}$는 $3{\displaystyle {\mathrm{}}^{}}$(${\displaystyle {\mathrm{F}}^{}}$ - 1${\displaystyle {}^{}}$) / ${\displaystyle 2{/}^{}}$ - 1${\displaystyle }$(${\displaystyle 모드{}_{}}$ ${\displaystyle F_{}}$)${\displaystyle }$. ${\displaystyle$ 3$^{(F_{n}-1)/2}\equiv -1{\pmod{F_{n}}}}}$인 경우에만 프라임이다$$.$}$

$3{\displaystyle {\mathrm{}}^{(\mathrm{F}}}$ ${\displaystyle {n_{}}^{}}$- 1${\displaystyle {}^{}}$)${\displaystyle {}^{}}$/ ${\displaystyle {2\mathrm{}}^{}}$ ${\$ 3$^{(F_{n}-1)/2}}$의 표현은 반복적인 스쿼링으로 modulo ${\$를 평가할 수 있다$$.따라서 테스트는 빠른 다항식 시간 알고리즘이 된다.그러나 페르마 수는 매우 빠르게 증가하여 소수의 페르마 숫자만이 합리적인 양의 시간과 공간에서 시험될 수 있다.

다른 베이스는 3 대신 사용할 수 있으며, 이러한 베이스는

3, 5, 6, 7, 10, 10, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48, 51, 54, 56, 65, 75, 78, 80, 82, 85, 90, 91, 96, 102, 102, 105, 112, 119, 126, 126, 147, 156, 160, OEIS(시퀀스 A129802).

위의 순서에 있는 프라임은 Elite 프라임이라고 불리며, 그것들은

3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041, 163841, 544001, 604801, 6684673, 14172161, 159318017, 446960641, 1151139841, 3208642561, 38126223361, 108905103361, 171727482881, 318093312001, 443069456129, 912680550401, ... (sequence A102742 in the OEIS)

정수 b > 1의 경우${\displaystyle }$(${\displaystyle \frac{{}_{}}{}\frac{F_{}}{}}$ n ) = 1${\displaystyle \left({\frac {b}{{\$frac {b}{)를 유한한 수의 페르마트 숫자 F가_n ${\displaystyle \mathrm{만족}}$하는 경우에만 base b를 사용할 수 있다.$F_{n}}\오른쪽)=1$ 여기서${\displaystyle }$(${\displaystyle \frac{{}_{}}{}}$ ${\displaystyle \frac{F_{}}{}}$ n${\displaystyle \frac{{}_{}}{}}$) ${\$$F_{n}}}\오른쪽)$은 자코비 기호다.

실제로 페핀의 테스트는 자코비 기호$({\displaystyle B\frac{}{}}$ $){\${b$}{\$frac {b}{){이후 페르마트 숫자에 대한 오일러-자코비 테스트와 동일하다.$F_{n}}\right)}$은 -1, 즉 위에 열거한 베이스에 오일러 자코비 유사시인 페르마 숫자가 없다.

정확성 증명

자급률: 합치성을 가정한다.

${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod{F_{n}}}}}}}$

holds. Then ${\displaystyle 3^{F_{n}-1}\equiv 1{\pmod {F_{n}}}}$, thus the multiplicative order of 3 modulo ${\displaystyle F_{n}}$ divides ${\displaystyle F_{n}-1=2^{2^{n}}}$, which is a power of two.On the other hand, the order does not divide ${\displaystyle (F_{n}-1)/2}$, and therefore it must be equal to ${\displaystyle F_{n}-1}$. In particular, there are at least ${\displaystyle F_{n}-1}$ numbers below ${\displaystyle F_{n}}$ coprime to ${\displayst$$yle F_{n}}$, 그리고 이것은 $F{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$가 prime일 경우에만 발생할 수 있다.

필요성: $F{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$가 프라임이라고 가정한다.오일러의 기준으로 보면

${\displaystyle 3^{}}$(${\displaystyle {\mathrm{F}}^{}}$ ${\displaystyle {n_{}}^{}}$- 1${\displaystyle {}^{}}$)${\displaystyle {}^{}}$/ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle (3\frac{\mathrm{}}{}}$ ${\displaystyle \frac{F_{}}{}}$ ${\displaystyle \frac{{}_{}}{}}$) ${\displaystyle (\mathrm{모드}}$ ${\displaystyle F_{}}$ ${\displaystyle n{}_{}}$) ${\$

여기서${\displaystyle }$(${\displaystyle \frac{{3Fn}_{}}{}}$) ${\$은 범례 기호다.By repeated squaring, we find that ${\displaystyle 2^{2^{n}}\equiv 1{\pmod {3}}}$, thus ${\displaystyle F_{n}\equiv 2{\pmod {3}}}$, and ${\displaystyle \left({\frac {F_{n}}{3}}\right)=-1}$. As ${\displaystyle F_{n}\e$$quiv 1{\pmod$${\displaystyle \frac{{}_{}}{}}$$4$${\displaystyle \}\}\},}$ 우리는 2차 상호주의 법칙으로부터$$ $({\displaystyle \frac{3_{}}{}}$ ${\displaystyle \frac{{}_{}}{}}$ ) = -$$ {\$displaystyle \left({\frac {3}{F_{n}}}\right)=-1}$로 결론을 내린다.

과거 페핀 테스트

페르마 숫자의 첨탑성 때문에 페핀 테스트는 (원초성 상태가 아직 알려지지 않은 페르마 숫자에 대해) 8번밖에 실행되지 않았다.^[1][2][3]메이어, 파파도풀로스, 크랜달은 사실 아직 결정되지 않은 페르마 숫자의 크기 때문에, 더 이상의 페핀 시험이 합리적인 시간 안에 실행되기까지는 상당한 기술 발전이 필요할 것이라고 추측한다.^[4]2021년^[update] 현재 가장 시험되지 않은 Fermat의 가장 작은 숫자는 2,585,827,973자리의 F ${\$이다.

연도	프로버스	페르마 수	페핀 테스트 결과	나중에 인자를 찾으십니까?
1905	모어헤드 & 웨스턴	${\displaystyle F_{7}}$	복합의	예 (1970)
1909	모어헤드 & 웨스턴	${\displaystyle F_{8}}$	복합의	예 (1980)
1952	로빈슨	${\displaystyle F_{10}}$	복합의	예 (1953)
1960	팍슨	${\displaystyle F_{13}}$	복합의	예 (1974년)
1961	셀프리지&허위츠	${\displaystyle F_{14}}$	복합의	예(2010)
1987	부엘앤영	${\displaystyle F_{20}}$	복합의	아니요.
1993	크랜달, 도니아스, 노리 & 영	${\displaystyle F_{22}}$	복합의	예(2010)
1999	메이어, 파파도풀로스 & 크랜달	${\displaystyle F_{24}}$	복합의	아니요.

메모들

참조

• P. P. Pépin, Sur la formule ${\displaystyle {{2n}^{}}^{}}$+ ${\displaystyle 1}$ ${\displaystyle$ 2$^{2^{n}+1$ Competes rendus de l'Academie des Science de Paris 85(1877), 페이지 329–333.

외부 링크

• 프라임 용어집: 페핀의 시험