Pepin testinin hesaplama karmaşıklığı hakkında

Question

İzin Vermek $F_{n} = 2^{2^{n}} + 1$, nerede $n > 0$.

Pepin'in Testi şunu iddia ediyor: $F_{n}$ asaldır ancak ve ancak $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$.

SORU: Büyük olan nedir?$\mathcal O$ Bu testin karmaşıklığı, `` tekrarlanan kare alma '' ile bir algoritmada uygulanıyorsa?

AYRICA: Bir Fermat sayısının asallığını belirlemek için Pepin Testinden daha etkili başka testler var mı?

Answer 1

Test, aşağıdakileri test etmeye eşdeğerdir: $3^{\frac{F_n-1}{2}} = -1\bmod F_n$. Bu, boyuttaki tam sayıları kabaca işlediğiniz anlamına gelir.$\log_2(F_n) \simeq 2^n$. Yinelenen kareyi alarak, gerçekleştirmek zorundasınız$O(\log(\frac{F_n-1}{2})) = O(2^n)$ bu tür tam sayılar üzerindeki işlemler ve her birinin maliyeti vardır $O(n2^n)$bilinen en hızlı tamsayı çarpma algoritmasını kullanarak. Toplamda karmaşıklık$O(n4^n)$.

Daha hızlı bir test bilmiyorum.