JEDNOSTKA NAUKOWA KATEGORII A+

Primality test for numbers of the form $(2p)^{2^n}+1$

Tom 169 / 2015

Yingpu Deng, Dandan Huang Acta Arithmetica 169 (2015), 301-317 MSC: Primary 11A51; Secondary 11Y11. DOI: 10.4064/aa169-4-1

Streszczenie

We describe a primality test for $M=(2p)^{2^n}+1$ with an odd prime $p$ and a positive integer $n$, which are a particular type of generalized Fermat numbers. We also present special primality criteria for all odd prime numbers $p$ not exceeding $19$. All these primality tests run in deterministic polynomial time in the input size $\log_{2}M$. A special $2p$th power reciprocity law is used to deduce our result.

Autorzy

  • Yingpu DengKey Laboratory of Mathematics Mechanization, NCMIS
    Academy of Mathematics and Systems Science
    Chinese Academy of Sciences
    100190, Beijing, P.R. China
    e-mail
  • Dandan HuangKey Laboratory of Mathematics Mechanization
    NCMIS, Academy of Mathematics and Systems Science
    Chinese Academy of Sciences
    100190, Beijing, P.R. China
    e-mail

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek