A+ CATEGORY SCIENTIFIC UNIT

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

Volume 169 / 2015

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

Abstract

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.

Authors

  • 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

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image