Tentang kompleksitas komputasi uji Pepin

Question

Membiarkan $F_{n} = 2^{2^{n}} + 1$, dimana $n > 0$.

Tes Pepin menegaskan hal itu $F_{n}$ adalah bilangan prima jika dan hanya jika $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$.

PERTANYAAN: Apa yang besar-$\mathcal O$ kompleksitas tes ini jika diimplementasikan dalam algoritma dengan `` kuadrat berulang ''?

JUGA: Apakah ada tes lain untuk menentukan primalitas bilangan Fermat yang lebih efisien daripada Tes Pepin?

Answer 1

Tes ini setara dengan menguji apakah $3^{\frac{F_n-1}{2}} = -1\bmod F_n$. Ini berarti Anda memanipulasi bilangan bulat dengan ukuran secara kasar$\log_2(F_n) \simeq 2^n$. Dengan kuadrat berulang, Anda harus tampil$O(\log(\frac{F_n-1}{2})) = O(2^n)$ operasi pada bilangan bulat tersebut, dan masing-masing memiliki biaya $O(n2^n)$menggunakan algoritma perkalian bilangan bulat tercepat yang diketahui. Secara keseluruhan, kompleksitasnya adalah$O(n4^n)$.

Saya tidak tahu tes yang lebih cepat.