Geodesic
Primality test for numbers of the form $(2p)^{2^n}+1$
Yingpu Deng 1   ; Dandan Huang 2
1 Key Laboratory of Mathematics Mechanization, NCMIS Academy of Mathematics and Systems Science Chinese Academy of Sciences 100190, Beijing, P.R. China
2 Key Laboratory of Mathematics Mechanization NCMIS, Academy of Mathematics and Systems Science Chinese Academy of Sciences 100190, Beijing, P.R. China
Acta Arithmetica, Tome 169 (2015) no. 4, pp. 301-317 Cet article a éte moissonné depuis la source Institute of Mathematics Polish Academy of Sciences

Voir la notice de l'article

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.
DOI : 10.4064/aa169-4-1
Keywords: describe primality test odd prime positive integer which particular type generalized fermat numbers present special primality criteria odd prime numbers exceeding these primality tests run deterministic polynomial time input size log special pth power reciprocity law deduce result

Yingpu Deng  1   ; Dandan Huang  2

1 Key Laboratory of Mathematics Mechanization, NCMIS Academy of Mathematics and Systems Science Chinese Academy of Sciences 100190, Beijing, P.R. China
2 Key Laboratory of Mathematics Mechanization NCMIS, Academy of Mathematics and Systems Science Chinese Academy of Sciences 100190, Beijing, P.R. China 
@article{10_4064_aa169_4_1,
     author = {Yingpu Deng and Dandan Huang},
     title = {Primality test for numbers of the form $(2p)^{2^n}+1$},
     journal = {Acta Arithmetica},
     pages = {301--317},
     year = {2015},
     volume = {169},
     number = {4},
     doi = {10.4064/aa169-4-1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/aa169-4-1/}
}
TY  - JOUR
AU  - Yingpu Deng
AU  - Dandan Huang
TI  - Primality test for numbers of the form $(2p)^{2^n}+1$
JO  - Acta Arithmetica
PY  - 2015
SP  - 301
EP  - 317
VL  - 169
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4064/aa169-4-1/
DO  - 10.4064/aa169-4-1
LA  - en
ID  - 10_4064_aa169_4_1
ER  - 
%0 Journal Article
%A Yingpu Deng
%A Dandan Huang
%T Primality test for numbers of the form $(2p)^{2^n}+1$
%J Acta Arithmetica
%D 2015
%P 301-317
%V 169
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4064/aa169-4-1/
%R 10.4064/aa169-4-1
%G en
%F 10_4064_aa169_4_1
Yingpu Deng; Dandan Huang. Primality test for numbers of the form $(2p)^{2^n}+1$. Acta Arithmetica, Tome 169 (2015) no. 4, pp. 301-317. doi: 10.4064/aa169-4-1

Cité par Sources :