Pepin의 테스트의 계산 복잡성

Question

허락하다 $F_{n} = 2^{2^{n}} + 1$, 어디 $n > 0$.

Pepin의 테스트는 다음과 같이 주장합니다. $F_{n}$ 다음과 같은 경우에만 프라임입니다. $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$.

질문 : 무엇이 큰가요?$\mathcal O$ ``반복 제곱 ''알고리즘으로 구현 된 경우이 테스트의 복잡성?

또한 : Pepin의 검정보다 더 효율적인 Fermat 수의 소수성을 결정하는 다른 검정이 있습니까?

Answer 1

이 테스트는 다음 여부를 테스트하는 것과 같습니다. $3^{\frac{F_n-1}{2}} = -1\bmod F_n$. 이것은 대략 크기의 정수를 조작한다는 것을 의미합니다.$\log_2(F_n) \simeq 2^n$. 반복 된 제곱을 통해 수행해야합니다.$O(\log(\frac{F_n-1}{2})) = O(2^n)$ 이러한 정수에 대한 작업은 각각 비용이 $O(n2^n)$알려진 가장 빠른 정수 곱셈 알고리즘을 사용합니다. 전체적으로 복잡성은$O(n4^n)$.

나는 더 빠른 테스트를 모른다.